ToolSphere
Back to all articles
student

CYK Algorithm Example with CNF Conversion

2026-11-0211 min read

Try it: free CYK Parser

Test a word with CYK and inspect the parse table and tree

Open →

The Cocke–Younger–Kasami (CYK) algorithm is one of the foundational parsing and membership-testing algorithms taught in university Theory of Computation and Compiler Design courses. Named after its independent discoverers John Cocke, Daniel Younger, and Tadao Kasami, CYK determines whether a given token sequence can be generated by a context-free grammar (CFG) in O(n³ · |G|) time, where n is the input length and |G| is the grammar size.

Unlike top-down parsers such as LL(1) or recursive-descent that require non-left-recursive, deterministic grammars, CYK works on any context-free grammar, including ambiguous and left-recursive grammars. The only requirement is that the grammar must first be in Chomsky Normal Form (CNF).

In this guide, we walk through the entire pipeline:

  1. Converting an arbitrary context-free grammar to Chomsky Normal Form step by step.
  2. The dynamic programming recurrence that defines every table cell.
  3. A complete worked CYK triangular table for the string baaba using a classic textbook CNF grammar.
  4. Extracting a valid parse tree from backpointers in the completed table.
  5. Tracing a rejected string (bbb) and comparing empty cells.
  6. Parsing a converted grammar string (aabb).

You can follow along interactively using our browser-based CYK parser and CFG to CNF converter.


Why CYK Requires Chomsky Normal Form (CNF)

In an arbitrary context-free grammar, productions can have empty right-hand sides (A → ε), single nonterminal unit productions (A → B), or arbitrary mixtures of terminals and nonterminals (A → a B c D). These flexible rules create two major challenges for algorithms:

  • Unit loops: Cycles like A → B and B → A allow infinite derivations without consuming any input tokens.
  • Empty derivations: Rules like A → ε allow nonterminals to vanish silently, obscuring which span of input tokens corresponds to which subtree.

Chomsky Normal Form eliminates both issues by enforcing a strict structural invariant. In strict CNF, every production rule must match one of two shapes:

  1. A → a: A single nonterminal derives exactly one terminal token.
  2. A → B C: A single nonterminal derives exactly two nonterminal variables.
  3. (Optional) S₀ → ε: Allowed only for the start symbol when the language includes the empty string, provided S₀ never appears on any right-hand side.

This restriction is what makes the CYK dynamic programming recurrence possible:

  • A single token (span of length 1) can only be produced by a terminal production A → a.
  • A substring of length l ≥ 2 cannot be produced by a terminal rule. It can only be produced by a binary rule A → B C, which cleanly partitions the span into a nonempty left piece of length k (1 ≤ k < l) derived by B, and a nonempty right piece of length l − k derived by C.
  • Because both k ≥ 1 and l − k ≥ 1, both subproblems are strictly smaller than l. Working bottom-up from length 1 to length n guarantees that every subproblem needed to solve span l has already been computed.

Part 1: Converting a Context-Free Grammar to CNF First

Before running CYK on a general grammar, we must normalize it. Consider the standard language of balanced symbols L = { aⁿbⁿ | n ≥ 0 }:

S -> a S b | ε

This grammar is not in CNF because S -> a S b contains three symbols (mixing terminals and nonterminals), and S -> ε is an empty production. The conversion follows five standard stages:

Stage 1: Add a fresh start symbol

Introduce a new start variable S₀ with a single production pointing to the original start symbol:

S0 -> S
S  -> a S b | ε

The fresh start symbol guarantees that the start variable never appears on any right-hand side, preserving correct semantics if the empty string is accepted.

Stage 2: Eliminate epsilon (ε) productions

A nonterminal is nullable if it can derive ε in one or more steps. Here:

  • S derives ε directly, so S is nullable.
  • S₀ derives S, so S₀ is nullable.

For every production containing nullable symbols on its right-hand side, add versions where each nullable occurrence is independently included or omitted. Then delete all ε-rules except at the fresh start S₀:

