Pushdown automata (PDA) — configuration, acceptance by empty stack - final state: Visual walkthrough

This page is a visual companion to the parent PDA note. If you've seen Nondeterministic Finite Automata, picture that machine — then imagine handing it a stack of plates.

Step 1 — A machine with a memory made of plates

WHAT. Before any formula, meet the object. A PDA is a small brain (finitely many moods, called states) plus one tall column of stacked plates — the stack. It reads a strip of letters left to right.

WHY. The parent note's headline is "a PDA is an NFA bolted onto a stack." A plain finite machine can only remember which of finitely many moods it's in — it can't count how many a's it saw if there could be a million. A stack fixes exactly that: you can add a plate for each a, and the pile grows as tall as you need. That unbounded-but-LIFO (Last In, First Out — you can only touch the top plate) memory is the one thing that lifts a PDA above regular languages.

PICTURE. The red column is the stack. Only the top plate is reachable. The input strip runs left→right; a reading head sits over the next unread letter.

Step 2 — One legal move, drawn term by term

WHAT. A single move takes one configuration to the next. The parent writes it as the yields relation $⊢$ (read "yields"): if the rulebook allows $(p, γ)$ as a response to seeing state $q$ , input letter $a$ , top plate $A$ , then $(q, a w, A β) ⊢ (p, w, γ β)$

WHY term by term — this is the heartbeat of the machine, so we annotate every piece:

$q \to p$ : the mood changes.

$a w \to w$ : the letter $a$ is consumed — it vanishes from the front of the unread input.

$A β \to γ β$ : the top plate $A$ is replaced by the string $γ$ ; everything below ( $β$ ) is untouched.

PICTURE. Watch the only plate that moves: the red top one. Below it, $β$ sits frozen. The letter $a$ is crossed off the strip.

Step 3 — Watch a real run empty its stack: $a^{n} b^{n}$

WHAT. Take the language ${a^{n} b^{n} ∣ n \geq 1}$ (some a's then equally many b's). The plan: push one plate per a, pop one plate per b. If the counts match, the plates vanish together. We trace the input $aabb$ .

WHY this language. It is the smallest thing a finite machine cannot do — it must count. The stack height is the count. When we finish, the stack tells us whether the counts balanced.

PICTURE. Read the run left→right; the red number tracks stack height. It rises on a, falls on b, and touches the floor at the very end.

$(q, aabb, Z_{0}) ⊢ (q, abb, A Z_{0}) ⊢ (q, bb, AA Z_{0}) ⊢ (q, b, A Z_{0}) ⊢ (q, ε, Z_{0}) ⊢ (q, ε, ε) ✓$

Term by term on the last step $(q, ε, Z_{0}) ⊢ (q, ε, ε)$ : input is already $ε$ (all read), the bottom marker $Z_{0}$ is popped (replaced by $ε$ ), stack becomes truly empty. Here $Z_{0}$ is the initial stack symbol, the single plate that sits on the floor before anything happens — our "bottom marker."

Step 4 — The FIRST way to say "you passed": empty the stack

WHAT. Acceptance by empty stack: the input is accepted exactly when, after reading everything, no plates remain. $L_{N} (M) = {w ∣ (q_{0}, w, Z_{0}) ⊢^{*} (q, ε, ε)}$ Here $⊢^{*}$ means "in zero or more steps," $q_{0}$ is the start mood, and the final $ε, ε$ means no input left, no plates left. The mood $q$ at the end is irrelevant.

WHY it works. In Step 3 the stack hit zero precisely when a's balanced b's. The emptiness of the stack is the certificate that the structure matched.

PICTURE. Two runs side by side: aabb drains to an empty floor (accept); aab leaves one red plate stranded (reject — one unmatched a).

Step 5 — The SECOND way: land in a happy mood (final state)

WHAT. Acceptance by final state: pick a special set $F$ of "happy" moods. Accept iff you finish reading input in some mood inside $F$ — whatever is on the stack. $L_{F} (M) = {w ∣ (q_{0}, w, Z_{0}) ⊢^{*} (q, ε, γ), q \in F}$ The $γ$ here is any leftover stack; it is simply ignored.

WHY the difference matters. For $a^{n} b^{n}$ we don't dump $Z_{0}$ ; instead, when only the marker $Z_{0}$ remains we hop to a happy mood $q_{f}$ and stop. The plates can stay on the table.

PICTURE. Same drain, but the accept test is a green flag on the mood, and the leftover $Z_{0}$ plate is greyed to show "we don't care about it."

Step 6 — Convert empty-stack → final-state (the fresh floor trick)

WHAT. Given a machine $N$ that accepts by empty stack, build $F$ that accepts by final state and recognizes the same language.

