CYK algorithm: Difference between revisions

Content deleted Content added
improved section after lede
Line 13:
}}</ref>
 
TheIn the [[theory of computation]], the importance of the CYK algorithm stems from the fact that it constructively proves that theit is [[membershipdecision problem|decidable]] (question concerning whether a given [[string (computer science)|string]] isbelongs anto element of athe [[Formalformal language]]) fordescribed context-freeby languagesa isgiven [[decisioncontext-free problem|decidablegrammar]] (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''.