PDAs and Grammars Are Equivalent

The headline: two descriptions, one class of languages

By now you have met two very different ways of describing a context-free language. One is a context-free grammar, a generator: it sits and produces strings by rewriting variables, the way you saw in the grammars rung. The other is the pushdown automaton from guides 1 and 2 of this rung, a recognizer: it reads a string left to right, pushing and popping a stack, and either accepts or rejects. The central theorem of this rung is that these two descriptions cover exactly the same languages. A language has a context-free grammar if and only if some PDA recognizes it. This is the equivalence of PDAs and context-free grammars.

Why should you care about a theorem that says two things are equal? Because each side is good at something the other is clumsy at. When you want to specify a language — describe the legal nesting of a programming language, say — a grammar is the natural pen. When you want to check membership by scanning a string once, an automaton with a stack is the natural machine. The equivalence lets you flip freely between them: design with a grammar, then turn the crank to get a recognizer for free, which is precisely what a parser is. The whole next rung on parsing rests on this bridge.

Grammar to PDA: let the stack run the derivation

The easier direction is turning a grammar into a PDA, and the idea is beautifully direct: build a machine whose stack carries out a leftmost derivation of the grammar. Recall from the grammars rung that a leftmost derivation always rewrites the leftmost variable first. At any moment the part of the derivation that is still 'unfinished' is a string of terminals and variables — a sentential form. The PDA keeps the not-yet-matched tail of that form on its stack, with the leftmost symbol on top, and works it down by matching terminals against the input and expanding variables by the rules.

1. Set up. The PDA has essentially one working state. Push the grammar's start symbol onto the stack (above the bottom marker), so the stack begins holding exactly 'the whole derivation still to do'.
2. Expand a variable. If a variable A is on top of the stack, pop it and push the right-hand side of some rule A -> alpha, leftmost symbol on top. This move reads no input — it is an epsilon move — and this is exactly where the PDA guesses which rule to apply.
3. Match a terminal. If a terminal a is on top of the stack and the next input symbol is also a, pop the a and advance the input. If the top terminal does not match the input, this branch is stuck and dies.
4. Accept. When the input is fully consumed and the stack has emptied back to the bottom marker, every guess turned out consistent — accept by empty stack. If no run reaches that state, reject.

Step 2 is where nondeterminism earns its keep. When a variable A has several rules, the PDA does not know which one this particular string needs, so it branches and tries them all in parallel — cloning itself, in the NFA picture. A string is accepted exactly when some sequence of rule-guesses spells out a real leftmost derivation that also matches the input. So the accepting runs of the PDA are in one-to-one correspondence with leftmost derivations in the grammar. That correspondence is the whole proof of this direction: the machine accepts a string if and only if the grammar can derive it. Empty-stack acceptance is the natural fit here, because the stack empties exactly when the derivation is complete.

Grammar:   S -> a S b | epsilon            (the language a^n b^n)

PDA built from it (single state q, accept by empty stack):
  push S to start
  delta(q, epsilon, S) = { push 'aSb' ,  push '' }   <- guess a rule
  delta(q, a, a) = pop                                <- match terminal a
  delta(q, b, b) = pop                                <- match terminal b

Run on input  a a b b  (top of stack on the LEFT):

  input left   stack         move
  ----------   -----------   -------------------------------
  a a b b      S             expand  S -> a S b
  a a b b      a S b         match a  (pop a, read a)
    a b b      S b           expand  S -> a S b
    a b b      a S b b        match a
      b b      S b b         expand  S -> epsilon
      b b      b b           match b
        b      b             match b
   (empty)     (empty)       ACCEPT

PDA to grammar: the harder, cleverer direction

The reverse direction — every PDA has an equivalent grammar — is the one that looks impossible at first and rewards a careful idea. The trouble is that a PDA's behavior is entangled: what it can do depends jointly on its current state and what is sitting on the stack, and the stack can grow without bound. We tame this by inventing a variable for each self-contained stack episode: a variable written A(p, X, q) whose promise is 'the strings that drive the PDA from state p, with X on top of the stack, to state q while popping that exact X off and never dipping below it in between'. Read it as 'the net effect of one push-then-matching-pop, from p to q'.

With that promise fixed, the grammar rules almost write themselves by mirroring the PDA's moves. If a single move pops X (going from p to q while reading a), that is a base case: A(p, X, q) -> a. If a move pushes a symbol — say it reads a, goes from p to r, and replaces X with two symbols Y Z — then clearing X means first clearing Y (ending in some intermediate state s) and then clearing Z (ending in q). That becomes the rule A(p, X, q) -> a A(r, Y, s) A(s, Z, q), with the machine guessing the intermediate state s. The start symbol expands to A(start, bottom, f) for each accepting state f. The grammar's derivations now trace, move for move, the PDA's accepting runs.

Do not memorize the index gymnastics — memorize the shape of the idea. A grammar variable stands for a complete bracketed episode of stack life, where something is pushed and later matched by its own pop, with the state at the open and the state at the close recorded in the variable's name. A pushed symbol that is later popped is the automaton's version of a matched pair of brackets, and the grammar's nested variables are the automaton's nested stack. That is the deep reason the two models coincide: the stack does last-in-first-out matching, and grammar recursion does nested matching, and those are the same operation seen from two sides.

Determinism: where finite automata and PDAs part ways

Here is the twist that makes this rung worth climbing, and it is genuinely surprising if you remember the finite-automaton story. For finite automata, the subset construction showed that nondeterminism buys nothing in power: every NFA has an equivalent DFA, and a deterministic finite automaton recognizes exactly the same regular languages. You might expect the same here. It is false. The deterministic pushdown automaton is strictly weaker than the nondeterministic one. There are context-free languages that no deterministic PDA can recognize.

Why the difference? A DFA can run all of an NFA's parallel guesses at once by tracking the set of states it might be in — finitely many subsets, so a bigger but still finite machine simulates the guessing. A PDA cannot pull the same stunt, because its 'configuration' includes the entire stack, and there is no bound on stack contents to fold into finitely many states. The classic example of a language that needs the guessing is the even-length palindromes over {a, b} — strings that read the same forwards and backwards. A nondeterministic PDA pushes the first half and pops it against the second, but it must guess where the midpoint is. A deterministic machine, reading left to right with no foresight, cannot know when to switch from pushing to popping.