= 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$. Initialize
$$
T_{i,i}=\{A:A\to v_i\text{ is a production}\}.
$$
For increasing substring lengths, compute
$$
T_{i,j}=\bigcup_{k=i}^{j-1}
\{A:A\to BC,\ B\in T_{i,k},\ C\in T_{k+1,j}\}.
$$
Accept 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 $\epsilon$ immediately.
Back to article page
