Content deleted Content added
No edit summary |
→top: explicit ref. for complexity |
||
Line 3:
The standard version of CYK operates only on context-free grammars given in [[Chomsky normal form]] (CNF). However any context-free grammar may be transformed to a CNF grammar expressing the same language {{harv|Sipser|1997}}.
The importance of the CYK algorithm stems from its high efficiency in certain situations. 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'' {{harv|Hopcroft|Ullman|1979|p=140}}. This makes it one of the most efficient parsing algorithms in terms of worst-case [[asymptotic complexity]], although other algorithms exist with better average running time in many practical scenarios.
==Standard form==
| |||