Past exam of the mathematics course of the University of Cambridge / 2019 / ii / Paper 3 / 4H / b / Solution

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.