WHY it's subtle. If we just said "accept when the stack empties," we can't see emptiness from inside — the moment the last plate leaves, there's nothing to trigger a transition. The fix: slip a brand-new bottom plate $X_{0}$ under everything at the start. When $N$ empties its plates, $X_{0}$ becomes visible — that exposure is our signal to jump to a happy mood.

PICTURE. The red $X_{0}$ is the new floor. $N$ 's real stack sits above it. When $N$ 's plates are gone, $X_{0}$ pokes out and we flip to $q_{f}$ .

Construction, annotated:

Add fresh start mood $q_{0}^{'}$ with $δ (q_{0}^{'}, ε, X_{0}) = {(q_{0}, Z_{0} X_{0})}$ — push $N$ 's marker $Z_{0}$ above our new floor $X_{0}$ , then run $N$ .
Add happy mood $q_{f}$ , with $δ (q, ε, X_{0}) = {(q_{f}, X_{0})}$ for every mood $q$ — whenever $X_{0}$ surfaces (⇒ $N$ 's stack was empty), go happy.
Set $F = {q_{f}}$ .

The floor $X_{0}$ guarantees $N$ can never accidentally reach a truly empty stack early — the only bare- $X_{0}$ moment is exactly when $N$ genuinely emptied.

Step 7 — Convert final-state → empty-stack (dump everything)

WHAT. Now the reverse: given $F$ accepting by final state, build $N$ that empties its stack on the same strings.

WHY. To make emptiness mean "accept," we must clear all plates — but only after truly reaching a happy mood, and never before. Again a fresh floor $X_{0}$ protects us: $F$ 's own machine might momentarily empty its plates mid-run without being in $F$ ; the extra floor stops that from counting.

PICTURE. From any happy mood, a red cascade of $ε$ -moves pops plate after plate until nothing (not even $X_{0}$ ) is left.

Construction, annotated:

New floor: $δ (q_{0}^{'}, ε, X_{0}) = {(q_{0}, Z_{0} X_{0})}$ — run $F$ above the protective floor.
Add dump mood $q_{d}$ . For every $q \in F$ and every stack symbol $A$ : $δ (q, ε, A) = {(q_{d}, ε)}$ enters dumping, then $δ (q_{d}, ε, A) = {(q_{d}, ε)}$ for every $A$ (including $X_{0}$ ) — pop everything, floor and all, reaching empty stack.

Because $X_{0}$ only ever gets popped inside the dump phase (entered only from a genuine final state), the two modes accept identical strings.

The one-picture summary

WHAT. One diagram: the same PDA core, two accept sockets. Left socket lights up when the stack floor is bare (empty stack). Right socket lights up when the mood is happy (final state). The two convertibility arrows show each can be rebuilt as the other — so both recognize exactly the context-free languages.

Recall Feynman: the whole walkthrough in plain words

A robot reads letters and holds a stack of plates; it can only touch the top plate. To check as match bs, it puts a plate down for each a and lifts one off for each b. There are two ways it can announce "you passed." One: it lifts the last plate off — no plates left means the counts balanced ("empty = exhausted"). Two: it finishes in a smiley mood, plates or no plates ("final = feeling"). Do they have equal power? Yes. If your robot uses the empty-plate rule, I slip an extra floor-plate underneath; when your real plates are gone, my floor pokes out and I make the robot smile — that's the empty→final rebuild. If your robot uses the smiley rule, I let it smile first, then have it toss every plate (floor included) off the table — that's the final→empty rebuild. The extra floor-plate is the trick that stops the robot from accidentally emptying or smiling too early. Same robot, same passing strings, two ways to say "passed."

Flashcards

A configuration (ID) is which triple?

(q, w, γ)

= current state, unread input, full stack with top written leftmost.

Write the one-step yields rule when

(p, γ) \in δ (q, a, A)

(q, a w, A β) ⊢ (p, w, γ β)

γ = A β

, which plate is on top?

A

— the top is written leftmost.

Define acceptance by empty stack.

w

accepted iff

(q_{0}, w, Z_{0}) ⊢^{*} (q, ε, ε)

; final states ignored.

Define acceptance by final state.

w

accepted iff

(q_{0}, w, Z_{0}) ⊢^{*} (q, ε, γ)

with

q \in F

; stack ignored.

Why add a fresh marker

X_{0}

in conversions?

So the simulated machine never empties (or "passes") accidentally —

X_{0}

surfaces only at the true accept moment.

Empty→final: what triggers the happy mood?

The fresh floor

X_{0}

becoming exposed, i.e. the original stack is empty.

Final→empty: what does the dump phase do?

From a final state,

ε

-pop every plate including

X_{0}

until the stack is truly empty.