S0 -> S | ε
S  -> a S b | a b

Notice that S -> a b was created by omitting nullable S from a S b. The production S -> ε is removed, while S0 -> ε is retained.

Stage 3: Eliminate unit rules

A unit rule is a production of the form A → B, where both sides are single nonterminals. Here, S0 -> S is a unit rule. To eliminate it, S₀ inherits all non-unit alternatives of S:

S0 -> ε | a S b | a b
S  -> a S b | a b

Stage 4: Split long right-hand sides

Productions with more than two symbols on the right-hand side must be broken into binary chains using fresh helper nonterminals (N, N1):

  • S -> a S b becomes S -> a N with N -> S b
  • S0 -> a S b becomes S0 -> a N1 with N1 -> S b

The grammar becomes:

S0 -> ε | a N1 | a b
S  -> a N | a b
N  -> S b
N1 -> S b

Stage 5: Isolate terminals in binary rules

Terminals that appear inside binary productions must be replaced with dedicated nonterminals. Introduce T → a and T1 → b:

  • Replace a N with T N
  • Replace a N1 with T N1
  • Replace a b with T T1
  • Replace S b with S T1

The completed Chomsky Normal Form grammar is:

S0 -> ε | T N1 | T T1
S  -> T N | T T1
N  -> S T1
N1 -> S T1
T  -> a
T1 -> b

Every production in this resulting grammar is either a single terminal, two nonterminals, or the start-only empty rule S0 -> ε. It generates the exact same language as the original grammar.


Part 2: The CYK Algorithm Recurrence

Let w = w₁ w₂ ... wₙ be an input string of length n. We construct a triangular table T where cell T[i, l] stores the set of nonterminals that derive the substring of length l starting at index i:

w[i ... i + l - 1] = wᵢ wᵢ₊₁ ... wᵢ₊ₗ₋₁

1. Base case: spans of length 1 (terminals)

For each token position i from 1 to n:

T[i, 1] = { A | A → wᵢ is a production in the grammar }

2. Inductive step: spans of length l from 2 to n

To determine which variables derive the substring of length l starting at i, partition the span into two nonempty pieces at split offset k (where 1 ≤ k < l):

  • Left piece: length k starting at index i, covered by nonterminals in T[i, k].
  • Right piece: length l − k starting at index i + k, covered by nonterminals in T[i + k, l − k].

For every split point k, if nonterminal B is in the left cell, nonterminal C is in the right cell, and the grammar contains a production A → B C, then nonterminal A derives the combined substring:

T[i, l] = ∪ (for k = 1 to l - 1) { A | A → B C where B ∈ T[i, k] and C ∈ T[i + k, l - k] }

3. Acceptance condition

The string w is accepted if and only if the grammar's start symbol S belongs to the full-span cell:

S ∈ T[1, n]

If the input is empty (n = 0), it is accepted if and only if the grammar contains the rule S → ε.


Part 3: Complete Worked Example on baaba

We now execute CYK on the classic textbook grammar:

S -> A B | B C
A -> B A | a
B -> C C | b
C -> A B | a

Notice that this grammar is already in strict CNF:

  • Nonterminals: S, A, B, C
  • Terminals: a, b
  • Start symbol: S

Target input string: baaba (length n = 5).

Position 1 2 3 4 5
Token b a a b a

The Full Triangular Table

The completed 15-cell triangular parse table generated by the CYK algorithm is:

Span Length (l) Start 1 (b...) Start 2 (a...) Start 3 (a...) Start 4 (b...) Start 5 (a...)
l = 1 (1 token) {B} {A, C} {A, C} {B} {A, C}
l = 2 (2 tokens) {A, S} {B} {C, S} {A, S} —
l = 3 (3 tokens) ∅ {B} {B} — —
l = 4 (4 tokens) ∅ {A, C, S} — — —
l = 5 (5 tokens) {A, C, S} — — — —

