Show how, having filled in the table as in Exercise 4.4.9, we can in 0(n) time recover a parse tree for a\a2---an . Hint: modify the table so it records, for each nonterminal A in each table entry...

Show how, having filled in the table as in Exercise 4.4.9, we can in 0(n) time recover a parse tree for a\a2---an . Hint: modify the table so it records, for each nonterminal A in each table entry Tij: some pair of nonterminals in other table entries that justified putting A in Tij.

Exercise 4.4.9

Every language tha t 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. Tha t is, given a string axa2 • • • a„, we construct an n-by-n table T such tha t 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 tha t 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?