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}