CYK algorithm

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. The dynamic programming algorithm requires the context-free grammar to be rendered into Chomsky normal form (CNF), because it tests for possibilities to split the current sequence into two smaller sequences. Any context-free grammar that does not generate the empty string can be represented in CNF using only production rules of the forms A → α {\displaystyle A\rightarrow \alpha } and A → B C {\displaystyle A\rightarrow BC} ; to allow for the empty string, one can explicitly allow S → ε {\displaystyle S\to \varepsilon } , where S {\displaystyle S} is the start symbol.