47.01.05 · theoretical-cs / formal-languages-automata

Context-Free Grammars, Parse Trees, and Pushdown Automata

shipped3 tiersLean: none

Anchor (Master): Sipser 2013 Introduction to the Theory of Computation 3e (Cengage) §2.1-2.3; Hopcroft, Motwani & Ullman 2006 Introduction to Automata Theory, Languages, and Computation 3e (Pearson) §5.1-5.4 (CFG-PDA equivalence proofs, Chomsky normal form construction, Greibach normal form)

Intuition Beginner

Think of a sentence in English. "The cat sat on the mat." A grammar for English would say: a sentence is a noun phrase followed by a verb phrase. A noun phrase is "the" followed by a noun. A noun is "cat" or "mat." And so on.

The key idea is that a grammar is a collection of replacement rules. You start with a single symbol (the "start symbol") and repeatedly replace symbols according to the rules until only words remain. Different choices of which rule to apply when produce different sentences.

A context-free grammar (CFG) works this way for formal languages. Each rule says "replace this single symbol with this sequence of symbols." The word "context-free" means the rule does not depend on what other symbols are nearby — the replacement applies regardless of context.

This is more powerful than a finite automaton because the rules can nest structures inside each other. A finite automaton cannot count an arbitrary number of open parentheses and match them with close parentheses, because it has only finitely many states. But a CFG handles this with a single rule: "a balanced string is an open parenthesis, a balanced string, and a close parenthesis."

A pushdown automaton (PDA) is the machine counterpart of a CFG. It is like an NFA with a stack. The stack provides unlimited memory, but with a restricted access pattern: you can only look at and change the top of the stack. This is exactly enough to match parentheses — push on open, pop on close.

Visual Beginner

A parse tree for the string "a + b * c" using a simple arithmetic grammar:

        E
       /|\
      E  +  E
      |    /|\
      T   T  *  T
      |   |     |
      F   F     F
      |   |     |
      a   b     c

Rules: $E \to E + E ∣ E * E ∣ T$ , $T \to F$ , $F \to a ∣ b ∣ c$ .

The parse tree shows that "a + b * c" is derived by first splitting into $E + E$ , then the right $E$ splits into $T * T$ . This captures the structure that multiplication binds tighter than addition.

String	Derived?	Parse tree depth
a	$F \to a$	3
a + b	$E \to E + E \to T + T \to F + F \to a + b$	4
a + b * c	As above	5

Worked example Beginner

We build a CFG for the language of all strings of balanced parentheses over the alphabet { ( , ) }.

Rules. The grammar has one variable $S$ and the rules:

$S \to (S)$ (wrap a balanced string in parentheses)
$S \to S S$ (concatenate two balanced strings)
$S \to ε$ (the empty string is balanced)

Derive the string "()()". Start with $S$ . Apply $S \to S S$ : we get $S S$ . Apply $S \to (S)$ to the first $S$ : we get $(S) S$ . Apply $S \to ε$ to the inner $S$ : we get $() S$ . Apply $S \to (S)$ to the remaining $S$ : we get $() (S)$ . Apply $S \to ε$ : we get "()()." Done.

Derive "(()". Can we? We need a balanced string, but "(()" has two open and one close — it is not balanced. No derivation can produce it. The grammar correctly generates only balanced strings.

Parse tree for "(())". $S \to (S) \to ((S)) \to (())$ . The tree is:

    S
   /|\
  ( S )
   /|\
  ( S )
    |
    ε

Check your understanding Beginner

Formal definition Intermediate+

Definition (CFG). A context-free grammar is a 4-tuple $G = (V, Σ, R, S)$ where:

$V$ is a finite set of variables (nonterminals),
$Σ$ is a finite set of terminals with $V \cap Σ = \emptyset$ ,
$R \subseteq V \times (V \cup Σ)^{*}$ is a finite set of production rules, written $A \to α$ ,
$S \in V$ is the start variable.

Definition (derivation). For strings $α, β \in (V \cup Σ)^{*}$ , we write $α \Rightarrow β$ (alpha derives beta in one step) if $α = γ A δ$ and $β = γ ω δ$ for some $A \to ω \in R$ . The reflexive transitive closure is $\Rightarrow^{*}$ . The language generated by $G$ is $L (G) = {w \in Σ^{*} : S \Rightarrow^{*} w}$ .

Definition (parse tree). A parse tree (derivation tree) for $G$ is a rooted tree where: the root is labelled $S$ ; each internal node labelled $A$ has children labelled $α_{1}, \dots, α_{k}$ where $A \to α_{1} \dots α_{k} \in R$ ; each leaf is labelled with a terminal or $ε$ ; reading the leaves left-to-right yields the derived string.

