Chapter 22 of 34

CYK Algorithm

Given a context-free grammar G and a string w, does G generate w? This is the membership problem for CFLs. For a DFA the answer is easy: just run the machine. For a grammar we cannot simply "try all derivations", because there may be infinitely many sentential forms to explore.

The CYK algorithm (named after Cocke, Younger and Kasami, who found it independently in the 1960s) answers the question in O(n3) time for a string of length n. It works bottom-up: first find which variables generate each single symbol, then each substring of length 2, then length 3, and so on, until we know which variables generate the whole string.

The CYK algorithm decides whether a string w of length n is generated by a context-free grammar in Chomsky Normal Form. It fills a triangular table where cell Xi,j holds every variable that derives the substring wi…wj. The string is in the language exactly when the start symbol is in X1,n.

CYK is a classic example of dynamic programming: the answer for a long substring is built from the stored answers for shorter ones. Every table in this chapter was computed by a program and cross-checked against an independent parser on all strings over {a, b} up to length 9.


Why the Grammar Must Be in CNF

In Chomsky Normal Form every production is A → BC or A → a. That gives us two clean facts:

  • A variable derives a single symbol a only through a production A → a.

  • A variable derives a longer string only through some A → BC, where B derives a non-empty prefix and C derives the rest. So the string splits into two non-empty pieces at some point k.

The second fact is the heart of CYK. To know whether A ⇒* wi…wj, we only need to look at every split point k and ask: is there a rule A → BC with B ⇒* wi…wk and C ⇒* wk+1…wj? Both pieces are shorter, so their answers are already in the table.

If your grammar is not in CNF, convert it first. (The empty string is handled separately: ε ∈ L(G) exactly when the original grammar has a nullable start symbol.)


The Algorithm

Input: CNF grammar G with start symbol S, string w = w1 w2 … wn  (n ≥ 1)

// length 1
for i = 1 to n:
    X[i,i] = { A : A → wi is a production }

// lengths 2 .. n
for len = 2 to n:
    for i = 1 to n − len + 1:
        j = i + len − 1
        X[i,j] = ∅
        for k = i to j − 1:                       // split: wi..wk | wk+1..wj
            for each production A → B C:
                if B ∈ X[i,k] and C ∈ X[k+1,j]:
                    add A to X[i,j]

accept  ⟺  S ∈ X[1,n]

We usually draw the table as a triangle, one row per substring length. The bottom row (length 1) has n cells; the top row (length n) has a single cell for the whole string.

Cost

  • Number of cells: n + (n − 1) + … + 1 = n(n + 1)/2.

  • A cell for a substring of length L has L − 1 split points.

  • Each split checks every binary production: O(|G|) work.

  • Total: O(n3 · |G|) time and O(n2) cells of space. For a fixed grammar, this is O(n3).


Worked Example 1: An Accepted String

We use the well-known textbook grammar (already in CNF):

S → AB | BC
A → BA | a
B → CC | b
C → AB | a

Is w = baaba in L(G)? Positions: w1 = b, w2 = a, w3 = a, w4 = b, w5 = a.

Length 1

b is produced only by B → b. a is produced by A → a and C → a.

X[1,1] = {B}     X[2,2] = {A,C}   X[3,3] = {A,C}   X[4,4] = {B}   X[5,5] = {A,C}

Length 2

Each substring of length 2 has one split. Form all pairs (left variable, right variable) and look for a production with that right side.

Cell

Substring

Split → pairs

Matching rules

Result

X[1,2]

ba

{B}·{A,C} → BA, BC

A → BA, S → BC

{S, A}

X[2,3]

aa

{A,C}·{A,C} → AA, AC, CA, CC

B → CC

{B}

X[3,4]

ab

{A,C}·{B} → AB, CB

S → AB, C → AB

{S, C}

X[4,5]

ba

{B}·{A,C} → BA, BC

A → BA, S → BC

{S, A}

Length 3

Now there are two splits per cell. Collect the variables from both.

Cell

Substring

Split 1

Split 2

Result

X[1,3]

baa

b | aa: {B}·{B} → BB: none

ba | a: {S,A}·{A,C} → SA, SC, AA, AC: none

∅

X[2,4]

aab

a | ab: {A,C}·{S,C} → AS, AC, CS, CC: B → CC

