language generated by a grammar in Chomsky normal form. With some
additions to keep track of how the elements of V ij are derived, itcan be converted
into a parsing method. To see that the CYK membership algorithm requires O
(n3) steps, notice that exactly n (n +1) /2 sets of V ij have to be computed. Each
involves the evaluation of at most n terms in (6.8), so the claimed result follows.
EXERCISES
1. 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.
2. Use the CYK algorithm to find a parsing of the string aab, using the grammar
of Example 6.11.
3. Use the approach employed in Exercise 2 to show how the CYK membership
algorithm can be made into a parsing method.
4. Use the CYK method to determine if the string w = aaabbbbab is in the
language generated by the grammar S → aSb|b.
additions to keep track of how the elements of V ij are derived, itcan be converted
into a parsing method. To see that the CYK membership algorithm requires O
(n3) steps, notice that exactly n (n +1) /2 sets of V ij have to be computed. Each
involves the evaluation of at most n terms in (6.8), so the claimed result follows.
EXERCISES
1. 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.
2. Use the CYK algorithm to find a parsing of the string aab, using the grammar
of Example 6.11.
3. Use the approach employed in Exercise 2 to show how the CYK membership
algorithm can be made into a parsing method.
4. Use the CYK method to determine if the string w = aaabbbbab is in the
language generated by the grammar S → aSb|b.