Content deleted Content added
Renamed headers; "The Algorithm" -> "Standard form"; "Algorithm extensions" -> "Extensions" |
Rephrasing introduction |
||
Line 4:
The standard version of CYK recognizes languages defined by context-free grammars written in [[Chomsky normal form]] (CNF). Since any context-free grammar can be converted to CNF without too much difficulty, CYK can be used to recognize any context-free language.
The importance of the CYK algorithm stems form the fact that it constructively proves that [[membership problem]] for context-free languages is [[decision problem|decidable]] 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
==Standard form==
| |||