aa | b: {B}·{B} → BB: none

{B}

X[3,5]

aba

a | ba: {A,C}·{S,A} → AS, AA, CS, CA: none

ab | a: {S,C}·{A,C} → SA, SC, CA, CC: B → CC

{B}

Length 4

Cell

Substring

Splits examined

Result

X[1,4]

baab

b|aab: {B}·{B} none. ba|ab: {S,A}·{S,C}: SS, SC, AS, AC none. baa|b: ∅·{B} none.

∅

X[2,5]

aaba

a|aba: {A,C}·{B} → AB gives S and C. aa|ba: {B}·{S,A} → BA gives A. aab|a: {B}·{A,C} → BA gives A, BC gives S.

{S, A, C}

Length 5

X[1,5] for baaba, four splits:

  • b | aaba: {B}·{S,A,C} → BA gives A, BC gives S.

  • ba | aba: {S,A}·{B} → AB gives S and C.

  • baa | ba: X[1,3] = ∅, nothing.

  • baab | a: X[1,4] = ∅, nothing.

So X[1,5] = {S, A, C}.

The complete table

len 5 |                      {S,A,C}
len 4 |                  ∅          {S,A,C}
len 3 |              ∅        {B}         {B}
len 2 |          {S,A}    {B}       {S,C}      {S,A}
len 1 |       {B}     {A,C}    {A,C}      {B}      {A,C}
      |        b        a        a         b        a

S ∈ X[1,5], so baaba ∈ L(G).

Recovering a parse tree

CYK can do more than say yes or no. If we remember why each variable was added (which rule and which split), we can rebuild a parse tree. For example, S was added to X[1,5] by S → AB with the split ba | aba:

S → A B              A ⇒* ba,   B ⇒* aba
A → B A              B → b,     A → a              (ba)
B → C C   split ab | a
    C → A B          A → a,     B → b              (ab)
    C → a                                          (a)

                 S
              /     \
             A       B
            / \     / \
           B   A   C   C
           |   |  / \   \
           b   a A   B   a
                 |   |
                 a   b

   leaves, left to right:  b  a  a  b  a

S was also added by S → BC with the split b | aaba. That gives a second, different parse tree. Counting with the same table (multiply the counts of the two halves and add over all splits and rules) shows that baaba has exactly 2 parse trees, so this grammar is ambiguous. CYK is a handy way to detect ambiguity for a particular string.


Worked Example 2: A Rejected String

Same grammar, w = abab.

len 4 |                 {B}
len 3 |             {B}      {S,C}
len 2 |        {S,C}    {S,A}    {S,C}
len 1 |     {A,C}    {B}     {A,C}    {B}
      |       a       b        a       b

The top cell comes from three splits: a | bab gives {A,C}·{S,C} → CC → B; ab | ab gives {S,C}·{S,C} → CC → B; aba | b gives {B}·{B}, which matches nothing. So X[1,4] = {B}.

S ∉ X[1,4], so abab ∉ L(G). (B does derive abab, but that does not matter: only the start symbol counts.)


Worked Example 3: A Grammar for anbn

A CNF grammar for { anbn : n ≥ 1 }:

S → AB | AX
X → SB
A → a
B → b

(S → AB gives ab; S → AX with X → SB gives a S b.) Tables for aabb and abab:

w = aabb                          w = abab
len 4 |          {S}              len 4 |          ∅
len 3 |      ∅       {X}          len 3 |      ∅       ∅
len 2 |   ∅     {S}      ∅        len 2 |   {S}    ∅     {S}
len 1 | {A}  {A}   {B}   {B}      len 1 | {A}  {B}  {A}   {B}
          a    a     b     b                a    b    a     b

For aabb: X[2,3] = ab gives S (S → AB); X[2,4] = abb, split ab | b gives SB, so X; X[1,4], split a | abb gives AX, so S. Accepted. For abab, no cell above length 2 gets any variable, so it is rejected.


