Chomsky Normal Form and the CYK Table

The Cocke–Younger–Kasami algorithm decides membership in any context-free language in time O(n³) on a grammar in Chomsky normal form. The cubic bound comes from the normal form, not from the algorithm’s cleverness: once every rule has at most two symbols on its right, a derivation step combines exactly two adjacent pieces, and a table over contiguous substrings is enough to record every combination.

The normal form, rule by rule

A grammar is in Chomsky normal form when every production is one of

A → BC      A → a      S → ε

where A, B, C are nonterminals, a is a terminal, and the ε-rule is permitted only for the start symbol and only when ε is in the language. No rule has more than two symbols on the right, no rule mixes terminals and nonterminals, and no rule has a single nonterminal on the right.

The conversion is a fixed sequence of four eliminations, and each preserves the generated language exactly. Sizes grow, but only polynomially.

1. Eliminate the start symbol from right sides. Add a fresh nonterminal S₀ with rule S₀ → S. If ε ∈ L(G), also add S₀ → ε. Now S appears only as a left side or as the root, and the ε-rule can be confined to S₀ in the last step.

2. Eliminate ε-productions. A nonterminal is nullable if it derives ε. Compute the nullable set by iterating to a fixed point: A is nullable if some rule A → α has every symbol of α nullable. Then for each rule, generate the variants obtained by optionally deleting each nullable symbol from the right side, except that a rule that becomes empty is dropped. The number of variants for a right side of length k with j nullable positions is 2ʲ, so a rule can expand exponentially in its own length, though the length is fixed by the grammar. The one exception is the start symbol: keep S₀ → ε if needed.

3. Eliminate unit productions. A unit production is A → B for nonterminals A, B. Compute the transitive closure of the unit relation, then for every pair (A, B) with A ⇒* B by units alone and every non-unit rule B → β, add A → β. Drop all unit rules. The closure is computable by repeated squaring or by graph reachability over at most |V|² pairs.

4. Split long right sides and isolate terminals. For each rule A → X₁X₂…Xₖ with k ≥ 3, introduce fresh nonterminals and replace it with a chain:

A → X₁ Z₁,   Z₁ → X₂ Z₂,   …,   Z_{k−2} → X_{k−1} X_k

For each remaining rule containing a terminal a mixed with nonterminals, add a fresh nonterminal Tₐ with rule Tₐ → a and replace every occurrence of a in that context by Tₐ. Rules that are already A → a or A → BC are left alone.

The result has O(|G|) nonterminals and O(|G|) rules, where |G| counts the original symbols plus rule lengths. The doubling in step 2 is the only superlinear growth, and it is bounded by 2^k for the longest right side, which is a constant of the grammar.

Why the table is indexed by substrings

CYK fills a triangular table. Let w = w₁w₂…wₙ and let T[i][j] be the set of nonterminals that derive the substring wᵢ…wⱼ. The base case is length 1: T[i][i] contains every A with rule A → wᵢ. The recurrence for a longer span splits it at every interior position k:

T[i][j] = { A : A → BC ∈ R, B ∈ T[i][k], C ∈ T[k+1][j], i ≤ k < j }

This works because a binary rule’s two children derive adjacent, contiguous pieces. If a rule could have three symbols on the right, the recurrence would need to enumerate pairs of split points and a three-dimensional inner loop, and the cost would rise to O(n⁴) or worse. Chomsky normal form is what collapses the split to a single index.

The order of evaluation is by increasing span length, since every entry of length ℓ depends only on entries of length less than ℓ. A span of length ℓ has ℓ − 1 split points, and there are n − ℓ + 1 spans of that length, so the total number of split examinations is

Σ_{ℓ=1}^{n} (n − ℓ + 1)(ℓ − 1) = O(n³)

and each examination costs at most |R| lookups, giving O(n³·|R|). Memory is O(n²·|V|) for the table, or O(n²) bits if each cell is a bitset over nonterminals.

