Introduction
Given a grammar and a string, is the string in the language? Trying derivations blindly can take forever. The CYK algorithm (named after Cocke, Younger and Kasami) answers the question for any context-free grammar in time proportional to n³, using dynamic programming. It is the clearest example of how grammars can be parsed systematically, and it also shows how the string is built.
How it works
CYK needs the grammar in Chomsky normal form (CNF), where every rule is one of:
- A → BC, a variable becomes exactly two variables, or
- A → a, a variable becomes exactly one terminal.
Every context-free grammar can be converted to CNF, keeping its language (apart from ε). With CNF, a variable produces a string of length 1 only through a terminal rule, and a longer string only by splitting it into two non-empty parts.
CYK fills a table whose cell (i, length) holds every variable that generates the substring starting at position i with that length:
- Length 1: put A in the cell when there is a rule A → c for that symbol.
- Longer substrings: for each way of splitting the substring into a left part and a right part, and each rule A → BC, put A in the cell if B is in the left part's cell and C in the right part's.
- The string is in the language if the start variable is in the cell for the whole string.
Because shorter substrings are always filled first, every cell a rule needs is ready when it is used. There are about n² cells and up to n splits each, hence O(n³) steps for a fixed grammar.
The CNF grammar used below generates aⁿbⁿ for n ≥ 1: S → AB | AC, C → SB, A → a, B → b. Here C means "an S followed by b", which is how CNF breaks the longer rule S → aSb into rules with two variables.
Syntax
table[(i, 1)] = {A for A, body in rules if body == word[i]}
for length in range(2, n + 1):
for i in range(n - length + 1):
for split in range(1, length):
left, right = table[(i, split)], table[(i + split, length - split)]
# add A for each rule A → BC with B in left and C in right
Example
rules = [("S", ("A", "B")), ("S", ("A", "C")), ("C", ("S", "B")), ("A", "a"), ("B", "b")]
def cyk(word):
n = len(word)
table = {}
for i, c in enumerate(word):
table[(i, 1)] = {head for head, body in rules if body == c}
for length in range(2, n + 1):
for i in range(n - length + 1):
cell = set()
for split in range(1, length):
left, right = table[(i, split)], table[(i + split, length - split)]
for head, body in rules:
if isinstance(body, tuple) and body[0] in left and body[1] in right:
cell.add(head)
table[(i, length)] = cell
return table
for word in ["aabb", "aab"]:
table = cyk(word)
n = len(word)
for length in range(1, n + 1):
row = ["{" + ",".join(sorted(table[(i, length)])) + "}" for i in range(n - length + 1)]
print(f"length {length}:", " ".join(row))
print(word, "accepted" if "S" in table[(0, n)] else "rejected")Line by line
- The rules are stored as pairs (head, body); a two-variable body is a tuple and a terminal body is a string.
- Row
length 1holds A for each a and B for each b. - In row
length 2, only the middleabgets S, through S → AB. - In row
length 3,abbgets C through C → SB, because S generatesaband B generatesb. - For
aabb, the top cell gets S through S → AC (a, then abb), so the string is accepted. Foraab, the top cell stays empty, so it is rejected.
Expected result
length 1: {A} {A} {B} {B}
length 2: {} {S} {}
length 3: {} {C}
length 4: {S}
aabb accepted
length 1: {A} {A} {B}
length 2: {} {S}
length 3: {}
aab rejected
In the real world
CYK is used in natural-language processing, where grammars are large and highly ambiguous, and its probabilistic version finds the most likely parse of a sentence. Similar table-filling parsers analyse RNA secondary structure in bioinformatics. Programming-language compilers usually use faster, specialised parsers (LL or LR) that handle restricted grammars in linear time.
Common mistakes
- Running CYK on a grammar that is not in CNF: long bodies or unit rules break the two-way split.
- Filling cells in the wrong order: every shorter substring must be done first.
- Missing a split: try every split point from 1 to length − 1.
- Checking the wrong cell: the answer is in the cell for position 0 and the full length.
Best practices
- Check that every rule has either two variables or one terminal before running CYK.
- Store each cell as a set, so that a variable is added once however many splits produce it.
- Print the table when debugging; it shows which part of the string each variable explains.
Summary
The CYK algorithm decides membership for a grammar in Chomsky normal form by dynamic programming. Each cell holds the variables generating one substring: length-1 cells come from terminal rules, and longer cells from rules A → BC over every split. The string is accepted when the start variable appears in the top cell, after O(n³) work.
Quick check
Key takeaways
- In Chomsky normal form, a variable generates a substring either directly (one terminal) or by splitting it in two.
- CYK fills the table shortest substrings first; each cell checks every split.
- The string is in the language when the start variable is in the cell for the whole string.
Practice problems for this lesson
My notes
Write down what you want to remember from this lesson. Notes are saved on this device as you type, and appear on your dashboard.