Note: The symbol ∅ represents an empty set (a valid substring span that cannot be generated by any nonterminal). An em dash (—) represents cells outside the triangular boundary.


Detailed Step-by-Step Derivation of Every Cell

Row 1: Span Length l = 1 (Base Row)

We inspect which nonterminals produce each individual token:

  • T[1, 1] (token at pos 1: b):
    Production B -> b matches ⇒ T[1, 1] = {B}
  • T[2, 1] (token at pos 2: a):
    Productions A -> a and C -> a match ⇒ T[2, 1] = {A, C}
  • T[3, 1] (token at pos 3: a):
    Productions A -> a and C -> a match ⇒ T[3, 1] = {A, C}
  • T[4, 1] (token at pos 4: b):
    Production B -> b matches ⇒ T[4, 1] = {B}
  • T[5, 1] (token at pos 5: a):
    Productions A -> a and C -> a match ⇒ T[5, 1] = {A, C}

Tip for exams: Never discard secondary parent nonterminals. Both A and C generate a. If you omit C from T[2, 1], binary pairings in later rows like S -> B C will fail, resulting in a false rejection.


Row 2: Span Length l = 2 (Two-Token Substrings)

For length 2, there is only one split point: k = 1.

Cell T[1, 2] for substring "ba" (positions 1–2):

  • Split after pos 1: Left = T[1, 1] = {B}, Right = T[2, 1] = {A, C}.
  • Possible pairs (Left, Right): (B, A), (B, C).
  • Matching binary rules:
    • A -> B A matches (B, A) ⇒ add A
    • S -> B C matches (B, C) ⇒ add S
  • T[1, 2] = {A, S}

Cell T[2, 2] for substring "aa" (positions 2–3):

  • Split after pos 2: Left = T[2, 1] = {A, C}, Right = T[3, 1] = {A, C}.
  • Possible pairs: (A, A), (A, C), (C, A), (C, C).
  • Matching binary rules:
    • B -> C C matches (C, C) ⇒ add B
  • T[2, 2] = {B}

Cell T[3, 2] for substring "ab" (positions 3–4):

  • Split after pos 3: Left = T[3, 1] = {A, C}, Right = T[4, 1] = {B}.
  • Possible pairs: (A, B), (C, B).
  • Matching binary rules:
    • S -> A B matches (A, B) ⇒ add S
    • C -> A B matches (A, B) ⇒ add C
  • T[3, 2] = {C, S}

Cell T[4, 2] for substring "ba" (positions 4–5):

  • Split after pos 4: Left = T[4, 1] = {B}, Right = T[5, 1] = {A, C}.
  • Possible pairs: (B, A), (B, C).
  • Matching binary rules:
    • A -> B A matches (B, A) ⇒ add A
    • S -> B C matches (B, C) ⇒ add S
  • T[4, 2] = {A, S}

Row 3: Span Length l = 3 (Three-Token Substrings)

Here we evaluate two possible split points: k = 1 and k = 2.

Cell T[1, 3] for substring "baa" (positions 1–3):

  • Split k = 1 (split after pos 1: b + aa):
    Left = T[1, 1] = {B}, Right = T[2, 2] = {B}.
    Pair: (B, B). No production has right-hand side B B.
  • Split k = 2 (split after pos 2: ba + a):
    Left = T[1, 2] = {A, S}, Right = T[3, 1] = {A, C}.
    Pairs: (A, A), (A, C), (S, A), (S, C). No production matches these pairs.
  • Result: T[1, 3] = ∅

Cell T[2, 3] for substring "aab" (positions 2–4):

  • Split k = 1 (split after pos 2: a + ab):
    Left = T[2, 1] = {A, C}, Right = T[3, 2] = {C, S}.
    Pairs: (A, C), (A, S), (C, C), (C, S).
    Rule B -> C C matches (C, C) ⇒ add B.
  • Split k = 2 (split after pos 3: aa + b):
    Left = T[2, 2] = {B}, Right = T[4, 1] = {B}.
    Pair: (B, B). No matching rule.
  • Result: T[2, 3] = {B}

