CYK algorithm

Cocke–Younger–Kasami algorithm (CYK)

Class	Parsing with context-free grammars
Data structure	String
Worst-case performance	${\displaystyle {\mathcal {O}}\left(n^{3}\cdot \left|G\right|\right)}$, where: ${\displaystyle n}$ is length of the string ${\displaystyle |G|}$ is the size of the CNF grammar

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.^[1][2] 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 ${\displaystyle {\mathcal {O}}\left(n^{3}\cdot \left|G\right|\right)}$, where ${\displaystyle n}$ is the length of the parsed string and ${\displaystyle \left|G\right|}$ is the size of the CNF grammar ${\displaystyle G}$ (Hopcroft & Ullman 1979, p. 140). This makes it one of the most efficient ^{[citation needed]} parsing algorithms in terms of worst-case asymptotic complexity, although other algorithms exist with better average running time in many practical scenarios.