Content deleted Content added
give algorithm, runtime, possible extensions, theoretical significance |
No edit summary |
||
Line 1:
'''Cocke-Younger-Kasami algorithm''' (CYK) is an example of [[dynamic programming]]. Its purpose is to efficiently parse a string belonging to a [[context-free language]].
The standard version of CYK can only recognize languages defined by [[context-free grammar]]s in [[Chomsky Normal Form]] (CNF). However, since any context-free grammar can be converted to CNF without too much difficulty, CYK can be used to recognize any context-free language. It is also possible to extend the CYK algorithm to handle some grammars which are not in CNF, although at the cost of making the algorithm significantly harder to understand.
The worst case asympotic time complexity of CYK is O(n<sup>3</sup>), which makes it the most efficient (in those terms) algorithm for recognizing a context-free language. However, in many cases, other algorithms will give better performance.
The CYK algorithm is important theoretically, since it can be used to constructively prove that the membership problem for context-free languages is decidable.
The CYK algorithm is a type of [[active chart parsing]] (is this correct?).
The CYK algorithm for the membership problem is as follows:
| |||