CYK - finding the closest word accepted Let's say I have a context-free grammar G and a string S. The normal CYK algorithm outputs that s can not be build using G. How would I find the closest String S' that can be build using G?
Your problem has been solved by Myers, Approximately Matching Context-Free Languages. A more recent algorithm, together with many relevant pointers, is Rajasekaran and Nicolae, An error correcting parser for context free grammars that takes less than cubic time.