Solution

ID: past-exam-of-the-mathematics-course-of-the-university-of-cambridge/2019/ii/paper-3/4h/a/solution

A context-free grammar is in Chomsky normal form when every production is of one of the forms
where are nonterminal symbols and is a terminal symbol. Under this strict convention there is no epsilon production, so such a grammar cannot generate the empty word. Conversion of an arbitrary grammar therefore gives
If , the two languages are equal. An alternative extended convention permits the exceptional start production ; under that convention conversion preserves the whole language.

New to topics? Read the docs here!