Cell T[3, 3] for substring "aba" (positions 3–5):

  • Split k = 1 (split after pos 3: a + ba):
    Left = T[3, 1] = {A, C}, Right = T[4, 2] = {A, S}.
    Pairs: (A, A), (A, S), (C, A), (C, S). No matching rule.
  • Split k = 2 (split after pos 4: ab + a):
    Left = T[3, 2] = {C, S}, Right = T[5, 1] = {A, C}.
    Pairs: (C, A), (C, C), (S, A), (S, C).
    Rule B -> C C matches (C, C) ⇒ add B.
  • Result: T[3, 3] = {B}

Row 4: Span Length l = 4 (Four-Token Substrings)

Here we evaluate three split points: k = 1, k = 2, and k = 3.

Cell T[1, 4] for substring "baab" (positions 1–4):

  • Split k = 1 (b + aab): Left = T[1, 1] = {B}, Right = T[2, 3] = {B}. Pair (B, B) ⇒ no match.
  • Split k = 2 (ba + ab): Left = T[1, 2] = {A, S}, Right = T[3, 2] = {C, S}. Pairs (A, C), (A, S), (S, C), (S, S) ⇒ no match.
  • Split k = 3 (baa + b): Left = T[1, 3] = ∅, Right = T[4, 1] = {B}. Left is empty ⇒ no pairs.
  • Result: T[1, 4] = ∅

Cell T[2, 4] for substring "aaba" (positions 2–5):

  • Split k = 1 (a + aba):
    Left = T[2, 1] = {A, C}, Right = T[3, 3] = {B}.
    Pairs: (A, B), (C, B).
    Rules S -> A B and C -> A B match (A, B) ⇒ add S, C.
  • Split k = 2 (aa + ba):
    Left = T[2, 2] = {B}, Right = T[4, 2] = {A, S}.
    Pairs: (B, A), (B, S).
    Rule A -> B A matches (B, A) ⇒ add A.
  • Split k = 3 (aab + a):
    Left = T[2, 3] = {B}, Right = T[5, 1] = {A, C}.
    Pairs: (B, A), (B, C).
    Rule A -> B A matches (B, A) ⇒ add A.
    Rule S -> B C matches (B, C) ⇒ add S.
  • Combining all splits: T[2, 4] = {A, C, S}

Row 5: Span Length l = 5 (The Complete String "baaba")

We test all four possible splits across the entire input:

Split k = 1 (positions 1 + 2–5, b + aaba):

  • Left = T[1, 1] = {B}
  • Right = T[2, 4] = {A, C, S}
  • Pairs: (B, A), (B, C), (B, S)
  • Matching productions:
    • A -> B A matches (B, A) ⇒ add A
    • S -> B C matches (B, C) ⇒ add S

Split k = 2 (positions 1–2 + 3–5, ba + aba):

  • Left = T[1, 2] = {A, S}
  • Right = T[3, 3] = {B}
  • Pairs: (A, B), (S, B)
  • Matching productions:
    • S -> A B matches (A, B) ⇒ add S
    • C -> A B matches (A, B) ⇒ add C

Split k = 3 (positions 1–3 + 4–5, baa + ba):

  • Left = T[1, 3] = ∅, Right = T[4, 2] = {A, S} ⇒ no pairs possible.

Split k = 4 (positions 1–4 + 5, baab + a):

  • Left = T[1, 4] = ∅, Right = T[5, 1] = {A, C} ⇒ no pairs possible.

Final Cell and Membership Verdict

Taking the union of all four split evaluations:

T[1, 5] = {A, C, S}

Since the grammar's start symbol S belongs to T[1, 5], the string baaba is ACCEPTED.

