Revision as of 10:30, 20 February 2010 edit Hermel (talk \| contribs) Extended confirmed users, Pending changes reviewers 2,052 edits m →Parsing non-CNF context-free grammars: avoid reusing notation that has been used to denote smth else before ← Previous edit		Revision as of 10:33, 20 February 2010 edit undo Hermel (talk \| contribs) Extended confirmed users, Pending changes reviewers 2,052 edits m →Parsing non-CNF context-free grammars: symbol n was already in use to denote smth else Next edit →
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>n</math>~~''g'' to denote the size of the original grammar, the size blow-up in the worst case may range from <math>ng^2</math> to <math>2^{2 ng}</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===

CYK algorithm: Difference between revisions