The algorithm answers membership by checking whether S ∈ T[1][n]. It does not build a tree. To recover a parse, each cell must also record a back-pointer — the rule and split point that first populated the entry — and reconstruction walks those pointers from the root. If a cell can be populated several ways, the table holds one witness and the grammar may be ambiguous, but the membership answer is unaffected.

A complete implementation

def cyk(grammar, start, word):
    """grammar: dict A -> list of right sides, each a tuple of 1 or 2 symbols.
    Symbols that are not keys of `grammar` are terminals."""
    n = len(word)
    if n == 0:
        return ('',) in grammar.get(start, [])

    table = [[set() for _ in range(n)] for _ in range(n)]
    back = {}

    # length-1 spans: terminal rules A -> a
    for i, ch in enumerate(word):
        for lhs, rhs_list in grammar.items():
            for rhs in rhs_list:
                if len(rhs) == 1 and rhs[0] == ch:
                    table[i][i].add(lhs)
                    back.setdefault((i, i, lhs), (rhs, None))

    # longer spans, shortest first
    for length in range(2, n + 1):
        for i in range(0, n - length + 1):
            j = i + length - 1
            for k in range(i, j):                    # split point
                left, right = table[i][k], table[k + 1][j]
                if not left or not right:
                    continue
                for lhs, rhs_list in grammar.items():
                    for rhs in rhs_list:
                        if (len(rhs) == 2 and rhs[0] in left
                                and rhs[1] in right):
                            table[i][j].add(lhs)
                            back.setdefault((i, j, lhs), (rhs, k))

    return start in table[0][n - 1]

The if not left or not right: continue line is not an optimisation detail; it skips splits where one side derives nothing, which is the common case in a sparse table. The back dictionary records the first derivation found for each (span, nonterminal) pair, which is enough to reconstruct one tree.

Two properties of the code matter for correctness. Terminals are recognised by absence from the grammar dictionary, which requires that no terminal symbol also be a nonterminal name — the definition of a grammar already forbids the overlap. And the loop over grammar.items() inside the split loop is the |R| factor; precomputing an index from pairs (B, C) to the set of left sides reduces it to a hash lookup per split and removes the factor.

Where the cubic bound comes from and where it stops applying

The O(n³) bound is a property of general context-free recognition, and there are lower-bound and upper-bound results around it. Valiant’s algorithm reduces context-free recognition to Boolean matrix multiplication and achieves O(n^ω) for the matrix multiplication exponent ω, which is below 3 in the asymptotically best known algorithms but carries constants that make it impractical. Earley’s algorithm achieves O(n³) in general, O(n²) for unambiguous grammars, and O(n) for grammars that are deterministic with bounded lookahead. The practical parser generators use LR or LL techniques that run in linear time on the deterministic subclass and reject grammars outside it.

CYK itself is the simplest of these and the least efficient on real inputs, but it has two properties the others lack. It handles arbitrary ambiguity without special cases, and it produces a table from which all parses can be enumerated, not just one. That makes it the standard choice for probabilistic parsing, where each cell stores the highest-probability derivation rather than a set of nonterminals, and the recurrence becomes a maximisation over split points — a Viterbi pass over the same triangular table.

The normal form also has a cost that is easy to overlook. Converting a grammar to Chomsky normal form can double the number of rules per nullable symbol and lengthen every derivation. A derivation in the original grammar of length d becomes one of length O(d) in the normal form, with the constant depending on the longest right side. The language is preserved; the derivation, and therefore the parse tree, is not. Tools that report trees must either keep the original grammar for reporting and use the normal form only for recognition, or carry a mapping from normal-form rules back to original rules. The mapping is mechanical — each introduced nonterminal stands for a suffix of one original right side — but it has to be maintained explicitly, and it is the usual source of bugs in parsers that transform grammars before parsing.

The cubic algorithm is also the reason context-free recognition is not used as a general-purpose matcher on long inputs. For an input of 10,000 tokens, n³ is 10¹² split examinations, which is thousands of seconds even at a few nanoseconds each. Linear-time parsers for deterministic grammars are the only way to process input at that scale, and the theory’s contribution is the boundary: the closure gaps and the undecidable questions mark which grammars those parsers cannot handle at all.