1. Show that if L is context free, then L^R = {x^R: x in L} (where x^R is x read backwards) is also context free.
2. Give a CFG for the language L = {a^ib^jc^k: i+j = k}.
3. Give a PDA for the language from the previous problem. Use the algorithm for tranforming a CFG to a PDA, rather than constructing the PDA directly.
4. Consider the language L = {a^ib^ia^{2i}: i in N}. Use the pumping lemma for context-free languages to prove that it is not context free.
5.
True or false?
a)
If L1 is regular and L2 is context free then L1 intersect L2 is context free.
b)
If L1 is context free and L2 is context free then L1 intersect L2 is context free.