The fact that nonterminals A and C are also present in T[1, 5] is normal; it simply means those variables also happen to derive the complete string. Acceptance strictly requires that the designated start symbol S is in the root cell.


Part 4: Reconstructing a Parse Tree from the Table

CYK is not limited to answering yes or no. By tracing back which split k and which binary production justified the start symbol, we can recover an explicit parse tree:

  1. In cell T[1, 5], start symbol S was formed at split k = 1 using the rule S → B C:
    • Left subtree: variable B over span [1, 1]
    • Right subtree: variable C over span [2, 4]
  2. In cell T[1, 1], B derives terminal b using B → b.
  3. In cell T[2, 4], variable C was formed at split k = 1 (position 2) using rule C → A B:
    • Left subtree: A over span [2, 1]
    • Right subtree: B over span [3, 3]
  4. In cell T[2, 1], A derives terminal a using A → a.
  5. In cell T[3, 3], variable B was formed at split k = 2 (position 4) using rule B → C C:
    • Left subtree: C over span [3, 2]
    • Right subtree: C over span [5, 1]
  6. In cell T[3, 2], variable C was formed at split k = 1 (position 3) using rule C → A B:
    • Left: A over [3, 1] deriving a (A → a)
    • Right: B over [4, 1] deriving b (B → b)
  7. In cell T[5, 1], C derives terminal a using C → a.

Writing this as an indented parse tree:

S
├── B -> b
└── C
    ├── A -> a
    └── B
        ├── C
        │   ├── A -> a
        │   └── B -> b
        └── C -> a

Reading the leaf nodes from left to right yields: b · a · a · b · a, confirming that the parse tree generates the exact target word.


Part 5: Tracing a Rejected String: bbb

To understand rejection, run the same grammar on the string bbb (length n = 3):

Span Length Start 1 (b) Start 2 (b) Start 3 (b)
l = 1 {B} {B} {B}
l = 2 ∅ ∅ —
l = 3 ∅ — —
  • Row 1: Every b is derived by B (B → b).
  • Row 2: For span [1, 2], Left = {B} and Right = {B}. The only pair is (B, B). But the grammar has no production producing B B! Thus T[1, 2] = ∅ and T[2, 2] = ∅.
  • Row 3: Both splits pair with an empty set, yielding T[1, 3] = ∅.

Because S ∉ T[1, 3], the string bbb is REJECTED.

Notice that empty cells (∅) do not cause an algorithm crash or immediate abort. The dynamic program computes each cell systematically; a string is rejected only when the start symbol does not appear in the final top cell.


Part 6: Parsing with the Converted Balanced Grammar (aabb)

Now let us verify the grammar we converted in Part 1:

S0 -> ε | T N1 | T T1
S  -> T N | T T1
N  -> S T1
N1 -> S T1
T  -> a
T1 -> b

Target input: aabb (length n = 4).

Span Length Start 1 (a) Start 2 (a) Start 3 (b) Start 4 (b)
l = 1 {T} {T} {T1} {T1}
l = 2 ∅ {S, S0} ∅ —
l = 3 ∅ {N, N1} — —
l = 4 {S, S0} — — —
  1. Row 1: Each a is generated by T, and each b is generated by T1.
  2. Row 2:
    • T[2, 2] represents substring ab (pos 2–3). Left = {T}, Right = {T1}. The pair (T, T1) matches productions S -> T T1 and S0 -> T T1 ⇒ {S, S0}.
    • Spans aa and bb have no matching binary rules ⇒ ∅.
  3. Row 3:
    • T[2, 3] represents substring abb (pos 2–4). Split at pos 3 pairs T[2, 2] = {S, S0} with T[4, 1] = {T1}. The pair (S, T1) matches N -> S T1 and N1 -> S T1 ⇒ {N, N1}.
  4. Row 4:
    • T[1, 4] represents aabb. Split at pos 1 pairs T[1, 1] = {T} with T[2, 3] = {N, N1}. The pairs (T, N) and (T, N1) match S -> T N and S0 -> T N1 ⇒ {S, S0}.

