Visual walkthrough — Equivalence of CFGs and PDAs

---

Step 1 — What a stack actually is (from zero)

WHAT. We draw a stack as a vertical column. The bottom plate went on first; the top plate is where all the action happens.

WHY this object and not a list or array? Because a stack answers exactly one question — "what is the single most recent unfinished thing I owe?" — and forgets everything below it until that top is cleared. That "one unfinished thing at a time, deepest last" behaviour is precisely how nested things (boxes in boxes, brackets in brackets) close.

PICTURE. The left column shows a push; the right column shows a pop. Watch the top move.

Recall Why "top only"?

Why can a stack read only its top plate? ::: Because that top plate is the innermost unfinished job; you cannot finish an outer job until the inner one closes — same as brackets.

---

Step 2 — A derivation is already a stack (the key sighting)

WHAT. We expand $S\Rightarrow aSb\Rightarrow aaSbb\Rightarrow aabb$ and draw the nesting as brackets.

WHY. This is the whole theorem in embryo. The reason a machine with one stack can imitate a grammar is that the grammar's own recursion is a bracket structure, and brackets are what a stack tracks. Nothing deeper is going on than this matching of shapes.

PICTURE. Each expansion opens a new bracket pair a[ ]b; the deepest bracket is the one we resolve first — exactly the top of a stack.

$\underset{\text{outer open}}{\underbrace{a}}\underset{\text{inner pair}}{\underbrace{a\underset{\text{inner }S\to \epsilon }{\underbrace{\epsilon }}b}}\underset{\text{outer close}}{\underbrace{b}}$

• $a,b$ = terminals (real output characters).
• $\epsilon$ = "empty string", the base case where the innermost $S$ produces nothing.
• The brace nesting = the stack depth at that moment.

---

Step 3 — Turning the grammar into a one-state PDA

WHAT. Two move-types, straight from the grammar:

$\underset{\text{state }q,\text{read nothing},\text{pop }A}{\underbrace{\delta (q,\epsilon ,A)}}\ni \underset{\text{stay }q,\text{push RHS }\alpha }{\underbrace{(q,\alpha )}}\text{for each rule }A\to \alpha$

$\underset{\text{read input }a,\text{pop stack }a}{\underbrace{\delta (q,a,a)}}\ni \underset{\text{push nothing}}{\underbrace{(q,\epsilon )}}\text{for each terminal }a$

WHY one state? The grammar has no "control state" — every scrap of progress lives in the sentential form (the half-finished string). We store that whole sentential form on the stack, so the machine needs no memory in its state at all. One state suffices.

WHY does expansion read $\epsilon$? Applying a grammar rule produces no input character; it only rearranges what we still owe. Reading a real symbol happens only in the second move, when a promised terminal meets the actual input.

PICTURE. Top of stack decides which move is even legal: a variable on top → only expansion; a terminal on top → only matching.

---

Step 4 — Run it on $aabb$ (the film strip)

WHAT. We trace the PDA move-by-move on the string $aabb$. Stack top is drawn at the left.

WHY show every row? Because acceptance is a path, and we must witness that the guesses (which rule to expand) can be made so the stack empties exactly as the input ends.

PICTURE. Each frame = the stack after one move; the arrow labels which move fired.

Step	Move (why)	Unread input	Stack (top-left)
0	start	$aabb$	$S$
1	expand $S\to aSb$	$aabb$	$aSb$
2	match $a$	$abb$	$Sb$
3	expand $S\to aSb$	$abb$	$aSbb$
4	match $a$	$bb$	$Sbb$
5	expand $S\to \epsilon$	$bb$	$bb$
6	match $b$	$b$	$b$
7	match $b$	$\epsilon$	(empty) → accept

Step 5 is the guess: nondeterminism tries $S\to \epsilon$ here, and this guess is the one that works.

---

Step 5 — The invariant that proves it (one picture)

WHAT. Read the read-part and the stack-part as one string; that concatenation is always something $S$ can derive so far.

