CYK algorithm: Difference between revisions

Revision as of 07:02, 17 July 2010

Revision as of 08:13, 18 July 2010

Line 13:

}}</ref>

The importance of the CYK algorithm stems from the fact that it constructively proves that the [[membership problem]] (question concerning whether a [[string (computer science)|string]] is an element of a [[Formal language]]) for context-free languages is [[decision problem|decidable]] (see also: [[theory of computation]]) and the fact that it does so quite efficiently.

Using [[Landau symbol]]s, the [[Analysis of algorithms|worst case running time]] of CYK is <math>\Theta(n^3 \cdot |G|)</math>, where ''n'' is the length of the parsed string and ''|G|'' is the size of the CNF grammar ''G''.