Past exam of the mathematics course of the University of Cambridge / 2023 / ii / Paper 1 / 4I (Automata & Formal Languages)

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.

The length isIndeed, the parse tree has $n$ terminal-production nodes and, as a full binary tree with $n$ leaves, $n-1$ binary-production nodes. This is the Chomsky-normal-form derivation length.

One parse tree can be recorded unambiguously by the nested expressionEvery internal node uses one of the given productions, and the leaves read from left to right areEquivalently, the corresponding leftmost grammar derivation isHence the required word is generated by the grammar.

TakewhereThis grammar is in Weak Chomsky normal form. In the original grammar, $C$ occurs only in $S\to AC$ and has the sole production $C\to BA$. Thus every use ofis replaced in $G^{\prime }$ by $S\to ABA$, while every later production is unchanged. Conversely, the ternary production can always be expanded into those two original steps. Therefore $G^{\prime }$ is equivalent to $G$ in the sense of an equivalent grammar.

The compressed initial production gives the leftmost derivationIt has $12$ steps, whereas part (b) gives $2\cdot 7-1=13$ for every derivation in Chomsky normal form. The Weak Chomsky normal form ternary rule has compressed exactly one pair of binary productions, so the derivation is strictly shorter as required.