Content deleted Content added
No edit summary |
|||
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 is contained in 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''.
| |||