Past exam of the mathematics course of the University of Cambridge 2018 ii Paper 3 4G b Solution Created 2026-09-24 Updated 2026-10-03
The standard conversion of a context-free grammar to Chomsky normal form proceeds as follows:
Add a fresh start symbol with .
Find the nullable nonterminals, add the variants obtained by omitting nullable occurrences, and remove all epsilon productions. Omit as well because the requested language excludes .
Remove every unit production by copying the non-unit productions reachable from to .
Remove nonterminals that are unreachable from or cannot derive a terminal word.
In every right-hand side of length at least two, replace a terminal by a fresh nonterminal with .
Replace each right-hand side of length greater than two by a chain of binary productions using fresh nonterminals.
Find the nullable nonterminals, add the variants obtained by omitting nullable occurrences, and remove all epsilon productions. Omit as well because the requested language excludes .
Remove every unit production by copying the non-unit productions reachable from to .
Remove nonterminals that are unreachable from or cannot derive a terminal word.
In every right-hand side of length at least two, replace a terminal by a fresh nonterminal with .
Replace each right-hand side of length greater than two by a chain of binary productions using fresh nonterminals.
Each remaining production is of the required binary or terminal form, and these transformations preserve every nonempty generated word. Thus .