CYK algorithm

In computer science, the Cocke–Younger–Kasami algorithm (alternatively called CYK, or CKY) is a parsing algorithm for context-free grammars published by Itiroo Sakai in 1961. The algorithm is named after some of its rediscoverers: John Cocke, Daniel Younger, Tadao Kasami, and Jacob T. Schwartz. It employs bottom-up parsing and dynamic programming. The standard version of CYK operates only on context-free grammars given in Chomsky normal form (CNF). However any context-free grammar may be algorithmically transformed into a CNF grammar expressing the same language (Sipser 1997). The importance of the CYK algorithm stems from its high efficiency in certain situations. Using big O notation, the worst case running time of CYK is O ( n 3 ⋅ | G | ) {\displaystyle {\mathcal {O}}\left(n^{3}\cdot \left|G\right|\right)} , where n {\displaystyle n} is the length of the parsed string and | G | {\displaystyle \left|G\right|} is the size of the CNF grammar G {\displaystyle G} (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.