172 Example 6.11 Chapter 6 SIMPLIFICATION OF CONTEXT-FREE GRAMMARS AND NORMAL FORMS Determine whether the string w = aabbb is in the language generated by the grammar S → AB, A -> BB|a, B→ AB|b. First note that w11 = a, so V11 is the set of all variables that immedi ately derive a, that is, V₁₁ = {A}. Since w22 = a, we also have V22 = {A} and, similarly, V₁₁ = {A}, V22 = {A}, V33 = {B}, V44 = {B}, V55 = {B}. V11 Now we use (6.8) to get V12 {A ABC, B E V11, C E V22}. = Since V₁₁ = {A} and V22 = {A}, the set consists of all variables that occur on the left side of a production whose right side is AA. Since there are none, V12 is empty. Next, V23 = {A: A → BC, B E V22, CE V33}, so the required right side is AB, and we have V23 = {S, B}. A straightfor- ward argument along these lines then gives V12 = Ø, V23 = {S, B}, V34 = {A}, V45 = {A}, V13 = {S, B}, V24 = {A}, V35 = {S, B}, V14 = {A}, V25 = {S, B}, V15 = {S, B}, so that wEL (G). The CYK algorithm, as described here, determines membership for any language generated by a grammar in Chomsky normal form. With some additions to keep track of how the elements of Vij are derived, it can be converted into a parsing method. To see that the CYK membership algo- rithm requires O (n³) steps, notice that exactly n (n+1)/2 sets of Vij have to be computed. Each involves the evaluation of at most n terms in (6.8), so the claimed result follows. EXERCISES Use the CYK algorithm to determine whether the strings aabb, aabba, and abbbb are in the language generated by the grammar in Example 6.11. 6.3 A MEMBERSHIP ALGORITHM FOR CONTEXT-FREE GRAMMARS* 173 14 Use the CYK method to determine if the string w = aaabbbbab is in the language generated by the grammar S→ aSblb.