The standard version of CYK can only recognize languages defined by contextfree grammars in Chomsky Normal Form (CNF). However, since any contextfree grammar can be converted to CNF without too much difficulty, CYK can be used to recognize any contextfree 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 asymptotic time complexity of CYK is Θ(n^{3}), where n is the length of the parsed string. This makes it the most efficient (in those terms) algorithm for recognizing a contextfree 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 contextfree languages is decidable.
The CYK algorithm for the membership problem is as follows:
In informal terms, this algorithm considers every possible consecutive subsequence of the sequence of letters and sets P[i,j,k] to be true if the sequence of letters starting from i of length j can be generated from R_{k}. Once it has considered sequences of length 1, it goes on to sequences of length 2, and so on. For subsequences of length 2 and greater, it considers every possible partition of the subsequence into two halves, and checks to see if there is some production P > Q R such that Q matches the first half and R matches the second half. If so, it records P as matching the whole subsequence. Once this process is completed, the sentence is recognized by the grammar if the subsequence containing the entire string is matched by the start symbol.
It is simple to extend the above algorithm to not only determine if a sentence is in a language, but to also construct a parse tree, by storing parse tree nodes as elements of the array, instead of booleans. Since the grammars being recognized can be ambiguous, it is necessary to store a list of nodes (unless one wishes to only pick one possible parse treee); the end result is then a forest of possible parse trees.
It is also possible to extend the CYK algorithm to parse Probabilised Context Free Grammars[?] (PCFG).
Search Encyclopedia

Featured Article
