Content deleted Content added
Rephrasing |
typo |
||
Line 4:
The standard version of CYK operates on context-free grammars given in [[Chomsky normal form]] (CNF). Any context-free grammar may be written thusly.
The importance of the CYK algorithm stems from the fact that it constructively proves that the [[membership problem]] for context-free languages is [[decision problem|decidable]] (see also: [[theory of computation]]) and the fact that it does so quite efficiently.
The worst case [[asymptotic]] time complexity of CYK is [[Big O notation|Θ]](n<sup>3</sup>), where ''n'' is the length of the parsed string. This makes it one of the most efficient (in those terms) algorithms for recognizing general context-free languages. Specialized and faster algorithms exist for certain subsets of the context-free languages.
| |||