An Introduction to Formal Languages and Automata, 7th Edition

6.3 A MEMBERSHIP ALGORITHM FOR CONTEXT-FREE GRAMMARS*

In Section 5.2, we claim, without any elaboration, that membership and parsing algorithms for context-free grammars exist that require approximately |w|³ 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\cdots a_n.$$

We define substrings

$$w_{ij}=a_i\cdots a_j,$$

and subsets of V

$$V_{ij}=\left\{A\in V:A\stackrel{\ast }{\Rightarrow }{w}_{ij}\right\}.$$

Clearly, w ∈ L(G) if ...