Motivation
Finite automata cannot match arbitrarily deep nesting, since matching requires counting without a bound. Context-free grammars describe nested structure directly: a rule such as says that a balanced block is an opening bracket, a balanced block, a closing bracket and another balanced block. A pushdown automaton is the corresponding machine, a finite control with a last-in first-out stack. This chapter proves the precise link in one direction, from grammars to stack machines, and then proves a pumping lemma that places a boundary on the class.
The pumping lemma uses Chomsky normal form as an explicit prerequisite. The companion note Normal forms and the grammar hidden in a stack computation proves that prerequisite and the converse NPDA-to-grammar construction. The grammar-to-machine proof below is independent of that converse.
Definitions
Definition 2.4.1
(Context-free grammar and derivations)
A context-free grammar (CFG) is with a finite set of variables, a finite alphabet disjoint from , a finite set of rules written , and a start variable . We write if arises from by replacing one variable occurrence with for a rule ; is the reflexive transitive closure. The language is , and a language is context-free if it equals for some CFG. A derivation is leftmost if every step replaces the leftmost variable.
Definition 2.4.2
(Parse tree, yield and ambiguity)
A parse tree has the start variable at the root, each internal node labeled by a variable whose children spell the right-hand side of a rule, and leaves labeled by terminals or ; its yield is the word read along the leaves. Every word of is the yield of some parse tree, and, expanding the leftmost unexpanded variable at each step, every parse tree gives a leftmost derivation. A grammar is ambiguous if some word has two different parse trees, equivalently two different leftmost derivations.
Definition 2.4.3
(Nondeterministic pushdown automaton, empty-stack acceptance)
An NPDA is with finite sets , an initial stack symbol , and finite subsets of . A configuration is : the state, the unread input, and the stack with its top at the left. If with then . The machine accepts by empty stack if for some .
This convention is a choice. Acceptance by final state is another common convention; the equivalence of the two is a standard theorem that is not proved here, so every NPDA statement below refers to empty-stack acceptance.
Theorems
Theorem 2.4.4
(Two basic grammars)
(a) The grammar generates exactly . (b) Call a word over balanced if it has equally many opening and closing brackets and every prefix has at least as many opening as closing. The grammar generates exactly the balanced words, and each balanced word has exactly one parse tree.
Theorem 2.4.5
(From a grammar to a stack machine)
Let be a CFG. Define with one state , stack alphabet , initial stack symbol , and transitions for and for , with no other transitions. Then accepts, by empty stack, exactly .
Theorem 2.4.6
(Closure of context-free languages under union, concatenation and star)
If are context-free, so are , and .
Theorem 2.4.7
(Pumping lemma for context-free languages)
Assume the normal-form theorem: every context-free language has a grammar in Chomsky normal form, meaning every rule is or , generating . Under this hypothesis, if is context-free there is such that each with can be written with , , and for every .
Proof sketch or proof idea
Proof
(Basic grammars: induction on derivations)
Basic grammars. (a) By induction on derivation length, a terminal word derived from either uses immediately or begins with the remaining derivation yielding from , so the word is . Conversely is obtained by uses of followed by .
(b) Soundness follows by induction on derivation length: the yield of is a bracket, a balanced word, a bracket and a balanced word, and these constructions preserve the prefix condition. For completeness induct on length. Let be nonempty and balanced; it begins with an opening bracket. Let be the smallest positive length of a prefix with equal counts, which exists since itself has equal counts. For positive prefix lengths below the opening count strictly exceeds the closing count, so symbol is a closing bracket and the prefix of length has excess exactly one. Hence where (positions to ) has equal counts and nonnegative excess in every prefix, and is balanced because prefixes beyond have nonnegative excess and the prefix of length has excess zero. Both and are shorter, so apply the hypothesis. Uniqueness: any parse tree for nonempty must use at the root, and the decomposition with balanced is forced to be the first return to zero, because a balanced followed by a closing bracket returns to zero for the first time there. Induction on length gives uniqueness of the subtrees.
Proof
(Grammar to NPDA: both inclusions)
Grammar to NPDA. Every word of is accepted. Take a leftmost derivation and write with terminal and empty or starting with a variable. Leftmost derivations never modify the terminal prefix, so for some . We claim for every . The case is trivial. For the step, and the rule is . The rule transition replaces by on the stack, and then, writing with terminal and starting with a variable or empty, the transitions pop the symbols of against the input, which matches because . At the stack is empty and the input is consumed.
Every accepted word lies in . We prove: if , and , then . Use strong induction on . If is terminal, the only applicable transition pops against an input symbol , so . If is a variable, the first move is a rule transition to with . If the stack is already empty and . Otherwise each step inspects and replaces only the top symbol, and removes exactly one symbol while pushing possibly more, so the stack height drops by at most one per step. Let be the first time the stack is . During the stretch from to the height stays above , so are never touched, and this stretch is a computation from to where is the input read in it. Then , each stretch is shorter than , and induction gives . So . Applying this to finishes the proof.
Proof
(Closure under union, concatenation and star)
Closure. After renaming, assume disjoint variable sets with starts . Add the rules for union, for concatenation, and for star, with a fresh . In the derivations, the variable sets are disjoint, so the two subderivations from and evolve independently. This gives , and respectively, the last by induction on the number of uses of .
Proof
(The pumping lemma from the height of a parse tree)
Pumping lemma. Let be in normal form for with variables and put . In a parse tree every internal node has either two variable children or one terminal child. Hence, by induction on height (the number of edges on a longest root-to-leaf path), a tree of height has at most leaves. Take with and a parse tree of . Its height satisfies , so a longest path contains at least variable nodes. Among the lowest variable nodes on this path, two carry the same variable by pigeonhole; call them above . The subtree at has height at most , so its yield , where is the yield of 's subtree, satisfies . Since has two children and one leads toward , the other child's yield is nonempty (each side subtree of this complete parse tree has a nonempty terminal yield) and lies within or , so . Replacing the subtree at by a copy of the subtree at gives ; replacing the subtree at by a copy of the subtree at , repeatedly, gives .
Proof X-ray
Dependencies in the context-free pumping lemma
The proof stands on three supports. First, the normal form hypothesis makes the tree binary, which converts the height bound into a leaf bound and guarantees that one side branch contributes a nonempty yield; without it, rules like or could make empty. Second, pigeonhole is applied to variables on a single longest path, which fixes . Third, the same variable at two nodes means the subtree at the lower node can replace, or be replaced by, the upper one while remaining a valid parse tree. The argument closes by reading the yields.
Counterexample mode
Context-free languages are not closed under intersection or complement
Claim (false): if and are context-free then so is . Take and , generated by , , and its mirror image. Each is context-free, but , which is not context-free by the pumping lemma (see the worked example on ). Complement fails as well: if the class were closed under complement, then since it is closed under union, would be context-free. Repair: closure holds for union, concatenation and star; for intersection with a regular language it also holds, but that is not proved here.
Concept lensStructural
The stack as the unexpanded part of a leftmost form
During the simulation, a leftmost sentential form is split into a consumed terminal prefix and a pending part that sits on the stack. The stack therefore contains exactly what the derivation still has to expand or to match against the input. Rule transitions are the derivation's expansions, and pop transitions are the checks of terminal symbols against the input. This is why a single state suffices for the construction: all the control information lies in the stack contents.
Worked examples
Worked example 2.4.8
(A leftmost derivation and the parse structure of (())())
With : . The root rule splits the word as with and ; the subderivation of is the second through fourth steps and that of is the last three. By the uniqueness part of the first theorem no other tree exists.
Worked example 2.4.9
(Ambiguity of an expression grammar)
For the word has two leftmost derivations: groups it as , while groups it as . Two different trees give different readings, which matters for evaluation. The following construction repairs this ambiguity by separating sums, products and atoms. We must prove both that it keeps the same terminal words and that it gives each word only one tree. Ambiguity belongs to the grammar: a language may also have an unambiguous grammar.
Repairing the expression grammar without changing its words
An instruction such as "multiply before adding" does not change the productions of the original grammar. Its two trees still exist. To make the grammar itself specify that convention, use three variables, with start variable :
Here means an expression, a term and a factor. The terminal alphabet is still . These rules have no parentheses, unary operators or empty expressions. Let
Thus , and lie in , whereas , and do not. The case means the single word .
Theorem 2.4.10
(Same expression language, unique parse)
The original one-variable expression grammar and the layered grammar both generate exactly . The layered grammar is unambiguous. Its trees put multiplication inside terms and group repeated additions and repeated multiplications to the left.
Proof
(The layered grammar generates the same words)
Language equality. For the original grammar, induction on a parse tree shows that every yield is in : a leaf production gives , and joining two words of with either operator gives another word of . Conversely, induct on the number of operators of a word in . The zero-operator word is . For a longer word, split off its last operator and last , obtaining . Use or according to , apply the induction hypothesis to , and derive on the right. This proves both inclusions for the original grammar.
For the layered grammar, generates only , and generates exactly the nonempty products : each use of adds one last factor, and ends the recursion. Here means repetitions of the two-symbol block consisting of a literal multiplication token followed by ; the parentheses are notation, not terminals. An -tree is a nonempty sequence of such terms separated by , because adds one last term. Every word in has such a decomposition: cut at every , then read each remaining block as a product. This constructs a layered derivation for it. Conversely, those productions can produce only alternating operands and operators, starting and ending with . Hence the layered language is also .
Why the repaired grammar has only one parse tree
Proof
(Uniqueness of the layered parse tree)
For , the tree for is forced. For a -word, prove uniqueness by induction on its number of multiplication tokens. With none, only is possible. With at least one, the root must use . Since its right yields exactly one , the root's multiplication token must be the last token in the word. Its left substring is therefore fixed and has one fewer multiplication token. Induction gives its unique -tree, and the right -tree is fixed too.
Now induct on the number of addition tokens in an -word. With none, the root cannot be , so it must be , whose tree was just proved unique. If there is an addition, the root cannot be , because a term contains no . It must be , and its must be the rightmost addition token: the right term cannot contain another . This forces both substrings. The left one has one fewer addition token and hence a unique -tree by induction; the right one has a unique -tree by the preceding argument. Thus every word has at most one tree. The language-equality proof already supplies at least one, completing unambiguity.
Proof X-ray
A root split must be forced, not merely possible
The language-equality argument shows how to construct a tree. That alone cannot exclude another tree. Uniqueness needs the restrictions on the right child: a factor is one , and a term contains no addition. Those restrictions force a root multiplication to be the last multiplication in a term, and a root addition to be the last addition in an expression. Induction then handles the forced smaller pieces. We do not assume the intended precedence convention as part of the proof; we derive it from the productions.
Worked example 2.4.11
(Reading the root before expanding a tree)
For , the rightmost forces the root split . In its left expression, the remaining forces . The product has just one -tree. The resulting grouping is ; the displayed grouping parentheses describe the tree and are not extra terminal symbols. If each is assigned value , this tree gives . A tree for would give , but is excluded because a -subtree cannot generate .
Similarly, has root split , and has term split . These are left-associative trees. Although ordinary addition and multiplication are associative and these particular regroupings have equal numerical values, equal values do not make two trees identical. The grammar fixes syntax independently of that algebraic coincidence.
Which differences actually demonstrate ambiguity?
Counterexample mode
Two derivation orders can describe one tree
For , , , the derivations and are different. They expand independent sibling nodes in different orders, but describe the same tree: an root with children , and terminal leaves . Only the first derivation is leftmost. This grammar is unambiguous. To demonstrate ambiguity, exhibit two different trees or two different leftmost derivations for the same word, not just two arbitrary expansion orders.
Left recursion is another separate issue. The rule recurses on the left, yet the proof above establishes unambiguity. A naive procedure that always expands this recursive alternative first may run forever before reading input. That is a problem with that parsing procedure; it does not supply a second tree. Conversely, merely deleting this alternative loses every expression containing , so it does not preserve the language.
Quick check
((a) Give the forced grouping of . (b) If we replace the term rules by , while keeping , does the grammar remain unambiguous?)
Solution · Answer
(a) Cut first at the last , then at the remaining , and finally at the multiplication in each term. The grouping is . (b) No. The word has a -tree whose left child generates and another whose right child generates . Placing either below gives two expression trees. The repair required a factor, rather than an arbitrary term, on the right of ; naming multiple levels without enforcing their restrictions is not enough.
Worked example 2.4.12
(Running M_G on aabb)
For : . The first, third and fifth steps expand , the other steps pop a matched terminal, and the fifth step uses . The choice is made at the right moment by nondeterminism, and a wrong choice, such as expanding with too early, leaves unread input with an empty stack, which is not accepting.
Worked example 2.4.13
( is not context-free)
Suppose a pumping length exists for and take . Since , the factor cannot contain both an and a , because the symbols lie between them. So at least one of the three letters does not occur in , while means at least one letter occurs. Then has a larger count of a letter that occurs in and an unchanged count of a letter that does not, so the three counts are not equal and the word is outside . This contradicts the lemma.
Common mistakes
Common mistake
(Ambiguity belongs to the grammar, not the language)
A common error is to treat ambiguity as a property of a language. It is a property of a grammar; "inherently ambiguous" is a separate notion for languages. Likewise, "context-free" does not mean that the grammar is unambiguous or that the machine is deterministic. In general nondeterminism is needed here; this chapter does not discuss deterministic pushdown automata.
Common mistake
(Empty-stack acceptance needs two conditions at once)
The NPDA of this chapter accepts by empty stack: an accepting configuration requires the input to be exhausted and the stack to be empty at once. A run that has consumed all input but still has stack symbols is not accepting.
Common mistake
(Check every placement of the pumped part)
In a pumping argument for the bound means that lies inside one block of equal letters or straddles two adjacent blocks. A complete argument treats every such placement: in each, some letter is missed by and keeps its count , while pumping changes the count of at least one letter occurring in (because ), so the three counts differ. Checking only a convenient placement proves nothing. Also, the pumping lemma can show that a language is not context-free, but it never shows that one is.
Summary
Context-free grammars generate nested structure, and derivations correspond to parse trees. The layered expression grammar preserves its terminal language while imposing a unique tree, with multiplication taking precedence and repeated operators associating to the left. A one-state stack machine simulates a leftmost derivation, and it accepts by empty stack exactly the grammar's language; the converse is proved in the companion normal-form note. Context-free languages are closed under union, concatenation and star, but not under intersection or complement. Under the normal-form hypothesis, the pumping lemma gives and shows that is outside the class.
Exercises
Quick check
(Give a grammar for and justify both inclusions.)
Solution · Answer
Use . Every sentential form reachable from and having a variable is with , because adds one and one , and adds one ; the final step gives with . Conversely, for apply exactly times, then exactly times, then .
Quick check
(Prove that is not context-free.)
Solution · Answer
Let be the pumping length and . Because it cannot touch both and , so at least one of the four letters is absent from , and at least one is present. Pumping with increases one count and leaves another unchanged, so the four counts are no longer all equal and the word is outside the language, a contradiction.
Quick check
(For a CFG define by reversing the right-hand side of every rule. Prove .)
Solution · Answer
Show by induction on derivation length that iff for every variable and terminal word . For length one this is the rule definition. For a longer derivation, a first rule (with terminal) in yields with ; in the rule is the reversed string, giving with each derived from , by induction. The converse is symmetric.
Quick check
(For , list the configurations of accepting .)
Solution · Answer
. The steps alternate between expansion and popping, with the expansion used three times.