Modify your algorithm of Exercise 4.4.9 so that it will find, for any string, the smallest number of insert, delete, and mutate errors (each error a single character) needed to turn the string into a...

Modify your algorithm of Exercise 4.4.9 so that it will find, for any string, the smallest number of insert, delete, and mutate errors (each error a single character) needed to turn the string into a string in the language of the underlying grammar.

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?