WHY it clinches Direction 1. When input is exhausted and the stack is empty, both sides say "$S{\Rightarrow }^{\ast }w$" — the whole input was genuinely derived. Conversely any derivation gives an accepting run. So $L(M)=L(G)$.

PICTURE. A dotted seam splits "already read" (left, teal) from "still on stack" (right, orange); glue them and you get the sentential form (plum) above.

---

Step 6 — The reverse direction: reading a run as brackets

WHAT. We first normalise the PDA so every move either pushes exactly one symbol or pops exactly one. Then a balanced run looks like a bracket string, and each variable expands like a bracket.

WHY this definition? A push that waits and is later popped is literally a matching bracket pair. A grammar variable expanding to "open · middle · close" is the same shape. Matching the shapes gives the grammar for free.

PICTURE. Stack height plotted over time (a "mountain profile"). $A_{pq}$ = one full mountain returning to the baseline.

---

Step 7 — The two rules, and why they are ALL the cases

WHAT. Term-by-term on the match rule $A_{pq}\to a{A}_{rs}b$:

• $a$ = the input read when the machine pushes symbol $t$, moving $p\to r$.
• $b$ = the input read when the machine pops that same $t$, moving $s\to q$.
• $A_{rs}$ = whatever happened above $t$ while it sat on the stack — a balanced sub-run from $r$ to $s$.

WHY exactly two working shapes? Look at the first symbol pushed in a balanced run. There are only two fates for it:

1. It is popped only at the very end → one outer bracket wraps everything → match rule.
2. It is popped strictly before the end → the stack touches baseline mid-run at some state $r$ → the run splits into two balanced halves → split rule.

No third possibility exists, so the rules generate exactly $L(M)$.

PICTURE. Two mountain profiles side by side: left = one big arch (match), right = two arches meeting the baseline (split).

For our example PDA (state $p$ pushes $A$ per $a$; pops $A$ per $b$ into $q$; pops $A$ per $b$ staying in $q$), the match rule gives $A_{pq}\to a{A}_{pq}b$ and $A_{pp}\to \epsilon$ — literally $S\to aSb\mid \epsilon$ again. The two constructions are inverse in spirit.

---

The one-picture summary

WHAT. One figure that stacks all four viewpoints of the SAME string $aabb$: the parse tree, the bracket nesting, the PDA stack film, and the balanced mountain profile. Read any column — they are the same object.

Compare with Leftmost Derivations and Parse Trees and Chomsky Normal Form (the normal form that makes the balanced-run argument clean). The one-stack limit is what keeps us inside Closure Properties of CFLs and short of Turing Machines — two stacks would jump the fence.

Recall Feynman: tell it to a friend in plain words

A grammar is a recipe for nesting boxes: to make a box you may put a smaller box inside and then close the lid, and the innermost box must be finished before any outer lid closes. A stack machine is a kid holding a pile of plates: every time the recipe opens a box the kid puts a plate down; every time a real letter is matched the kid takes the matching plate off. Because you must always deal with the top plate first — the innermost box first — the pile of plates and the nested boxes rise and fall in perfect step. Reading the run forward, the plate you set down first is the plate you lift last: one opening bracket, one closing bracket, with a smaller balanced run sitting on top of it. That single fact — "first plate down is last plate up" — is why one stack equals grammar recursion, and why two stacks would be too much and turn the kid into a full computer.

Recall Active recall — cover the answers

• What single shape do a derivation and a stack share? ::: nesting / matched brackets.
• In CFG→PDA, when is input read? ::: only on the match move (a terminal on top meets the input); expansion is an $\epsilon$-move.
• What does "balanced run" mean for $A_{pq}$? ::: same start and end stack height, never dipping below the start.
• Why exactly two rule schemas in PDA→CFG? ::: the first pushed symbol is popped either at the very end (match) or earlier (split); no third case.
• Why does the equivalence fail with two stacks? ::: two stacks simulate a Turing machine, escaping the context-free class.