Past exam of the mathematics course of the University of Cambridge / 2023 / ii / Paper 1 / 4I / a / Solution

A context-free grammar is in Chomsky normal form when every production is of one of the formswhere $A,B,C$ are nonterminal symbols and $a$ is a terminal symbol. The conventional exceptional production $S\to ϵ$ may be allowed when the language contains the empty word, with $S$ excluded from right-hand sides.