CYK algorithm: Difference between revisions

Revision as of 23:39, 16 February 2010

Revision as of 10:25, 20 February 2010

Line 67:

===Parsing non-CNF context-free grammars===

It is also possible to extend the CYK algorithm to handle some context-free grammars which are not written in CNF; this may be done to improve performance, although at the cost of making the algorithm harder to understand.

As pointed out by Lange and Leiß (2009), the drawback of these transformations is that they can lead to an undesirable bloat in grammar size. Using <math>|G|</math> to denote the size of the original grammar <math>G</math>, the size blow-up in the worst case may range from <math>|G|^2</math> to <math>2^{2 |G|}</math>, depending on the used transformation algorithm. For the use in teaching, they propose a slight generalization of the CYK algorithm, "without compromising efficiency of the algorithm, clarity of its presentation, or simplicity of proofs" (Lange and Leiß 2009).

===Parsing weighted context-free grammars===