# CYK Algorithm

The CYK algorithm is a parsing algorithm for context-free grammars that uses bottom-up parsing and dynamic programming, with worst-case O(n^3) time complexity.

The Cocke-Younger-Kasami algorithm (CYK, or CKY) is a parsing algorithm for context-free grammars in computer science. It was first published by Itiroo Sakai in 1961 and later rediscovered by John Cocke, Daniel Younger, Tadao Kasami, and Jacob T. Schwartz, after whom it is named. The algorithm employs bottom-up parsing and dynamic programming to determine whether a given string can be generated by a given grammar, and it can also construct parse trees. Its worst-case running time is O(n^3 · |G|), where n is the length of the input string and |G| is the size of the grammar in Chomsky normal form, making it one of the most efficient parsing algorithms in terms of asymptotic worst-case complexity, though other algorithms may have better average performance in practice.

The CYK algorithm is widely used in [natural language processing](https://www.wikiprompt.org/wiki/natural-language-processing) and compiler design, where parsing is a fundamental step. It is particularly valued for its simplicity and guaranteed polynomial time, even for ambiguous grammars. The algorithm's reliance on dynamic programming allows it to handle all possible parses systematically, which is useful in applications such as syntax analysis in programming languages and syntactic parsing in [artificial intelligence](https://www.wikiprompt.org/wiki/artificial-intelligence) systems.

## Historical Background

The algorithm was first described by Itiroo Sakai in 1961, but it gained prominence through independent rediscoveries by John Cocke, Daniel Younger, and Tadao Kasami in the late 1960s. Jacob T. Schwartz also contributed to its development. The algorithm's name reflects these rediscoveries, with the acronym CYK derived from Cocke, Younger, and Kasami. The algorithm became a standard topic in computer science education, particularly in courses on formal languages and automata theory. Its development predates modern [machine learning](https://www.wikiprompt.org/wiki/machine-learning) and [neural network](https://www.wikiprompt.org/wiki/neural-network) approaches to parsing, but it remains relevant as a foundational technique.

## Standard Form: Chomsky Normal Form

The standard version of the CYK algorithm requires the context-free grammar to be in Chomsky normal form (CNF). In CNF, all production rules are of the form A → BC (where B and C are nonterminals) or A → α (where α is a terminal symbol). Additionally, the start symbol S may have a production S → ε to allow for the empty string. Any context-free grammar that does not generate the empty string can be transformed into an equivalent CNF grammar, as shown by Sipser in 1997. This transformation is algorithmic and preserves the language generated by the grammar. The CNF requirement simplifies the parsing process because it limits the ways in which a substring can be split into two parts, enabling efficient dynamic programming.

## Algorithm Description

The CYK algorithm operates by filling a three-dimensional table P[l, s, v], where l is the length of a substring, s is the starting position of that substring, and v is a nonterminal. The entry P[l, s, v] is set to true if the substring of length l starting at position s can be derived from nonterminal R_v. The algorithm proceeds in increasing order of substring length, starting with length 1.

For each substring of length 1, the algorithm checks unit productions of the form R_v → a_s, where a_s is the terminal at position s. For substrings of length 2 or greater, it considers every possible partition of the substring into two parts, and for each production A → BC, it checks whether the first part can be derived from B and the second part from C. If so, it marks the substring as derivable from A. The algorithm also maintains a backpointer table to allow reconstruction of parse trees.

At the end, the input string is recognized as a member of the language if P[n, 1, 1] is true, meaning the start symbol R_1 can derive the entire string. The backpointers can then be used to construct all possible parse trees.

## Example

Consider the following grammar in CNF:

- S → NP VP
- VP → VP PP
- VP → V NP
- VP → eats
- PP → P NP
- NP → Det N
- NP → she
- V → eats
- P → with
- N → fish
- Det → the

This grammar can parse sentences like "she eats the fish with the fork". The CYK algorithm would fill the table by first marking single-word substrings: "she" as NP, "eats" as VP or V, "the" as Det, "fish" as N, "with" as P, and "fork" as N. Then it combines substrings: "the fish" as NP (Det N), "eats the fish" as VP (V NP), and so on. Eventually, it determines that the entire sentence can be derived from S, and the backpointers reveal the parse tree structure.

## Applications and Significance

The CYK algorithm is significant in parsing theory and practice. It is used in [natural language processing](https://www.wikiprompt.org/wiki/natural-language-processing) for syntactic analysis, in compiler design for parsing programming languages, and in bioinformatics for RNA secondary structure prediction. Its worst-case time complexity of O(n^3) is optimal for general context-free grammar parsing in the worst case, though specialized algorithms like Earley parser can be more efficient for certain grammars. The algorithm's dynamic programming approach also makes it suitable for ambiguous grammars, as it can enumerate all possible parses. In modern [artificial intelligence](https://www.wikiprompt.org/wiki/artificial-intelligence), the CYK algorithm has been adapted for use in probabilistic context-free grammars and statistical parsing, where it computes the most likely parse tree given a probability distribution over productions.

## Limitations and Extensions

One limitation of the standard CYK algorithm is its requirement for CNF, which can increase the size of the grammar and affect efficiency. Extensions exist for grammars that are not in CNF, such as the Earley algorithm, which handles arbitrary context-free grammars directly. Additionally, the CYK algorithm has been extended to handle weighted grammars and probabilistic grammars, where each production has a weight or probability, and the goal is to find the parse with the maximum weight or probability. These extensions are used in [speech recognition](https://www.wikiprompt.org/wiki/speech-recognition) and [machine translation](https://www.wikiprompt.org/wiki/machine-translation). The algorithm also forms the basis for more advanced parsing techniques in [deep learning](https://www.wikiprompt.org/wiki/deep-learning)-based models, though those often use [neural network](https://www.wikiprompt.org/wiki/neural-network) approaches rather than explicit grammar rules.

---
Source: https://www.wikiprompt.org/wiki/cky-algorithm
License: CC BY-SA 4.0 (https://creativecommons.org/licenses/by-sa/4.0/)
Last updated: 2026-09-13T03:59:47.685018+00:00