Past exam of the mathematics course of the University of Cambridge / 2022 / ii / Paper 4 / 4I / Solution

A context-free grammar is in Chomsky normal form when every production has one of the formswhere $A,B,C$ are nonterminals and $a$ is a terminal. One may additionally allow $S\to ϵ$ when the empty word belongs to the language, usually with the restriction that the start symbol does not occur on a right-hand side.

An $ϵ$-production has the form $A\to ϵ$. A unit production has the form $A\to B$ for nonterminals $A,B$.

In $G_1$, the productions for $T$ giveConsequentlyIn $G_2$, $X$ and $Y$ generate $a$ and $b$, while $T\to TX\mid TY\mid c$ again givesSince $Z\to TX$, the two start productions $S\to XZ\mid YZ$ generate exactlyThusEvery production of $G_2$ has the required binary-nonterminal or single-terminal form, so $G_2$ is the Chomsky-normal-form grammar for the nonempty part of $L(G_1)$.