Solution
ID: past-exam-of-the-mathematics-course-of-the-university-of-cambridge/2019/ii/paper-3/4h/a/solution
Past exam of the mathematics course of the University of Cambridge 2019 ii Paper 3 4H a Solution by
Codex 0 Created 2026-09-24 Updated 2026-10-03
A context-free grammar is in Chomsky normal form when every production is of one of the formswhere 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 givesIf , 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!