steps to parse a string w. We are now in a position to justify this claim. The
algorithm we will describe here is called the CYK algorithm, after its originators
J. Cocke, D. H. Younger, and T. Kasami. The algorithm works only if the
grammar is in Chomsky normal form and succeeds by breaking one problem into
a sequence of smaller ones in the following way. Assume that we have a
grammar G = (V, T, S, P) in Chomsky normal form and a string
w = a 1 a 2 …a n .
We define substrings
w ij = a i …a j .
and subsets of V
Clearly, w L (G) if and only if S V 1n .
To compute V ij , observe that A V ii if and only if G contains a production A
→ a i . Therefore, V ii can be computed for all 1 ≤ i ≤ n by inspection of w and the
productions of the grammar. To continue, notice that for j > i, A derives w ij if and
only if there is a production A → BC, with
and
for some k
with i ≤ k, k < j. In other words,
An inspection of the indices in (6.8) shows that it can be used to compute all the
V ij if we proceed in the sequence
1. Compute V 11 , V 22 ,…,V nn ;
2. Compute V 12 , V 23 ,…,V n – i,n ,
3. Compute V 13 , V 24 , V n – 2,n ,
and so on.
Example 6.11