CYK algorithm: Difference between revisions

Revision as of 07:27, 9 February 2011

Revision as of 09:27, 18 February 2011

Line 1:

The '''Cocke–Younger–Kasami (CYK) algorithm''' (alternatively called '''CKY''') determines whetheris a [[parsing]] [[algorithm]] for [[context-free grammar]]s. It employs [[bottom-up parsing]] and [[dynamic programming]].

[[string (computer science)|string]] can be generated by a given [[context-free grammar]] and, if so, how it can be generated. This is known as [[parsing]] the string. The algorithm employs [[bottom-up parsing]] and [[dynamic programming]].

The standard version of CYK operates only on context-free grammars given in [[Chomsky normal form]] (CNF). AnyHowever 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''. This makes it the most efficient parsing algorithm in terms of worst-case [[asymptotic complexity]], although other algorithms exist with better average running time in many practical scenarios.

In the [[theory of computation]], the importance of the CYK algorithm stems from the fact that it constructively proves that it is [[decision problem|decidable]] whether a given [[string (computer science)|string]] belongs to the [[formal language]] described by a given [[context-free grammar]], 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''.

==Standard form==