Homework #7


1.  Show that the language L = {a^i b^j c^k: i < j < k} is not a context-free
language.


2.  Show that the language L = {a^i: is is a prime} is not a context-free
language.


3.  Is the language L = {w w^R w: w is in {a,b}*} a context-free language?
Prove or disprove your answer.


4.  Show that CFLs are closed under the REVERSE operation, where
REVERSE(L) = {x: x^R is in L}.


5.  How would you modify the CYK algorithm (or the dynamic programming
algorithm presented in the book, choose either one) to produce an actual
derivation of x in G?


6.  Use the CYK algorithm for the grammar G below to determine whether
    a) aaaaa
    b) aabbab

    are in the language generated by grammar G.

    G = ({S, A, B, C, a, b}, {a, b}, R, S)
    R = {S -> AB | BC
	 A -> BA | a
	 B -> CC | b
	 C -> AB | a}