Motivation
The preceding context-free chapter proved that grammars can be simulated by stack machines. It used a normal-form theorem as an explicit prerequisite for pumping and left the converse machine-to-grammar construction for later. This chapter supplies both arguments. They reveal different kinds of normalization: simplifying rules without changing terminal words, and summarizing an arbitrarily long computation by its entry state, one stack symbol and its exit state.
A grammar variable need not stand for a visible constituent such as a noun phrase. It can stand for a promise about a computation. The variable below describes the entire job of removing one stack symbol , starting in state and finishing in state . Internal details can be nested arbitrarily deeply, but the interface has only three finite labels. That is the reason a finite grammar suffices.
Definitions
Definition 2.2.1
(Nullable variable, unit rule and normal form)
A variable of a CFG is nullable if it derives the empty word. A rule with both symbols variables is a unit rule. A grammar is in Chomsky normal form for nonempty words if every rule is or , with variables and terminal . To retain the empty word, we may additionally allow , provided the fresh start variable never occurs on a right-hand side.
Use the preceding chapter's NPDA convention: a transition reads , replaces the top stack symbol by a finite string, changes state, and acceptance means both empty unread input and empty stack. The top of the stack is written at the left. Each transition table is finite, although a run need not have bounded length.
Definition 2.2.2
(Protected removal of a stack symbol)
A protected removal of from state to state , reading , is a finite computation that starts with stack , ends with stack , and first exposes that suffix at its last step. No symbol of is inspected or changed. Because transitions access only the top, the same sequence of steps works for every suffix . Equivalently, one may check the run on the stack consisting just of , ending the first time it becomes empty. The states and consumed word are retained.
Theorem/proposition
Theorem 2.2.3
(Context-free normal form)
Every CFG language has a grammar in normal form for . If , a fresh start variable with its single exceptional empty rule can preserve the whole language. The construction is finite and effective; it need not preserve the original grammar's parse trees or ambiguity.
Theorem 2.2.4
(A grammar from an empty-stack NPDA)
Let be a finite NPDA accepting by empty stack. There is a finite CFG with language . Consequently, together with the preceding chapter's construction, CFGs and empty-stack NPDAs describe exactly the same languages.
Proof sketch or proof idea
Proof
(Normal form by nullable deletion, unit removal and binarization)
For normal form, first add a fresh start with , and never place on a right-hand side. Compute the nullable variables by starting with those having an empty rule and repeatedly adding when a rule has only already nullable variables on its right. This increasing process stabilizes because there are finitely many variables. Induction on its stages proves every marked variable nullable; induction on a parse tree for the empty word proves every nullable variable eventually marked.
For each rule, add every version obtained by deleting any collection of nullable variable occurrences, retaining only nonempty right-hand sides. Remove the old empty rules; keep exactly when the original start was nullable. To verify preservation, prune subtrees yielding the empty word from an original parse tree for a nonempty word. Conversely, at each deleted occurrence insert a fixed empty-word derivation of that nullable variable. There are finitely many occurrences in any rule, so only finitely many versions are added. This proves both inclusions of terminal languages, rather than simply assuming deletion is harmless.
Next eliminate unit rules. Compute the reflexive transitive reachability relation through unit rules. For every such pair, copy each nonunit rule as a rule , then discard all unit rules. A derivation in the old grammar has finite blocks of unit steps followed by a nonunit step; collapse each such block to the copied rule. Conversely, expand a copied rule by its finite unit path. The protected empty rule remains confined to : no other variable reaches , since occurs on no right-hand side.
For each terminal occurring in a right-hand side of length at least two, introduce a fresh variable with and replace those occurrences by . This only subdivides terminal leaves. Finally replace a right-hand side of length by
using fresh chain variables for that rule. Each chain expands to exactly the original right-hand side, and contracting it recovers the old tree. Remaining rules have the required two-variable or one-terminal form. Removing the optional start empty rule gives the nonempty language. If the language has no nonempty words, a start with no productions correctly generates the empty language.
Proof
(Triple variables describe protected removals)
For the NPDA theorem, introduce a variable for every , and a fresh start . For every , add . Consider a transition that in state reads and replaces by , entering state . If , add
where means an empty right-hand side. If , for every choice of states add
For the right side is simply . These are finite choices in a finite construction, not an assumption of a bound on run length. There are finitely many transitions, finitely many states and a finite push length for each transition, so the grammar is finite.
We prove its intended variable meaning in both directions. A parse tree rooted at chooses one initial transition and then, from left to right, derivations for removing . By induction on the parse tree, those subderivations give protected removals of the pushed symbols, with exactly the intermediate states named by the rule. Execute them over the untouched lower suffix. Their concatenated inputs, preceded by , give a protected removal of . A pop rule is the one-step base case.
Conversely, induct on the number of steps in a protected removal of . Its first transition has some push string . If , it already exposes the suffix, so the computation has one step and the pop rule derives exactly its input. If , split the remaining run at the first successive exposures of , then , and so on, ending at . Each split exists: stack height drops by at most one per step, and a lower symbol cannot be accessed before the symbols above it have been removed. Each segment is a shorter protected removal of one , and consumes a consecutive input factor. The induction hypothesis supplies its corresponding triple-variable derivation. Choose the production with those observed intermediate states and concatenate the factors. This proves the exact protected-removal meaning.
An accepting run from first reaches an empty stack at its end: an empty stack permits no further transitions in this model, and acceptance requires all input consumed. Thus it is a protected removal from to some , and the start rules derive exactly the accepted words. This proves the converse without relying on an intuitive but undefined statement that “a grammar can remember the stack”.
Proof X-ray
Why the run splits at first exposures
The pivotal step is the converse induction. Three facts combine. A transition looks only at the top symbol, so a lower symbol cannot be inspected or changed before everything above it has been removed. The stack height drops by at most one per step, so on the way from down to the stack passes through each suffix at a first moment. Those moments cut the run into consecutive segments, each a protected removal of one with fewer steps than the whole run. Finally, the states at the cut points are exactly the labels that a production needs, which is why the construction ranges over every choice of intermediate states: the right production exists because it was added for all of them. If a transition could inspect symbols below the top, the cut points would not exist and a triple would not summarize a segment.
The construction proves effective finite description, not an unqualified polynomial bound in the original presentation size. A rule with many nullable occurrences can generate many deletion alternatives, and a long push string can require many combinations of intermediate states. This does not affect the language-equivalence proof. It does matter when grammar size itself is part of an algorithmic input: a later complexity estimate must account for the transformed description or use a separately justified size-controlled normalization. Keeping existence, effective construction and efficient construction distinct prevents a representational theorem from silently acquiring a stronger complexity claim.
Worked examples
Worked example 2.2.5
(Normalizing a matching grammar)
For , a grammar for the nonempty words is
The first alternative produces ; the second produces . Induction gives exactly for . To include the empty word with a protected start, add and use as start. It never occurs on a right-hand side; does. The distinction is why the empty exception belongs to , not indiscriminately to every variable.
Worked example 2.2.6
(A unit cycle does not create terminal words)
Take , , . The unit-reachability relation lets each of reach , so each receives the nonunit rule to . Removing the unit rules leaves only productions yielding . Infinite travel around was never a finite derivation of another terminal word. Grammar languages quantify over finite derivations, not every possible infinite sequence of rewrites.
Worked example 2.2.7
(One stack symbol, one triple variable)
Let a one-state NPDA start with , replace by on reading , and pop on reading , with no other transitions. There is only one triple variable , giving . The word has derivation , matching the stack heights . The word is not accepted: its first empties the stack while input remains, and the machine cannot restart. The grammar's variable records one complete removal, rather than an arbitrary interval of a run after the stack has already emptied.
Concept lensStructural
A variable as a computational interface
The triple forgets the detailed nested work but keeps precisely what a surrounding computation needs: where the work starts, which top symbol it removes, and the state in which the lower stack becomes visible again. The proof of the correspondence validates this interface in both directions. State labels alone would lose the stack obligation; a full stack string in every variable would give infinitely many variables. The triple is the finite middle ground.
Common mistakes
Common mistake
(Nullable does not mean only empty)
Nullable means "has some derivation of the empty word", not "only derives the empty word". Deleting a nullable occurrence therefore adds an alternative; it does not justify deleting that occurrence in every use of the rule.
Common mistake
(Chain variables must be fresh for each rule)
Fresh variables in binarization must be fresh for each rule, or unrelated chains may combine and generate new words.
Common mistake
(Protected removal cannot look below and then restore)
The NPDA construction is nondeterministic. Guessing intermediate states in a grammar production does not prove a deterministic stack machine suffices. Protected removal also cannot inspect the lower suffix and later restore it: that would exceed the variable's meaning. The first-exposure condition is what makes recursive composition sound.
Counterexample mode
One designated final state is not enough
Claim: for an empty-stack NPDA it suffices to add one start rule for a single chosen state . Take , start state , initial stack symbol , and exactly two transitions: reading in replaces by and enters ; reading in replaces by and stays in . Both words and are accepted, since each empties the stack with the input consumed, and nothing else is accepted, so . The construction gives and , and no other rules have a nonempty right-hand side. With alone the grammar generates only ; with alone it generates only . Empty-stack acceptance does not fix the final state, so the repaired statement adds for every .
Summary
Finite grammar transformations produce binary parse trees without changing nonempty terminal words, completing the normal-form prerequisite used by pumping. Triple variables summarize protected stack removals and produce a CFG for every empty-stack NPDA. Together the two machine/grammar constructions give the full language equivalence.
Exercises
Quick check
(Find nullable variables for , , , and give an equivalent grammar without empty or unit rules.)
Solution · Answer
Only is nullable: cannot produce the empty word, so neither alternative for does. Delete the occurrence of in , adding . Remove . Unit elimination then gives , , . This generates , exactly the original language.
Quick check
(Explain why replacing by , is safe, but sharing chain variables arbitrarily across unrelated rules need not be.)
Solution · Answer
Both alternatives had the same initial , and the two choices for give exactly the intended suffixes, so both directions are immediate. For a failure of arbitrary sharing, replace and by , , . Then additionally generates and additionally generates . Rule-local fresh variables prevent that mixing.
Quick check
(For the one-state machine above, characterize its accepted words by the counts of in each prefix and in the whole word.)
Solution · Answer
The height after a prefix is . Acceptance requires final height zero, so the full word has one more than . Every proper prefix must have positive height, equivalently ; otherwise the run empties early or attempts an invalid pop. Conversely these inequalities permit every transition, and the final equality empties the stack exactly as the input ends. These conditions are necessary and sufficient.
Quick check
(For the one-state NPDA with transitions and , write the grammar given by the construction and describe its language.)
Solution · Answer
There is one triple variable and the start rule . The transition on pushes one symbol, so ; the transition on pops, so . The language is , which is exactly what the machine accepts: it keeps while reading and empties the stack on the single .