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

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.