Because the converted grammar's start symbol S₀ belongs to T[1, 4], the word aabb is ACCEPTED.


Computational Complexity Analysis

Metric Complexity Explanation
Table size O(n²) Total number of cells is n(n + 1) / 2.
Splits evaluated O(n³) A cell of span length l evaluates l − 1 split positions. Across the full table, the total number of split evaluations is (n³ − n) / 6.
Total time O(n³ · |P|) Each split checks left/right variable pairs against the grammar's binary production rules |P|.
Space O(n² · |V|) Each cell stores a subset of the nonterminal set V.

Compared to brute-force depth-first search (which can loop infinitely or run in O(|P|^n) exponential time on general CFGs), CYK guarantees polynomial-time parsing for any context-free grammar.


Common Homework and Exam Mistakes

  1. Forgetting to convert to Chomsky Normal Form: Trying to run CYK directly on a grammar with unit rules (A → B) or rules with three symbols (A → a B C) will yield incorrect table entries or infinite loops.
  2. Dropping secondary nonterminals: If both A and C derive a, you must include both in the base cell. Omitting one cascades errors upward through the entire triangle.
  3. Reversing production order: The production S -> B C requires nonterminal B in the left cell and C in the right cell. Finding C on the left and B on the right does not satisfy the rule.
  4. Stopping after the first matching split: Multiple split points can contribute different valid nonterminals to the same cell. You must evaluate all k from 1 to l − 1.
  5. Checking for the start symbol in the wrong place: Finding S in an intermediate cell like T[1, 2] does not mean the string is accepted. Acceptance is determined solely by the presence of S in the root cell T[1, n].

Frequently Asked Questions

What is the CYK algorithm used for?

The CYK algorithm is a dynamic programming membership algorithm that determines whether a string of tokens belongs to the language of a context-free grammar. It is widely used in computational linguistics, natural language processing (NLP), bioinformatics (RNA secondary structure prediction), and compiler theory.

Why does CYK require Chomsky Normal Form?

Chomsky Normal Form ensures that every production either produces a single terminal (for span length 1) or splits a span into two strictly smaller, nonempty sub-spans (for span length l ≥ 2). This guarantees a clean dynamic programming recurrence without infinite unit-rule loops or vanishing epsilon transitions.

How does CYK decide if a string is accepted or rejected?

A string of length n is accepted if and only if the grammar's designated start symbol S is present in the full-span table cell T[1, n]. If S is not in that cell, the string is rejected.

Can an intermediate cell in the CYK table be empty?

Yes. An empty cell (∅) simply indicates that no nonterminal in the grammar can derive that specific substring. Other splits may still derive the complete string, so an empty middle cell does not imply rejection.

How does CYK extract a parse tree?

When a nonterminal A is placed in cell T[i, l], the parser records which split point k and which production rule A → B C justified it. Once the table is complete, a recursive backpointer traversal starting from S in T[1, n] reconstructs the complete derivation tree.

How does CYK handle the empty string (ε)?

In strict CNF, the empty string is accepted if and only if the grammar contains the rule S₀ → ε for its start symbol. The triangular table is only built for strings of length n ≥ 1.

Can CYK handle ambiguous grammars?

Yes. Unlike LL and LR parsers that fail when given ambiguous grammars, CYK processes ambiguous grammars without issue. Multiple valid parse trees simply correspond to multiple successful splits in the table cells.

What is the difference between CYK and Earley parsing?

Earley's algorithm is an active chart-parsing algorithm that works directly on arbitrary context-free grammars without converting to CNF. However, both algorithms share an O(n³) worst-case time complexity, with CYK having a much simpler table structure.


Interactive Tools and Related Guides

For a related walkthrough, read Pushdown Automata Example: aⁿbⁿ Step by Step.

Looking for other tools?

Explore ToolSphere Homepage →