Motivation
A grammar can contain symbols that never contribute to a terminal word, productions that only rename one nonterminal, and nonterminals that disappear. Removing these features makes later constructions such as Chomsky normal form easier to understand. It is also easy to remove too much: deleting every empty production loses the empty word, while deleting a nullable symbol in only one position can miss valid derivations.
We will give explicit finite constructions and prove both language inclusions. The constructions preserve languages, not necessarily parse trees, ambiguity or derivation lengths. They are preprocessing tools, so their hypotheses and special treatment of the empty word matter.
Definitions and setup
Definition 2.5.1
(Nullable nonterminal, empty production, unit production)
Let be a finite context-free grammar with disjoint terminal and nonterminal alphabets. A nonterminal is nullable when . A production is an empty production when its right-hand side is , and a unit production when it has the form for nonterminals .
First introduce a fresh start symbol that does not occur in any old production. Add . If is nullable, also add . The new start does not occur on any right-hand side. This preliminary grammar has the same language as the old one: the first new rule delegates to , and the second adds only an empty word that was already generated.
A nullable set is found as a least fixed point. Mark the left side of every empty production. Repeatedly mark when some right-hand side of an -production consists entirely of already marked nonterminals. Terminals are not nullable. A finite grammar has finitely many nonterminals, so marking stops.
Theorem 2.5.2
(Empty-production elimination)
From the fresh-start grammar one can construct a grammar for the same language with no empty production except possibly , and with absent from all right-hand sides.
Theorem 2.5.3
(Unit-production elimination)
From a finite grammar one can construct an equivalent grammar with no unit productions. If its only empty production is the protected and occurs on no right-hand side, that property is preserved.
Computing nullable nonterminals
Proof
(Correctness of the nullable marking)
Every mark is sound: the marking rule combines known empty derivations of all symbols on a right-hand side. Conversely, if derives the empty word, consider a finite derivation tree. Its root production can contain no terminal, and every child nonterminal has a smaller tree deriving the empty word. Induction on tree height shows those children are eventually marked, and then so is .
This proof handles cycles without guessing. The rule alone does not mark : the fixed point begins with no unsupported marks. If , and , then is marked first and afterward. A circular dependency needs a finite base derivation to establish nullability.
Eliminate empty productions
For each production , generate a right-hand side by independently retaining or deleting each occurrence that is a nullable nonterminal. All terminal occurrences and nonnullable nonterminals must remain. Insert every generated nonempty right-hand side for ; remove duplicates. Delete all empty right-hand sides, then restore exactly when the original start was nullable. In particular, deleting one occurrence of a repeated nonterminal is different from deleting another occurrence, although the resulting right-hand sides may coincide.
Proof
(The empty-production construction preserves the language)
To prove that every new derivation produces an old word, replace each generated production by the old production from which it came and insert an empty derivation for each omitted nullable occurrence. The protected empty production is valid because was nullable. Thus every new terminal word belonged to the original language.
For the other inclusion, take an old derivation tree for a nonempty terminal word. Remove every child subtree whose terminal yield is empty. At each surviving nonterminal, the removed children were nullable occurrences, so its remaining right-hand side is one of the generated alternatives. Retain the root and the children whose yields contribute to the nonempty word. This yields a new tree for the same word. If the old word is empty, the protected produces it. Both inclusions prove the theorem.
Proof X-ray
Deleting a symbol represents a whole empty derivation
The inclusion from new to old is easy; the inclusion from old to new carries the idea. A nullable occurrence in an old tree may sit above a large subtree with empty yield, but the new grammar cannot keep a nonterminal whose subtree is gone, so it must have deleted that occurrence at the parent. That is why each occurrence is deleted or kept independently: an old tree decides occurrence by occurrence which children have empty yield. Two hypotheses carry the argument. The finite derivation to the empty word, which the marking provides, justifies the deletion in the new-to-old direction by putting an empty derivation back. The protected start rule handles the one word that cannot be represented by any nonempty right-hand side, namely the empty word itself. Without the protected rule the construction loses , as the worked example with shows.
A right-hand side with nullable occurrences has at most deletion choices before duplicate removal. This can cause exponential expansion in the size of an individual production. A proof that a construction terminates is not automatically a polynomial-size bound for its output.
Eliminate unit productions
Build a directed graph on the nonterminals, with an edge for every unit production. For each , find every reachable by zero or more unit edges, including itself. For each nonunit production , add . Finally delete all unit productions. Unit cycles pose no difficulty: graph reachability has finitely many vertices, and copying a production more than once has no effect.
Proof
(The unit-production construction preserves the language)
For soundness, an added simulates the old unit path from to followed by . For completeness, take an old derivation tree and compress each maximal chain of unit nodes into the first subsequent nonunit production. The corresponding graph reachability caused that nonunit production to be copied to the chain's initial nonterminal. Every finite terminal derivation has such a subsequent production at each compressed chain, so the resulting tree produces the same word.
If does not occur on any right-hand side, no nonterminal other than has a unit edge into . Therefore only can reach the source of a protected through unit edges, and the copying step does not introduce an unprotected empty production. This is why the fresh-start restriction is useful, not decorative.
The zero-length path in the unit graph is essential. It ensures that every existing nonunit production of is copied back to even if has no outgoing unit edge. Without it, a construction that first removed all productions and then copied only along positive-length paths could accidentally delete ordinary terminal-generating rules. An alternative implementation may keep all existing nonunit productions and explicitly follow only positive-length paths; both descriptions give the same set after duplicates are removed.
Counterexample mode
Removing units first does not keep them removed
Claim: once unit productions have been eliminated, eliminating empty productions cannot bring any back. Take , , . There are no unit productions, so unit elimination changes nothing. Only is nullable, and deleting it from adds , a new unit production, while the language stays . The repair is the order used in this note: eliminate empty productions first, then unit productions, which here copies to give .
The construction preserves the terminal language even when some nonterminals cannot be reached from the start. Those extra rules can be removed by the following useful-symbol pass. Separating unit elimination from reachability simplifies the proof: the unit graph can be processed for every nonterminal without first deciding whether it participates in a start derivation.
Remove useless symbols
A nonterminal is productive if it derives some terminal word, possibly empty. Compute productive nonterminals by marking whenever a production for contains only terminals and already marked productive nonterminals. The empty right-hand side qualifies. Remove every production containing an unproductive nonterminal and remove unproductive symbols. A terminal derivation cannot use such a symbol, so this does not remove any terminal word.
If the start is productive, now compute the symbols reachable from it in the remaining grammar, beginning at the start and following right-hand-side occurrences of productions whose left side has already been reached. Remove productions and symbols not reachable. Every symbol in a remaining production is reachable, and every remaining nonterminal is productive. A terminal derivation from the start never visits an unreachable symbol, so the language is unchanged.
The order matters for the claim that the final grammar has no useless nonterminals. A symbol can be reachable only through a production later discarded because it contains an unproductive symbol; recomputing reachability after productive filtering removes that newly isolated symbol. If the start is unproductive, the language is empty. Represent it separately by a start symbol with no productions; its start is necessarily unproductive, so do not claim that this empty-language representation has all nonterminals productive.
Counterexample mode
Reachable alone is not useful
For , , , both and are reachable in the original grammar, but cannot derive a terminal word. Removing the production leaves unreachable; the reduced nonempty-language grammar can simply use .
Worked examples
Worked example 2.5.4
(Repeated nullable occurrences)
Let , . Both and are nullable. The production generates nonempty alternatives ; deleting either occurrence gives the same alternative. Keep , and protect the empty word using a fresh start. The resulting language is , exactly as before.
Worked example 2.5.5
(A unit cycle)
For , , , the unit graph makes and mutually reachable and makes both reachable from . Each of receives both nonunit productions to and . Deleting unit rules leaves the same start language .
Worked example 2.5.6
(Why a protected start is needed)
If , deleting the empty rule without compensation loses . Introduce . Nullable deletion adds alongside , and unit elimination copies these nonunit alternatives to . The resulting start still derives every word in , including the empty word, while no old nonterminal needs an empty rule.
Worked example 2.5.7
(An empty language)
For , , neither nonterminal is productive: no finite derivation produces a terminal word. Its language is empty. A grammar with fresh start and no productions represents that language. Merely finding that is reachable would not make it productive.
Common mistakes
Common mistake
(Each occurrence of a nullable symbol is its own choice)
A nonterminal may occur more than once in a right-hand side, and each occurrence is independently present or absent in the pruned tree. Enumerating only one global decision per symbol name can miss productions. For instance, if and is nullable, retaining only the first or only the second occurrence produces distinct alternatives and .
Common mistake
(A unit production is a whole right-hand side)
A unit chain is a sequence of whole productions , not a production containing a nonterminal among other symbols. The rule is not a unit rule. Similarly, a unit cycle alone does not generate a terminal word; productive alternatives at the end of a finite chain are what get copied.
Common mistake
(Equal languages do not mean equal parse trees)
Finally, language equivalence does not imply identical parse structure. Copying and pruning productions can merge derivations that were previously distinct. Do not use this language-preservation proof to conclude that the number of parse trees or ambiguity is preserved.
Summary
Nullable fixed points identify finite empty derivations. Deleting any combination of nullable occurrences and protecting the start preserves every word, including the empty word. Unit reachability then replaces chains by their nonunit exits. Productive filtering followed by reachability removes unused structure, with the empty language handled separately. Each step has a proof in both directions rather than a purely syntactic justification.
Exercises
Quick check
(For , , , list the nonempty alternatives generated from and state whether the start needs a protected empty production.)
Delete each nullable occurrence independently, then discard the empty result.
Solution · Answer
The alternatives are , and . Deleting both gives an empty right-hand side, which is omitted there. Since both and are nullable, so is , and the fresh start must retain its protected empty production.
Quick check
(For , , , give an equivalent unit-free start production.)
Follow the unit edges out of .
Solution · Answer
The unit graph has a path from to . Copy the nonunit production to obtain . The self-loop contributes no additional terminal production.
Quick check
(Explain why the grammar , , has empty language, despite every nonterminal being reachable.)
Which productions could start the productivity marking?
Solution · Answer
There is no production with terminals or an empty right-hand side from which productivity marking could begin. No nonterminal can derive a terminal word. Reachability only says that symbols occur along possible derivations; it does not guarantee termination in terminals.
Quick check
(In , where is nullable, list all distinct nonempty alternatives generated by deleting occurrences of .)
There are two occurrences, so four deletion patterns.
Solution · Answer
The alternatives are , , , and . All are nonempty because the terminal is never deleted. The two single-deletion cases differ in the position of the retained nonterminal.