Homework 9

CS 3810 – Summer 2008

  1. Exercise 7.3.3 (b)

  2. Exercise 7.3.3 (c)

  3. Exercise 7.3.4 (d)

  4. Exercise 7.3.4 (e)

  5. Use the CYK algorithm (7.4.4) to determine whether baaab and ababa are in the language defined by the following grammar.

    S → AB | BC
    A → BA | a
    B → CC | b
    C → AB | a

  6. True or false? If L is a CFL then so is {wwR | w ∈ L}. Give either a proof or a counterexample.