Past exam of the mathematics course of the University of Cambridge / 2018 / ii / Paper 3 / 4G (Automata and Formal Languages)

A context-free grammar is in Chomsky normal form when every production rule has one of the formswhere $A,B,C$ are nonterminal symbols and $a$ is a terminal symbol. If the language contains the empty word, one may additionally permit $S_0\to ϵ$, with the start symbol $S_0$ absent from all right-hand sides.

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 \{ϵ\}$.

The original grammar generatesbecause each use of $S\to ASc$ adds one $a$ on the left and one $c$ on the right, and $S\to B\to b$ terminates the derivation.

Introduce nonterminals $S_0,X,C$ and useEvery production is in Chomsky normal form. The production $X\to SC$ completes one matched $a,c$ pair, while either start-like symbol terminates with $b$, so the grammar generates exactly the same language. These productions are a valid $G_{\mathrm{Chom}}$.