Paper 4, Section I, 4F4 F

Automata and Formal Languages
Part II, 2020

Define what it means for a context-free grammar (CFG) to be in Chomsky normal form (CNF)(\mathrm{CNF}).

Describe without proof each stage in the process of converting a CFG G=G= (N,Σ,P,S)(N, \Sigma, P, S) into an equivalent CFG Gˉ\bar{G} which is in CNF. For each of these stages, when are the nonterminals NN left unchanged? What about the terminals Σ\Sigma and the generated language L(G)\mathcal{L}(G) ?

Give an example of a CFG GG whose generated language L(G)\mathcal{L}(G) is infinite and equal to L(Gˉ)\mathcal{L}(\bar{G}).