Solving CYK Questions Quickly in Exams

  • Write the bottom row first; it is just "which variables have A → this terminal".

  • Make a reverse lookup table of the binary rules: BA → {A}, BC → {S}, AB → {S, C}, CC → {B}. Then each pair is one lookup.

  • For a cell of length L, list the L − 1 splits explicitly so you do not miss one. A missed split is the most common error.

  • An empty cell kills every split that uses it. In Example 1, X[1,3] = X[1,4] = ∅ removed two of the four splits for the top cell.

  • Questions often ask for a single cell (for example "which variables are in X[2,4]?") rather than the whole table. You only need the cells below it in its triangle.


CYK Compared with Other Parsing Methods

Method

Grammars handled

Time

Typical use

CYK

Any CFG (after CNF conversion)

O(n3)

Theory, membership proofs, natural-language parsing

Earley

Any CFG, no conversion needed

O(n3) worst case; O(n2) for unambiguous grammars

General parsing tools

LL(1), LR(1) parsers

Restricted subclasses (deterministic CFLs)

O(n)

Compilers

Brute-force derivation search

Any CFG

Exponential

Never in practice

Valiant (1975) showed that general CFG parsing can be reduced to Boolean matrix multiplication, so it can be done in less than cubic time in theory, but CYK's simple O(n3) bound is what exams expect. Compilers do not use CYK: programming-language grammars are designed so that linear-time parsers work.

CYK also gives a clean proof that membership is decidable for context-free languages, one of the decision properties discussed in Closure & Decision Properties of CFLs.


Common Mistakes

  • Running CYK on a grammar that is not in CNF. A rule like S → aSb or A → B does not fit the split logic. Convert first.

  • Mixing up the order of a pair. For split wi..k | wk+1..j, the left variable comes from X[i,k] and the right one from X[k+1,j]. AB and BA are different right sides.

  • Missing a split. Each cell of length L needs all L − 1 splits.

  • Accepting because some variable is in the top cell. Only the start symbol matters.

  • Stopping when a cell is found non-empty. Collect variables from all splits: a cell is a set, and later cells may need all of them.


Practice and GATE-Style Questions

Q1. For a string of length 6, how many cells does the CYK table have, and how many split points are examined in total?

Cells: 6·7/2 = 21. Splits: a cell of length L has L − 1 splits and there are 7 − L such cells, so the total is ΣL=2..6 (7 − L)(L − 1) = 5·1 + 4·2 + 3·3 + 2·4 + 1·5 = 35. In general the total is (n − 1)n(n + 1)/6, which is Θ(n3).

Q2. Using the grammar of Example 1, find X[1,3] for w = aab.

X[1,1] = X[2,2] = {A, C}, X[3,3] = {B}; X[1,2] (aa) = {B} via CC; X[2,3] (ab) = {S, C} via AB. Splits for aab: a | ab gives {A,C}·{S,C}, and CC gives B; aa | b gives {B}·{B}, nothing. So X[1,3] = {B}, and since S is not there, aab ∉ L(G).

Q3. Using the grammar of Example 1, is "ab" in L(G)? Is "ba"?

X for ab: {A,C}·{B} → AB → {S, C}. S is present, so ab ∈ L. For ba: {B}·{A,C} → BA, BC → {A, S}. ba ∈ L too.

Q4. Why is the time O(n3) and not O(n2), even though the table has only O(n2) cells?

Each cell must examine up to n − 1 split points. O(n2) cells × O(n) splits per cell = O(n3) (times the grammar size).

Q5. Interview: how would you change CYK to count the number of parse trees of w?

Store a count N[A, i, j] instead of a yes/no. Set N[A, i, i] = 1 if A → wi. For longer substrings, N[A, i, j] = Σ over rules A → BC and splits k of N[B, i, k] · N[C, k+1, j]. Then N[S, 1, n] is the number of parse trees (equivalently, leftmost derivations). For baaba in Example 1 this gives 2.


Summary

  • CYK solves the membership problem for CFLs: is w ∈ L(G)?

  • It needs the grammar in CNF, so every long derivation splits the string into two non-empty pieces.

  • X[i,j] = set of variables deriving wi…wj, filled by increasing length; accept iff S ∈ X[1,n].

  • n(n + 1)/2 cells, L − 1 splits per cell, O(n3·|G|) time.

  • With back-pointers it builds parse trees; with counts it counts them and exposes ambiguity.

CYK answers "who can generate this substring?" for every substring, shortest first. Two halves you already know, one rule to join them: that is the whole algorithm.