context-free grammar

Every language that has a context-free grammar can be recognized in at most O(n3 ) 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 a1a2 …… an, we construct an n-by-n table T such that Tij is the set of nonterminals that generate the substring aiai+1 ….. aj . If the underlying grammar is in CNF (see Exercise 4.4.8), then one table entry can be lled in in O(n) time, provided we
Fill the entries in the proper order: lowest value of j i first. Write an algorithm that correctly Fills in the entries of the table, and show that your algorithm takes O(n3 ) time. Having Filled in the table, how do you determine whether a1a2 ….. an is in the language?