Every language that has a context-free grammar can be recognized in at most 0(n 3 ) time for strings of length n. A simple way to do so, called the Cocke-Younger-Kasami (or CYK) algorithm is based on...

Every language that has a context-free grammar can be recognized in at most 0(n 3 ) time for strings of length n. A simple way to do so, called the Cocke-Younger-Kasami (or CYK) algorithm is based on dynamic programming. That is, given a string axa2 • • • a„, we construct an n-by-n table T such that Tij is the set of nonterminals that generate the substring a{ai+1 •••aj . If the underlying grammar is in CNF (see Exercise 4.4.8), then one table entry can be filled in in O(n) time, provided we fill the entries in the proper order: lowest value ofj-i first. Write an algorithm that correctly fills in the entries of the table, and show that your algorithm takes 0(n 3 ) time. Having filled in the table, how do you determine whether axa2 • • • an is in the language?