Paper 1, Section I, 4 F4 \mathrm{~F}

Automata and Formal Languages
Part II, 2016

State the pumping lemma for context-free languages (CFLs). Which of the following are CFLs? Justify your answers.

(i) {a2nb3nn3}\left\{a^{2 n} b^{3 n} \mid n \geqslant 3\right\}.

(ii) {a2nb3nc5nn0}\left\{a^{2 n} b^{3 n} c^{5 n} \mid n \geqslant 0\right\}.

(iii) {app\left\{a^{p} \mid p\right. is a prime }\}.

Let L,ML, M be CFLs. Show that LML \cup M is also a CFL.