Past exam of the mathematics course of the University of Cambridge / 2018 / ii / Paper 3 / 4G / b / Solution

The standard conversion of a context-free grammar to Chomsky normal form proceeds as follows:

Add a fresh start symbol $S_0$ with $S_0\to S$.
Find the nullable nonterminals, add the variants obtained by omitting nullable occurrences, and remove all epsilon productions. Omit $S_0\to ϵ$ as well because the requested language excludes $ϵ$.
Remove every unit production $A\to B$ by copying the non-unit productions reachable from $B$ to $A$.
Remove nonterminals that are unreachable from $S_0$ or cannot derive a terminal word.
In every right-hand side of length at least two, replace a terminal $a$ by a fresh nonterminal $T_a$ with $T_a\to a$.
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 $\mathcal{L}(G_{\mathrm{Chom}})=\mathcal{L}(G)\setminus \{ϵ\}$.