Motivation
The CYK algorithm works because each nonempty parse tree has a particularly simple root: it either produces one terminal, or splits the word into two nonempty pieces. An arbitrary context-free grammar need not have this structure. It can contain long right-hand sides, terminal symbols mixed with nonterminals, renaming rules and empty productions. To apply CYK to such a grammar, we need a conversion whose proof explains why every original word still has a parse and why no new word appears.
A normal form is a statement about the language, not about preserving the original derivations. Simplification can collapse several original derivations into one rule. If the goal is to count parses or prove ambiguity, language equivalence alone does not give enough information. We will track precisely what the construction guarantees.
Definitions
Definition 2.6.1
(Protected-start Chomsky normal form)
A context-free grammar consists of finite disjoint sets of variables and terminals, a finite set of productions , and a start variable. We use a protected-start version of Chomsky normal form: every production has one of the forms
where are variables, is a terminal, and the last rule is optional. The fresh start occurs on no right-hand side. In particular, it cannot be a child in a binary rule. There are no other empty rules and no variable-to-variable unit rules. An empty set of productions is allowed and generates the empty language.
Our companion grammar-simplification unit proves an effective preprocessing theorem: from any finite CFG, one obtains a language-equivalent grammar with a protected fresh start, no empty production except possibly , and no unit production. We use that theorem here and explicitly explain the conversion after it. Deleting useless variables is optional for the normal form; it is not needed for the language argument.
Theorem 2.6.2
(Every context-free language has this normal form)
For every finite context-free grammar , an effectively constructible grammar in the protected-start normal form above satisfies , including the empty word when it belongs to the language.
Theorem 2.6.3
(The shape of a nonempty normal-form parse)
In a protected-start normal-form grammar, every parse tree for a nonempty word of length has exactly terminal-production nodes and binary-production nodes. Its root is either a terminal production when , or a binary production with two nonempty child yields when .
Proof: isolate terminals and make chains binary
Proof
(Terminal proxies and right chains preserve the language)
Start with the preprocessed grammar. Every nonempty right-hand side has length one or more. A length-one right-hand side must be a terminal: a single variable would be a unit rule. The protected empty rule, if present, is already allowed and is left untouched.
For each terminal that occurs in a right-hand side of length at least two, create one fresh variable with the sole production . In every such long right-hand side replace each occurrence of by . Leave existing one-terminal rules alone. The resulting nonempty rules have either one terminal or a sequence of at least two variables. The replacement is simultaneous, and no is used as a start symbol.
Why is this language preserving? In an old parse tree, replace every terminal leaf appearing among siblings by a node with its child. Conversely, every node in a new parse has exactly that one terminal child; contract it. These transformations preserve the left-to-right leaf word. Since the fresh variables have no other productions, the reverse transformation cannot introduce a choice that did not exist in the old rule.
Now take each rule of length ,
where each is a variable. Introduce fresh variables , unique to this rule, and replace it by the chain
For this means exactly and . Existing length-two rules remain unchanged. Every new variable in this chain has exactly the displayed production, and no other old rule uses it. Expanding the chain therefore forces the original sequence in order. Conversely, a node using the original rule can be expanded into the chain without changing the yields of its children. This gives language inclusion in both directions.
The protected start cannot appear on a right-hand side before conversion. The procedure inserts only fresh proxy and chain variables, so it still cannot appear there afterwards. It introduces no empty or unit rule. Hence the resulting grammar has exactly the required forms and the same language, including if and only if its protected empty rule is present. This proves the first theorem.
Proof X-ray
Why fresh variables make contraction exact
Two things must hold: the new grammar generates nothing extra, and nothing is lost. “Nothing extra” uses freshness. A chain variable appears on the right-hand side of exactly one rule and has exactly one production, so any use of it expands to the original sequence , and contracting a completed chain gives a legal use of the old rule. If were shared between two rules, contraction could splice the front of one rule onto the end of another, which is the failure shown in the four-variable example below. “Nothing lost” is the easier direction: expand each old rule node into its chain. The non-obvious move is a piece of bookkeeping, namely choosing names unique to the rule and the position, and the argument closes because contraction works from the leaves upward over completed subtrees.
Proof: binary trees have one fewer internal node
Proof
(Counting the nodes of a full binary tree)
For a nonempty derived word, the optional cannot occur below the root, because occurs nowhere on a right-hand side. Nor can it be used at the root of a nonempty yield. Thus every node is either binary or has exactly one terminal child. The word has terminal leaves, hence terminal-production nodes.
Contract each terminal-production node and its terminal child to a single leaf. The remaining rooted tree is full binary. If it has binary internal nodes, counting its edges gives , so . In particular a binary child cannot derive the empty word: no variable other than the protected start has an empty derivation. This is exactly the nonempty-split hypothesis used by CYK.
Concept lensCombinatorial
A normal-form parse tree as a bracketing of the word
The nonempty-split property says that every binary node divides an interval of the word into a left interval and a right interval, both nonempty. A normal-form parse of a word of length is therefore a full binary bracketing of its letters, with variables as labels, and its binary nodes are the places where a split is made. This is exactly the interval structure that the CYK table indexes: the cell for an interval is filled from pairs of cells for its two parts.
Worked examples
Worked example 2.6.4
(A mixed production)
Suppose preprocessing has produced , , with protected start . Introduce and , giving the temporary rule . A fresh makes it binary:
Both grammars generate exactly . The occurrence of under uses ; the final occurrence uses the proxy . They happen to have the same terminal yield, but their roles in the parse are different.
Worked example 2.6.5
(The empty word and a single letter)
The grammar generates . One valid protected normal-form grammar is
The root never occurs on a right-hand side. The rule supplies the length-one case; the binary rules add one leading at a time. Omitting would lose exactly the empty word.
Worked example 2.6.6
(Four variables in one rule)
For , use fresh and the three rules , , . If generate respectively, the new tree yields in the same order. Reusing from an unrelated production could give it an extra alternative and therefore produce words that the original rule did not allow.
Worked example 2.6.7
(An empty language)
If the original grammar is , no terminal word is derivable. A grammar with a fresh start and no productions is already in our normal form and generates the same empty language. There is no requirement to manufacture a terminal production merely to make the grammar look nonempty.
Common mistakes and scope
Counterexample mode
Renaming is not a normal-form rule
A tempting shortcut is to treat as if it were a normal-form rule and run CYK unchanged. Take , with start symbol , which generates the word . A CYK table that uses only rules of the forms and fills the length-one cell for with alone, because only has a terminal on its right-hand side. The start symbol never enters the table, so is rejected although . Deleting the unit rule is no repair, since then nothing is generated; the proved preprocessing step replaces it by .
Common mistake
(Binarizing before removing empty and unit rules)
The order of operations matters for this particular presentation. Binarizing a rule first is possible, but then a later empty-rule elimination can create unit rules, which must also be removed. Here we cite simplification first and only then add forced terminal and binary rules. The proof does not claim that every conceivable rearrangement of these steps works without further cleanup.
Common mistake
(Parse counts are not preserved)
Nor does it claim that the conversion preserves parse counts. For example, , , has two parse trees for ; unit elimination may give the single production when productions are treated as a set. The language stays unchanged, while a CYK counting table for the new grammar counts its trees, not the old ones. To transfer ambiguity information one would need extra provenance and a separate proof.
Reading the construction as an algorithm
A rule with variables is replaced by binary rules and fresh chain variables. Thus, after the preprocessing theorem has been applied, terminal isolation and binarization add only linearly many symbols and productions relative to the total length of the preprocessed grammar. This accounting does not imply that the particular preprocessing procedure was linear or polynomial: expanding all nullable-position choices can be exponential in the original rule length. A different order and shared intermediate variables can improve size, but their analysis is not part of this theorem.
To implement the construction, use fresh names systematically and retain a mapping from each artificial variable to the production and position that created it. This mapping supports the contraction described in the proof and helps a student reconstruct an original-language witness. It does not recover multiplicities already collapsed during simplification. The distinction between a witness word, one parse and all original parses should remain visible at the interface to any parser.
A useful way to follow one converted derivation is to record the yield at every artificial node. A terminal proxy contributes exactly its named letter. A chain variable contributes the consecutive suffix of the original production assigned to it. These local claims let us contract the artificial nodes from the leaves upward, one completed subtree at a time. This is useful when the original children themselves have many possible derivations: their internal choices are left unchanged by the contraction. The argument does not need the grammar to be unambiguous, and it does not require all its variables to be productive. An unproductive child simply has no completed terminal-yield tree to contract.
There is also an easy boundary check on the second theorem. A nonempty one-letter word has , hence no binary nodes. For a two-letter word there is exactly one binary node, whose two children each produce one terminal. These counts are properties of a completed normal-form parse tree; they do not say that an arbitrary sentential form in the middle of a derivation contains exactly variables.
Another normal form makes every derivation step consume a letter, at the cost of a different construction.
A path to generalization
What if every rule must begin with a terminal?
Another normal form makes every derivation step consume a letter, at the cost of a different construction.
Greibach normal form allows only rules , where is a terminal and is a string of variables, possibly empty. Every context-free language without the empty word has such a grammar. Since each step then produces one letter, a leftmost derivation of a word of length takes exactly steps. The construction needed is more involved than the one above.
Summary
First remove empty and unit productions while protecting the start and its possible empty word. Replace terminals in long rules by fresh terminal proxies, then expand long variable sequences into fresh binary chains. Tree expansion and contraction prove equality of languages. The resulting binary-tree shape supplies the nonempty split needed by CYK, but does not automatically preserve ambiguity or parse counts.
Exercises
Exercise 2.6.8
(Convert the already simplified grammar , , to the protected normal form. Identify its language.)
Foundation
Solution(3)
- 1
Isolate the terminal in the long rule
Add and rewrite as .
- 2
Binarize the sequence of three variables
Introduce a fresh and use , . Keep , and .
Because: The rule has length , so it needs one fresh chain variable.
- 3
Read off the language
The only way to leave is , and then . The language is .
Quick check
(A normal-form parse tree has seven terminal leaves. How many binary-production nodes does it contain? Why can none of its non-start variables derive the empty word?)
Use the node count for a nonempty word.
Solution · Answer
It has six binary nodes. Any non-start node is expanded only by a binary rule or a terminal rule. In a finite parse tree these rules cannot produce an empty terminal yield, and the sole permitted empty rule belongs to the protected start, which cannot occur as a child.
Quick check
(Suppose , , and . Give a normal-form grammar for the same language and explain why its parse count differs.)
What does unit elimination do to the two roots and ?
Solution · Answer
The one-rule grammar generates the same singleton language. The original has distinct trees with intermediate roots and , while the new grammar has one tree. Language equality is not a parse-tree bijection through unit elimination.
Exercise 2.6.9
(The preprocessed grammar has and each of has a one-terminal production. How many fresh chain variables are required by the stated right-chain construction? Write the binary rules.)
Core
Solution(2)
- 1
Count the chain variables
The length is five, so three variables are introduced.
Because: A rule of length needs fresh variables.
- 2
Write the chain
The rules are , , and . Every introduced variable has exactly its displayed rule.