Past exam of the mathematics course of the University of Cambridge / 2019 / ii / Paper 3 / 4H (Automata and 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. Under this strict convention there is no epsilon production, so such a grammar cannot generate the empty word. Conversion of an arbitrary grammar therefore givesIf $ϵ\notin \mathcal{L}(G)$, the two languages are equal. An alternative extended convention permits the exceptional start production $S_0\to ϵ$; under that convention conversion preserves the whole language.

Use the CYK algorithm. For a nonempty input word $v=v_1\cdots v_n$, let $T_{i,j}$ be the set of nonterminals that derive the substring $v_i\cdots v_j$. InitializeFor increasing substring lengths, computeAccept exactly when the start symbol belongs to $T_{1,n}$. The proof is a mathematical induction on substring length: a one-letter derivation uses a terminal production, while every longer parse tree has a root production $A\to BC$ whose two subtrees yield two adjacent nonempty substrings. The recurrence considers every possible split point and therefore finds exactly all possible roots. For a fixed grammar the algorithm uses $O(n^3)$ time. Under the strict form in part (a), it rejects $ϵ$ immediately.

Introduce nonterminals for the terminals and one for the pair $bb$:Because the original start symbol occurs on a right-hand side, take a fresh start symbol $S_0$. After eliminating the unit production $S\to T$, one grammar in Chomsky normal form isThe original grammar generates exactlyThe displayed grammar generates the same set: $AS$ adds an $a$ on the left, $SU$ adds one $bb$ pair on the right, and $CC$ terminates the derivation with $cc$. Since the original grammar does not generate $ϵ$,