Paper 3, Section I, F

Automata and Formal Languages
Part II, 2020

Define a context-free grammar GG, a sentence of GG and the language L(G)\mathcal{L}(G) generated by GG.

For the alphabet Σ={a,b}\Sigma=\{a, b\}, which of the following languages over Σ\Sigma are contextfree? (i) {a2mb2mm0}\left\{a^{2 m} b^{2 m} \mid m \geqslant 0\right\},

(ii) {am2bm2m0}\left\{a^{m^{2}} b^{m^{2}} \mid m \geqslant 0\right\}.

[You may assume standard results without proof if clearly stated.]