Motivation
A context-free grammar can have many different derivations of the same word, and naive derivation search may repeat the same questions. Instead, ask which variables can derive each consecutive substring of the input. When grammar productions have a restricted form, every nontrivial parse tree splits into two smaller subtrees. A table indexed by substrings can reuse these smaller answers and decide membership without enumerating all derivations.
The algorithm below is often called CYK. Its input is a grammar in the specified normal form and a word; normal-form conversion is a separate construction in the companion notes. A membership answer concerns this grammar and this word, not the equivalence of two arbitrary context-free grammars.
Definitions
Let be a finite context-free grammar. Assume every production has the form with variables or with terminal . Optionally is allowed, with absent from every right-hand side. This is the normal-form convention used here. For a nonempty word , let be the set of variables that derive the substring , where .
The table is computed by increasing substring length. Set . For , put in precisely when there are with and a production such that and . Accept a nonempty word exactly when . For the empty word, accept exactly when the exceptional production is present.
Theorems
Theorem 2.3.1
(Correctness of substring membership)
For every nonempty input and all , the computed set consists exactly of the variables for which . Thus the algorithm decides whether the grammar generates the input.
Theorem 2.3.2
(Resource bound)
A direct implementation that checks every split and binary production uses elementary production checks and Boolean table entries for . With backpointers for successful entries it can reconstruct one parse tree when the input is accepted.
Proof sketch or proof idea
Proof
(Correctness by induction, and the resource count)
Proceed by induction on the substring length. For length one, a variable can derive one terminal only by a terminal production: a binary production yields two nonempty variable subtrees, and under the stated normal form neither can derive the empty word. The initialization is therefore exact.
For a longer substring, a variable at the root of any parse tree must use a binary production . Its two children produce nonempty consecutive parts of the yield, giving some split . By induction, and appear in the corresponding shorter-substring sets, so the table includes . Conversely, if the table inserts using and a split, induction supplies derivations of both parts; applying the production and then those derivations yields the full substring. This proves both inclusions. The exceptional empty start rule never contributes to a nonempty subtree because the start variable is absent from right-hand sides.
There are substrings and at most split positions per substring. Checking all binary productions at each split gives checks; terminal initialization is within this bound up to the usual input-reading and constant-size boundary terms. A Boolean table has one entry per variable and substring. For each inserted variable, store the terminal production or one successful production and split. The recorded children have shorter yields, so recursively following pointers terminates and gives a parse tree. One pointer per table entry suffices for one tree, not for all possible parses.
Proof X-ray
Where each normal-form hypothesis is used
The induction is strong induction on the length , and it needs every split to produce two strictly shorter, nonempty intervals. Three hypotheses supply this. The form makes the root of a length-one tree a terminal rule and the root of a longer tree a binary rule, so there is no third shape to handle. The absence of unit rules and of -rules other than means a binary child can never derive the empty word, so both intervals are nonempty and both are shorter than . The ban on in right-hand sides keeps out of every nonempty tree. The only non-obvious move is the converse inclusion: a cell entry is a certificate, so each inserted variable carries two shorter certificates. Drop any one hypothesis and a cell can miss a variable that a parse tree places there (see the unit-rule example under common mistakes).
Worked examples
Worked example 2.3.3
(A two-symbol word)
With productions , , , the input gives and . The only split inserts into . Therefore is accepted, with root production and two terminal children.
Worked example 2.3.4
(A longer nested derivation)
Use , , , . For , the two middle symbols put in . The substring then puts in via . Finally the leading and that put in . The resulting parse tree yields .
Worked example 2.3.5
(An empty table entry)
For the first grammar and input , each length-one set contains . No production has two children, so is empty and is absent. The algorithm rejects; this conclusion follows from the entire table construction, not merely from failing to find one particular derivation.
Common mistakes
Counterexample mode
Testing only the first split
Claim: to fill it is enough to test the split , because a variable that derives at all must do so through its first split. Take , , , , and the input . Then is generated: . With the single split the pair is and , and no rule exists, so and the input is wrongly rejected. The split gives (by ) and , so . The repaired claim is the recurrence itself: is the union over all with .
Common mistake
(Running the table on a grammar with unit rules)
Take , and the input . The word is generated (), but initialization gives only, since is not a production, and the recurrence never revisits length one. So and the word is wrongly rejected. The table is exact only for grammars already in the stated normal form; first remove the unit rule (here, replace by ).
Common mistake
(Treating one stored parse as proof of unambiguity)
Take and . Here , and through both and , which are the two different trees and . A single backpointer would reconstruct only one of them. A tree from the table shows membership; it does not show that no other tree exists.
A table entry may contain several variables and a variable may have several valid backpointers. Storing only the first successful pointer preserves membership and one parse, but loses information about other parses. The exceptional empty word must be handled separately: the displayed table has no cell for a substring of length zero.
Executing the table algorithm
A direct implementation can store a Boolean flag for each triple . First initialize every flag to false. Scan the terminal productions for each input position and set the corresponding length-one flags. Then for lengths , consider each with , every split , and every production . If the flags for and are true, set the flag for to true and optionally save that production and split as a witness.
When processing length , both substrings at any split have length smaller than . Thus all flags read by the update have their final values. The order among cells of the same length is irrelevant. Setting a flag to true is monotone: once a derivation has been found, a later failed split must not reset it to false. Equivalently, the mathematical update is a union over all successful combinations, not an assignment based on the last one inspected.
Worked example 2.3.6
(Different splits for the same cell)
Consider productions , , , , , , . For input , the root can use with split after the first character: derives and derives . It can also use with split after the second character: derives and derives . Both insert the same variable into . One backpointer produces one parse; retaining both would preserve the choice of two root decompositions.
The grammar may contain symbols that derive no terminal string, repeated productions, or variables unreachable from . Such symbols can appear in the representation, but they do not invalidate the induction. A table entry contains a variable only when a terminal production or a certified pair of shorter entries supports it. Removing unreachable or unproductive symbols can improve an implementation, but is not a prerequisite for correctness of this table algorithm.
Backpointers and ambiguity
A backpointer for a length-one entry records a production . For a longer entry it records a production and a split , together with the two child entries. To reconstruct a tree rooted at over , create a node labeled , follow its pointer, and recursively build the two children over their specified intervals. At each internal node the intervals are nonempty, disjoint and consecutive; their union is the parent's interval. Consequently the leaf labels, read left to right, reproduce the input word exactly.
The table is a membership certificate in both directions. If appears in the final cell, the pointers yield a parse tree that can be checked locally: each internal node uses a grammar production and each leaf matches the input. If is absent, the correctness proof establishes that no parse tree exists. A single failed search path would not give that negative conclusion, but the table has considered all possible split positions and productions under the normal-form hypothesis.
An ambiguous grammar can give more than one parse tree for a word. Membership alone does not decide ambiguity, and one reconstructed tree cannot show that no other tree exists. If every successful backpointer is retained, the resulting shared structure can represent multiple parses, but explicitly listing them may take much more space than the Boolean table. A claim about the cost of enumerating all parses would need to count the size of the output and handle shared substructures carefully.
The role of normal form
A grammar with a unit rule does not fit the displayed recurrence. For instance, if and , initialization inserts but would fail to insert for input . Likewise, an empty production inside a binary derivation could give one child an empty yield, which is not represented by a split into two nonempty intervals. Applying the algorithm unchanged to such a grammar can give false negatives. Either first convert the grammar to the stipulated form with a proved language-preserving procedure, or use a different algorithm that explicitly handles those rules.
Normal-form conversion can change the grammar and its parse trees even when it preserves the language. A backpointer tree is a tree of the converted grammar. If an application needs a tree in the original grammar, the conversion must also retain enough correspondence to translate that tree back; mere equality of generated languages does not itself specify such a translation. The companion construction proves the language-level conversion, while this unit proves membership for a grammar already in the required form.
The empty-word convention is separate because there is no nonempty substring to enter in the table. Under the protected-start rule, is the only way the start can derive the empty word. If a different normal-form convention permits other empty productions, the special test must be adapted. For nonempty words, may appear at the root, but its prohibition on right-hand sides prevents the exceptional empty rule from being used as a child.
Understanding the complexity statement
The length loop contains cells at length , and each cell has candidate splits. Thus the number of cell-and-split pairs is . Scanning at most binary productions at each pair gives the stated cubic upper bound. This bound counts a simple implementation; indexing productions by child symbols can be useful, but its data structures and preprocessing must be accounted for in a separate analysis.
The space bound counts Boolean membership flags. A straightforward dense table allocates flags for each of nonempty intervals. Backpointers require indices and production identifiers, whose bit length depends on the input representation; saying entries is not automatically the same as that many bits. A sparse representation can save space on some inputs, but its worst-case behavior and lookup cost depend on the chosen data structure.
The complexity is polynomial in the grammar size and input length for a grammar already in normal form. When starting with a different grammar, include the time and size of the conversion in the total. The theorem does not say that the number of possible parse trees is polynomial: a compact table can share many partial derivations while the number of complete trees is much larger.
Summary
Normal form reduces a nonempty parse to either one terminal or a binary split into nonempty substrings. Induction makes the table exact; the start variable in the whole-word cell decides membership, and stored witnesses reconstruct one parse tree.
Exercises
Quick check
(For , , , compute the table for and decide membership.)
Fill the two length-one cells first.
Solution · Answer
The singleton cells are and . No binary production has children in that order, so , , and is rejected.
Quick check
(For the longer grammar in the examples, identify a split that places in the cell for .)
Use the input and the cell .
Solution · Answer
Split into and . The first part is derived by (so ) and the second by (so ), hence applies.
Quick check
(If is absent under the stated normal form, is the empty word accepted?)
Which productions can have an empty yield?
Solution · Answer
No. Every other production derives a nonempty yield, and the optional exceptional rule is the only empty production.
Quick check
(Why is it safe to store one successful backpointer per variable and cell when only one parse is requested?)
Think about what a pointer certifies.
Solution · Answer
Each stored pointer certifies one derivation from its variable over that substring. Following shorter-substring pointers recursively builds one complete parse; other derivations are unnecessary for this output.