Definition (ambiguity). A CFG $G$ is ambiguous if there exists a string $w \in L (G)$ that has two or more distinct parse trees (equivalently, two distinct leftmost derivations). A language $L$ is inherently ambiguous if every CFG for $L$ is ambiguous.

Definition (Chomsky normal form). A CFG is in Chomsky normal form (CNF) if every rule is of the form $A \to B C$ (two variables) or $A \to a$ (one terminal), and $S \to ε$ is allowed only if $ε \in L (G)$ .

Theorem (conversion to CNF). Every CFG $G$ can be converted into a CFG $G^{'}$ in Chomsky normal form with $L (G^{'}) = L (G) ∖ {ε}$ (and $L (G^{'}) = L (G)$ if $S \to ε$ is added back).

The conversion proceeds in stages: add a new start variable, eliminate $ε$ -productions (rules of the form $A \to ε$ where $A \neq = S$ ), eliminate unit productions ( $A \to B$ ), and split long right-hand sides into binary branching rules.

Definition (PDA). A pushdown automaton is a 6-tuple $P = (Q, Σ, Γ, δ, q_{0}, F)$ where:

$Q$ is a finite set of states,
$Σ$ is the input alphabet,
$Γ$ is the stack alphabet,
$δ : Q \times (Σ \cup {ε}) \times (Γ \cup {ε}) \to P (Q \times (Γ \cup {ε}))$ is the transition function,
$q_{0} \in Q$ is the start state,
$F \subseteq Q$ is the set of accept states.

A transition $δ (q, a, b) ∋ (q^{'}, c)$ means: in state $q$ , reading input $a$ (or $ε$ ), and popping $b$ from the stack (or $ε$ for no pop), go to state $q^{'}$ and push $c$ onto the stack (or $ε$ for no push).

Counterexamples to common slips

"A CFG with rules $A \to a B$ is context-free." Yes, this is a right-linear grammar, which is a special case of CFG. Right-linear grammars generate exactly the regular languages.
"CNF restricts the grammar so much that some languages cannot be expressed." CNF is a normal form: every context-free language has a CFG in CNF. The conversion may increase the number of variables but does not change the language.
"A PDA's stack can read any position." The stack is last-in-first-out (LIFO). You can only read and modify the top element. This restriction is what makes the PDA weaker than a Turing machine.

Key theorem with proof Intermediate+

Theorem (CFG = PDA). A language $L$ is context-free (generated by some CFG) if and only if it is recognised by some PDA.

Proof sketch (CFG to PDA). Given $G = (V, Σ, R, S)$ , construct a PDA $P$ with two states $q_{start}$ and $q_{loop}$ . The PDA operates as follows: push $S$ onto the stack. In $q_{loop}$ , repeatedly do one of two things. If the top of the stack is a variable $A$ , nondeterministically choose a rule $A \to α$ and replace $A$ on the stack with $α$ (pushing the symbols right-to-left so the leftmost symbol is on top). If the top of the stack is a terminal $a$ , read the next input symbol and check that it matches $a$ ; if so, pop $a$ . Accept when the input is exhausted and the stack is empty.

The PDA simulates a leftmost derivation of $G$ : each variable replacement corresponds to a grammar rule, and each terminal match corresponds to reading the input. Every accepting computation of $P$ yields a valid derivation of the input string, and every derivation yields an accepting computation.

Proof sketch (PDA to CFG). Given $P = (Q, Σ, Γ, δ, q_{0}, F)$ , construct $G$ with variables $A_{pq}$ for each pair of states $p, q \in Q$ . The variable $A_{pq}$ generates all strings that take $P$ from state $p$ with empty stack to state $q$ with empty stack. Rules: for each transition that pushes a symbol and a later transition that pops it, add a rule $A_{pq} \to a A_{r s} b$ encoding the matching push-pop pair. The start variable is $A_{q_{0}, q_{f}}$ for each $q_{f} \in F$ .

Bridge. The CFG-PDA equivalence is the foundational reason the context-free languages admit two complementary descriptions: a generative model (grammar rules) and a recognitive model (machine with stack). This builds toward the CYK parsing algorithm of 47.01.06, which uses the CNF structure for dynamic programming, and it appears again in 47.02.01 where CFL membership is shown to be in P. The central insight is that the stack provides exactly the right amount of memory to handle one level of nesting — this is exactly the computational resource that separates context-free from regular languages, and it generalises the finite-state model of 47.01.01 by adding unbounded LIFO storage. Putting these together with the pumping lemma for CFLs yields a complete characterisation of what can and cannot be expressed with nested structure.

Exercises Intermediate+

Exercise 7 (hard, symbolic).

Prove that the language $L = {a^{i} b^{j} c^{k} : i = j or j = k}$ is inherently ambiguous.

Hint

Show that any grammar for $L$ must generate strings with $i = j = k$ in two different ways: one from the $i = j$ branch and one from the $j = k$ branch.

Answer

The language $L = L_{1} \cup L_{2}$ where $L_{1} = {a^{n} b^{n} c^{m} : n, m \geq 0}$ and $L_{2} = {a^{m} b^{n} c^{n} : n, m \geq 0}$ . The intersection $L_{1} \cap L_{2} = {a^{n} b^{n} c^{n} : n \geq 0}$ is not context-free (by the CFL pumping lemma). Any CFG for $L$ must generate $L_{1}$ and $L_{2}$ using overlapping rules. For strings $a^{n} b^{n} c^{n}$ with $n \geq 1$ , the grammar must derive them from both the $L_{1}$ and $L_{2}$ branches, producing two distinct parse trees. By a formal argument (see Harrison 1978), this forces ambiguity. Rubric: full credit for identifying the intersection $L_{1} \cap L_{2}$ and arguing the forced double derivation.

Exercise 8 (hard, symbolic).

Describe the construction that converts a PDA $P$ to a CFG $G$ with $L (G) = L (P)$ . Define the variables and rules of $G$ in terms of $P$ .

Hint

Variables $A_{pq}$ represent "the set of strings taking $P$ from state $p$ with empty stack to state $q$ with empty stack."

Answer

For each pair of states $p, q \in Q$ , introduce a variable $A_{pq}$ . The start variable is $S$ with rules $S \to A_{q_{0}, q_{f}}$ for each $q_{f} \in F$ . For each state $r$ , add $A_{pq} \to A_{p r} A_{r q}$ (splitting the computation at $r$ ). For each transition $(r, t) \in δ (p, a, ε)$ that pushes symbol $X$ and each transition $(q, ε) \in δ (s, b, X)$ that pops $X$ , add $A_{pq} \to a A_{r s} b$ . For epsilon-moves, the corresponding terminal is $ε$ . The grammar generates exactly those strings for which $P$ has an accepting computation, because each derivation step encodes a matching push-pop pair on the stack. Rubric: full credit for the variable definition and the two rule types (splitting and push-pop matching).

Lean formalization Intermediate+

Mathlib has Computability.ContextFreeGrammar with a basic definition of context-free grammars and derivations, but it does not define pushdown automata, the CFG-to-PDA conversion, or Chomsky normal form. The foundational gap is the absence of a PDA structure with stack operations, the proof that CFG.language G = PDA.language (CFG.toPDA G), and the Chomsky normal form normalisation algorithm with a correctness proof showing CFG.language (CFG.toCNF G) = CFG.language G. The PDA-to-CFG direction is also absent. This unit ships without a lean_module.

Advanced results Master

Three results deepen the theory of context-free languages.

Theorem 1 (CYK algorithm). Given a CFG $G$ in Chomsky normal form and a string $w$ of length $n$ , the membership question $w \in L (G)$ can be decided in $O (n^{3} ∣ G ∣)$ time.

The algorithm uses dynamic programming. For each substring $w [i .. j]$ , compute the set of variables that can derive it. A substring of length 1 can be derived by variables $A$ with rule $A \to w [i]$ . For longer substrings, split at every position $k$ and check if there exist $A \to B C$ with $B$ deriving $w [i .. k]$ and $C$ deriving $w [k + 1.. j]$ . This places CFL recognition in P.

Theorem 2 (closure under substitution). If $L$ is context-free over $Σ = {a_{1}, \dots, a_{k}}$ and each $L_{i}$ is context-free, then the substitution $s (L) = {w_{1} \dots w_{m} : a_{i_{1}} \dots a_{i_{m}} \in L, w_{j} \in L_{i_{j}}}$ is context-free.

The proof replaces each terminal $a_{i}$ in the grammar for $L$ with the start variable of the grammar for $L_{i}$ , yielding a CFG for the substituted language. This closure property implies closure under union, concatenation, and star, but not intersection.

Theorem 3 (Pumping lemma for CFLs). If $L$ is context-free, then there exists $p$ (the pumping length) such that any $s \in L$ with $∣ s ∣ \geq p$ can be written $s = uv x y z$ with $∣ v y ∣ > 0$ , $∣ v x y ∣ \leq p$ , and $u v^{i} x y^{i} z \in L$ for all $i \geq 0$ ^{[Sipser §2.3]}.

The proof uses the self-embedding property of parse trees: a parse tree for a sufficiently long string must repeat a variable on some root-to-leaf path, and the subtree rooted at the lower occurrence can be pumped.

Synthesis. The CFG-PDA equivalence is the foundational reason the context-free languages form a robust class with both generative and recognitive characterisations. The central insight is that one level of unbounded nesting — captured by the stack in a PDA or by recursive rules in a CFG — is exactly the right amount of structure to go beyond regularity while remaining decidable and efficiently parsable. This builds toward the CYK algorithm, which exploits the CNF structure for polynomial-time parsing, and it appears again in the Chomsky hierarchy where context-free languages sit between regular and context-sensitive. Putting these together with the DFA-NFA equivalence of 47.01.01 and the subset construction of 47.01.02 reveals a pattern: each level of the hierarchy adds a specific computational resource (deterministic states, nondeterministic states, a stack, a tape) and this is exactly what defines the boundary between adjacent levels.

Full proof set Master

Proposition 1 (CFG to PDA construction correctness). Let $G = (V, Σ, R, S)$ be a CFG. The PDA $P$ constructed with states ${q_{1}, q_{2}, q_{3}}$ , stack alphabet $V \cup Σ \cup {$}$ , and transitions that (i) push $$$ then $S$ onto the stack in $q_{1}$ , (ii) loop in $q_{2}$ replacing variables by rule right-hand sides and matching terminals, and (iii) accept in $q_{3}$ by popping $$$ , satisfies $L (P) = L (G)$ .

Proof. ( $L (G) \subseteq L (P)$ .) For any $w \in L (G)$ , there is a leftmost derivation $S \Rightarrow α_{1} \Rightarrow α_{2} \Rightarrow \dots \Rightarrow w$ . The PDA simulates this derivation: when a variable $A$ is on top of the stack, it applies the same rule $A \to γ$ used in the derivation. When a terminal $a$ is on top, it matches the next input symbol. Since the derivation produces $w$ , the PDA consumes $w$ and empties its stack.

( $L (P) \subseteq L (G)$ .) Any accepting computation of $P$ starts with $S$ on the stack and ends with an empty stack after reading the entire input. Each time $P$ replaces a variable $A$ by a rule right-hand side, this corresponds to one derivation step. The sequence of replacements yields a derivation $S \Rightarrow^{*} w$ . $□$

Proposition 2 (conversion to Chomsky normal form preserves the language). Let $G$ be a CFG. The grammar $G^{'}$ obtained by (i) adding a new start variable, (ii) eliminating $ε$ -productions for non-start variables, (iii) eliminating unit productions, and (iv) splitting long right-hand sides into binary rules satisfies $L (G^{'}) = L (G)$ .

Proof. Each step preserves the language. Step (i) adds $S_{0} \to S$ without changing derivable strings. Step (ii) removes $A \to ε$ for $A \neq = S_{0}$ by adding, for each rule $B \to α A β$ , the rule $B \to α β$ (simulating the nullable $A$ ). This preserves all non-empty derivations and handles $ε$ through $S_{0}$ . Step (iii) removes $A \to B$ by transitively replacing with the rules of $B$ . Step (iv) replaces $A \to A_{1} A_{2} \dots A_{k}$ with a chain $A \to A_{1} B_{1}, B_{1} \to A_{2} B_{2}, \dots, B_{k - 2} \to A_{k - 1} A_{k}$ using fresh variables. Each step preserves the set of derivable terminal strings. $□$

Proposition 3 (PDA to CFG construction correctness). Let $P$ be a PDA. The grammar $G$ with variables $A_{pq}$ and rules as described above satisfies $L (G) = L (P)$ .

Proof. By double inclusion. For $w \in L (P)$ , the accepting computation of $P$ decomposes into nested push-pop pairs on the stack. Each pair from state $p$ to state $q$ (pushing symbol $X$ at state $r$ , popping $X$ at state $s$ ) corresponds to a rule $A_{pq} \to a A_{r s} b$ in $G$ . The nesting structure of push-pop pairs mirrors the parse tree structure. Conversely, every derivation in $G$ encodes a valid PDA computation because each rule corresponds to a genuine push-pop matching. $□$

Connections Master

47.01.01 — DFAs recognise the regular languages; PDAs extend DFAs with a stack to recognise the context-free languages, a strict superset.
47.01.02 — The subset construction shows DFAs and NFAs have equal power; the CFG-PDA equivalence is the analogous result for the context-free level of the Chomsky hierarchy.
47.01.06 — The CYK algorithm uses the Chomsky normal form structure defined here for polynomial-time parsing of context-free languages.
47.02.01 — CFL membership (the parsing problem) is in P via the CYK algorithm; the relationship between CFL recognition and complexity classes connects formal languages to computational complexity.

Historical & philosophical context Master

Context-free grammars were introduced by Noam Chomsky in 1956 as part of his hierarchy of formal grammars, originally developed to model the syntax of natural languages ^{[Chomsky 1956]}. Chomsky defined four levels of grammars (type 0 through type 3), with context-free grammars at type 2, and proved that each level generates a strictly larger class of languages than the one below.

The equivalence between CFGs and PDAs was established independently by several researchers in the early 1960s. The PDA model was formalised by A. G. Oettinger in 1961 and independently by M. P. Schutzenberger. The CFG-to-PDA construction, where the PDA simulates a leftmost derivation using its stack, is sometimes called the "top-down parser" construction because it mirrors recursive-descent parsing used in compiler design.

Chomsky normal form was introduced by Chomsky as part of his study of the algebraic properties of context-free grammars. The normal form is essential for the CYK algorithm (Cocke, Younger, and Kasami, independently discovered circa 1965-1967) and for proving the pumping lemma for context-free languages. The fact that any CFG can be put into CNF without changing its language is a structural result analogous to the subset construction for NFAs: it shows that the apparently complex generality of CFG rules can be reduced to a simple canonical form ^{[Sipser §2.1]}.

Bibliography Master

@book{sipser2013,
  author    = {Sipser, Michael},
  title     = {Introduction to the Theory of Computation},
  edition   = {3rd},
  publisher = {Cengage Learning},
  year      = {2013},
}
@book{hopcroft2006,
  author    = {Hopcroft, John E. and Motwani, Rajeev and Ullman, Jeffrey D.},
  title     = {Introduction to Automata Theory, Languages, and Computation},
  edition   = {3rd},
  publisher = {Pearson},
  year      = {2006},
}
@article{chomsky1956three,
  author  = {Chomsky, Noam},
  title   = {Three Models for the Description of Language},
  journal = {IRE Transactions on Information Theory},
  volume  = {2},
  number  = {3},
  pages   = {113--124},
  year    = {1956},
}

Prerequisites

47.01.01

Tier anchors

beginner: Sipser 2013 Introduction to the Theory of Computation 3e (Cengage) §2.1 (context-free grammars as rewrite rules that generate strings, parse trees showing the derivation structure, balanced parentheses as a canonical example)
intermediate: Sipser 2013 Introduction to the Theory of Computation 3e (Cengage) §2.1-2.3 (formal CFG definition, parse trees and ambiguity, Chomsky normal form, pushdown automata, equivalence of CFGs and PDAs)
master: Sipser 2013 Introduction to the Theory of Computation 3e (Cengage) §2.1-2.3; Hopcroft, Motwani & Ullman 2006 Introduction to Automata Theory, Languages, and Computation 3e (Pearson) §5.1-5.4 (CFG-PDA equivalence proofs, Chomsky normal form construction, Greibach normal form)

References

Sipser, M. — Introduction to the Theory of Computation (3rd ed.) · Cengage (2013). Section 2.1 defines a context-free grammar as a 4-tuple $G = (V, Σ, R, S)$ where $V$ is a finite set of variables, $Σ$ is a finite set of terminals, $R \subseteq V \times (V \cup Σ)^{*}$ is a finite set of rules, and $S \in V$ is the start variable; a string $w \in Σ^{*}$ is derived by repeated application of rules $A \to α$ , starting from $S$ ; the language $L (G) = {w \in Σ^{*} : S \Rightarrow^{*} w}$ is the language generated by $G$ ; Section 2.2 defines parse trees (derivation trees), ambiguity (a grammar is ambiguous if some string has two distinct leftmost derivations), and Chomsky normal form (all rules are $A \to B C$ or $A \to a$ ); Section 2.3 defines pushdown automata as NFAs with an unbounded stack, and proves $L (G)$ is context-free iff it is recognised by some PDA.
Hopcroft, J. E., Motwani, R. & Ullman, J. D. — Introduction to Automata Theory, Languages, and Computation (3rd ed.) · Pearson (2006). Sections 5.1-5.4 develop the CFG-PDA equivalence: given a CFG $G$ , construct a PDA that guesses a leftmost derivation using the stack; given a PDA $P$ , construct a CFG whose variables encode pairs of PDA states and whose rules simulate stack operations. The conversion to Chomsky normal form is given as an algorithm that eliminates epsilon-productions, unit productions, and useless symbols.

Estimated time

beginner: 15m
intermediate: 40m
master: 75m