CYK algorithm: Difference between revisions

Revision as of 10:27, 20 February 2010

Revision as of 10:30, 20 February 2010

Line 68:

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

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|n</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|n^2</math> to <math>2^{2 |G|n}</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===