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

This page is a complete tour of every situation a PDA problem can throw at you. Before we work anything, we lay out a matrix of case-classes. Then each worked example is tagged with the cell it fills, so by the end you have seen every corner — accept, reject, empty stack vs final state, degenerate empty input, "stack never empties" traps, nondeterministic guessing, and an exam twist.

If any symbol below feels unfamiliar, go back to the parent topic first — everything here reuses its 7-tuple $M = (Q, Σ, Γ, δ, q_{0}, Z_{0}, F)$ , its configuration triple $(q, w, γ)$ , and its yields relation $⊢$ .

The scenario matrix

Every PDA exercise lives in one of these cells. The examples that follow cover all ten.

#	Case class	What makes it tricky	Filled by
C1	Accept by empty stack, matched input	must pop $Z_{0}$ too	Ex 1
C2	Accept by final state, junk left on stack	stack ignored	Ex 2
C3	Reject — input runs out with symbols still on stack	no accepting snapshot	Ex 3
C4	Reject — stack empties too early / no move available	dead configuration	Ex 3
C5	Degenerate: empty input $ε$	does $n = 0$ count?	Ex 4
C6	Nondeterminism essential: guess a midpoint	one guess-path accepts	Ex 5
C7	Two counters at once ( $a^{n} b^{2 n}$ )	push/pop in bulk	Ex 6
C8	Conversion empty-stack $\to$ final-state (marker $X_{0}$ )	avoid early emptying	Ex 7
C9	Real-world word problem: balanced brackets	practical parsing	Ex 8
C10	Exam twist: same string, opposite verdict under the two modes	modes really differ	Ex 9

Ex 1 — C1 · $a^{n} b^{n}$ accepted by empty stack

The rules again (top of stack written leftmost):

$δ (q, a, Z_{0}) = {(q, A Z_{0})}$
$δ (q, a, A) = {(q, AA)}$
$δ (q, b, A) = {(q, ε)}$
$δ (q, ε, Z_{0}) = {(q, ε)}$

Steps (one $⊢$ -move per line, each labelled with the rule it uses):

$(q, aaabbb, Z_{0}) ⊢ (q, aabbb, A Z_{0})$ — Why this step? rule 1: first $a$ hits $Z_{0}$ , push $A$ on top.
$(q, aabbb, A Z_{0}) ⊢ (q, abbb, AA Z_{0})$ — Why? rule 2: second $a$ pushes another $A$ (count $\to 2$ ).
$(q, abbb, AA Z_{0}) ⊢ (q, bbb, AAA Z_{0})$ — Why? rule 2 again: third $a$ pushes another $A$ (count $\to 3$ ).
$(q, bbb, AAA Z_{0}) ⊢ (q, bb, AA Z_{0})$ — Why? rule 3: first $b$ pops one $A$ (count $\to 2$ ).
$(q, bb, AA Z_{0}) ⊢ (q, b, A Z_{0})$ — Why? rule 3: second $b$ pops one $A$ (count $\to 1$ ).
$(q, b, A Z_{0}) ⊢ (q, ε, Z_{0})$ — Why? rule 3: third $b$ pops the last $A$ (count $\to 0$ ).
$(q, ε, Z_{0}) ⊢ (q, ε, ε)$ — Why? rule 4: input empty, only $Z_{0}$ remains, pop it on $ε$ -input. Stack empty = accept.

Ex 2 — C2 · Final-state accept with junk on the stack

Steps (one $⊢$ -move per line):

$(q, aabb, Z_{0}) ⊢ (q, abb, A Z_{0})$ — Why? rule 1: first $a$ pushes an $A$ .
$(q, abb, A Z_{0}) ⊢ (q, bb, AA Z_{0})$ — Why? rule 2: second $a$ pushes another $A$ .
$(q, bb, AA Z_{0}) ⊢ (q, b, A Z_{0})$ — Why? rule 3: first $b$ pops one $A$ .
$(q, b, A Z_{0}) ⊢ (q, ε, Z_{0})$ — Why? rule 3: second $b$ pops the last $A$ .
$(q, ε, Z_{0}) ⊢ (q_{f}, ε, Z_{0})$ — Why this step? rule $4^{'}$ : move to $q_{f}$ on $ε$ -input without popping. Input exhausted and $q_{f} \in F$ → accept.

Ex 3 — C3 & C4 · Two ways to reject

Case C3 — $aab$ (surplus on stack).

$(q, aab, Z_{0}) ⊢ (q, ab, A Z_{0})$ — Why? rule 1: first $a$ pushes an $A$ .
$(q, ab, A Z_{0}) ⊢ (q, b, AA Z_{0})$ — Why? rule 2: second $a$ pushes another $A$ .
$(q, b, AA Z_{0}) ⊢ (q, ε, A Z_{0})$ — Why? rule 3: the single $b$ pops one $A$ . Now input is empty but stack is $A Z_{0}$ , not $ε$ .
Could rule 4 fire? No — it needs $Z_{0}$ on top, but $A$ is on top. No $ε$ -move applies. Stuck with a non-empty stack ⇒ reject. (Cell C3.)

Case C4 — $abb$ (pop past the marker).

$(q, abb, Z_{0}) ⊢ (q, bb, A Z_{0})$ — Why? rule 1: one $a$ pushes one $A$ .
$(q, bb, A Z_{0}) ⊢ (q, b, Z_{0})$ — Why? rule 3: first $b$ pops the lone $A$ . Stack is now just $Z_{0}$ .
Second $b$ with $Z_{0}$ on top: is there a rule $δ (q, b, Z_{0})$ ? No. The machine is in a dead configuration with input left. Reject. (Cell C4.)

Ex 4 — C5 · The degenerate empty input $ε$

On the Ex 1 machine (which we'll show actually targets $n \geq 0$ ).

Start: $(q, ε, Z_{0})$ — input already empty. Why look here? The empty string means we never read a letter.
Only $ε$ -rule available is rule 4: $δ (q, ε, Z_{0}) = {(q, ε)}$ , giving $(q, ε, ε)$ — empty stack!
So this exact machine accepts $ε$ . Since $ε = a^{0} b^{0}$ , the Ex 1 machine really recognises $L_{0}$ ( $n \geq 0$ ), not $L_{1}$ ( $n \geq 1$ ).

A formally sound machine for $L_{1}$ ( $n \geq 1$ ). The bug is that rule 4 can fire from the very start, before any $A$ was ever pushed. To forbid that, we use two states $q$ and $q^{'}$ so the marker-pop is reachable only after at least one full pop happened. The state itself records "have we popped an $A$ yet?":

$δ (q, a, Z_{0}) = {(q, A Z_{0})}$ — first $a$ : push $A$ (still in $q$ ).
$δ (q, a, A) = {(q, AA)}$ — each further $a$ : push $A$ (still in $q$ ).
$δ (q, b, AA)$ is not how $δ$ works (it only reads the single top symbol), so we split the last pop by looking at what is underneath: use $δ (q, b, A) = {(q, ε)}$ for a pop that still leaves an $A$ or $Z_{0}$ below, and detect the final pop by the state we move into:
- $δ (q, b, A) = {(q, ε), (q^{'}, ε)}$ — nondeterministically, this $b$ may be the last one: branch to $q^{'}$ .
$δ (q^{'}, ε, Z_{0}) = {(q^{'}, ε)}$ — pop the marker only in $q^{'}$ , i.e. only on a branch that has already popped at least one $A$ .
There is no rule $δ (q, ε, Z_{0})$ , so on input $ε$ the machine sits in $q$ with $Z_{0}$ on top and no move → $ε$ is rejected.

Why this is sound. State $q$ means "no $A$ has been popped as the final one yet"; state $q^{'}$ means "the branch guessed the last $A$ is popped." The only marker-pop lives in $q^{'}$ , and $q^{'}$ is entered only by a $b$ -pop. Therefore a marker-pop can never happen unless at least one $b$ popped an $A$ — which forces $n \geq 1$ . The correct branch (guess the last $b$ correctly) reaches $(q^{'}, ε, ε)$ and accepts; wrong guesses die harmlessly.

For $L_{0}$ ( $n \geq 0$ ): the original Ex 1 machine is exactly right, since it accepts $ε$ directly via rule 4.

Ex 5 — C6 · Nondeterminism is essential ( $w w^{R}$ )

Rules (one state $q$ , top of stack leftmost). Note $δ$ maps to a set:

(P) Push phase: $δ (q, x, Y) = {(q, x Y)}$ for $x \in {a, b}$ and any top $Y \in {a, b, Z_{0}}$ — put the read symbol on top.
(G) Midpoint guess: $δ (q, ε, Y) = {(q, Y)}$ for $Y \in {a, b}$ — an $ε$ -move that consumes no input and leaves the stack unchanged, but commits to "stop pushing, start matching." (This is the nondeterministic choice, offered alongside (P).)
(M) Match-pop phase: $δ (q, x, x) = {(q, ε)}$ for $x \in {a, b}$ — pop iff the input symbol equals the top.
(E) Finish: $δ (q, ε, Z_{0}) = {(q, ε)}$ — pop the marker → empty stack.

The accepting branch on $abba$ (one $⊢$ -move per line, each labelled with the rule and how the configuration changes):

$(q, abba, Z_{0}) ⊢ (q, bba, a Z_{0})$ — Why? rule (P): push the first symbol $a$ ; stack $Z_{0} \to a Z_{0}$ .
$(q, bba, a Z_{0}) ⊢ (q, ba, ba Z_{0})$ — Why? rule (P): push the second symbol $b$ ; stack $a Z_{0} \to ba Z_{0}$ . (This is the push; input shrank $bba \to ba$ , stack grew.)
$(q, ba, ba Z_{0}) ⊢ (q, ba, ba Z_{0})$ — Why this step? the midpoint-guess rule (G) fires: $δ (q, ε, b) = {(q, b)}$ consumes no input and leaves the stack unchanged, so state, input and stack look identical to step 2's result. Its only effect is that we now commit to matching. (This is the $ε$ -guess; nothing visible changes — that is exactly what a silent commit looks like.)
$(q, ba, ba Z_{0}) ⊢ (q, a, a Z_{0})$ — Why? rule (M): input $b$ equals top $b$ → pop; input $ba \to a$ , stack $ba Z_{0} \to a Z_{0}$ .
$(q, a, a Z_{0}) ⊢ (q, ε, Z_{0})$ — Why? rule (M): input $a$ equals top $a$ → pop; both halves now matched.
$(q, ε, Z_{0}) ⊢ (q, ε, ε)$ — Why? rule (E): pop $Z_{0}$ → empty stack, accept.

Why other branches don't spoil it. A branch that fires (G) too early (say after 1 symbol) will find the input $\neq =$ top and get stuck — that branch just dies. Acceptance needs only one surviving branch, and the correct-midpoint branch survives.

Ex 6 — C7 · Two counters at once: ${a^{n} b^{2 n} ∣ n \geq 1}$

Rules:

$δ (q, a, Z_{0}) = {(q, AA Z_{0})}$ — first $a$ pushes two $A$ 's.
$δ (q, a, A) = {(q, AAA)}$ — each further $a$ pushes two more $A$ 's (replace top $A$ by $AAA$ = net $+ 2$ ).
$δ (q, b, A) = {(q, ε)}$ — each $b$ pops one $A$ .
$δ (q, ε, Z_{0}) = {(q, ε)}$ — pop marker when $A$ 's exhausted.

Run on $abb$ (one $⊢$ -move per line):

$(q, abb, Z_{0}) ⊢ (q, bb, AA Z_{0})$ — Why? rule 1: one $a$ deposits two $A$ 's (the debt of two $b$ 's).
$(q, bb, AA Z_{0}) ⊢ (q, b, A Z_{0})$ — Why? rule 3: first $b$ pops one $A$ .
$(q, b, A Z_{0}) ⊢ (q, ε, Z_{0})$ — Why? rule 3: second $b$ pops the last $A$ .
$(q, ε, Z_{0}) ⊢ (q, ε, ε)$ — Why? rule 4: pop $Z_{0}$ → accept.

Sanity on a bad string $abbb$ . After the two $A$ 's are popped by the first two $b$ 's we reach $(q, b, Z_{0})$ ; the third $b$ needs $δ (q, b, Z_{0})$ which is undefined → dead → reject (correct, since $3 \neq = 2 \cdot 1$ ).

Ex 7 — C8 · Conversion empty-stack $\to$ final-state with marker $X_{0}$

Construction of $M$ . New start state $p_{0}$ , new bottom guard $X_{0}$ , final state $q_{f}$ , $F = {q_{f}}$ :

(S) Set-up: $δ (p_{0}, ε, X_{0}) = {(q, Z_{0} X_{0})}$ — push $N$ 's bottom $Z_{0}$ above the guard, hand control to $N$ 's state $q$ .
(1c) copy of rule 1: $δ (q, a, Z_{0}) = {(q, A Z_{0})}$ .
(2c) copy of rule 2: $δ (q, a, A) = {(q, AA)}$ .
(3c) copy of rule 3: $δ (q, b, A) = {(q, ε)}$ .
(4c) copy of rule 4 (pop the simulated bottom $Z_{0}$ ): $δ (q, ε, Z_{0}) = {(q, ε)}$ .
(A) Accept: $δ (q, ε, X_{0}) = {(q_{f}, X_{0})}$ — when $X_{0}$ is exposed, jump to the final state.

Run on $aabb$ (one $⊢$ -move per line, each labelled with the rule it fires):

$(p_{0}, aabb, X_{0}) ⊢ (q, aabb, Z_{0} X_{0})$ — Why? rule (S): set up the simulated bottom $Z_{0}$ above the guard $X_{0}$ , enter $N$ 's state $q$ .
$(q, aabb, Z_{0} X_{0}) ⊢ (q, abb, A Z_{0} X_{0})$ — Why? rule (1c): first $a$ pushes an $A$ .
$(q, abb, A Z_{0} X_{0}) ⊢ (q, bb, AA Z_{0} X_{0})$ — Why? rule (2c): second $a$ pushes another $A$ .
$(q, bb, AA Z_{0} X_{0}) ⊢ (q, b, A Z_{0} X_{0})$ — Why? rule (3c): first $b$ pops one $A$ .
$(q, b, A Z_{0} X_{0}) ⊢ (q, ε, Z_{0} X_{0})$ — Why? rule (3c): second $b$ pops the last $A$ .
$(q, ε, Z_{0} X_{0}) ⊢ (q, ε, X_{0})$ — Why this step? rule (4c) — the rule-4 copy — pops the simulated bottom $Z_{0}$ on $ε$ -input. Now only the guard $X_{0}$ remains: this is the moment $N$ "would have emptied its stack."
$(q, ε, X_{0}) ⊢ (q_{f}, ε, X_{0})$ — Why? rule (A): $X_{0}$ exposed → jump to $q_{f}$ . Input empty and $q_{f} \in F$ → accept.

Why the marker matters (Mistake D defused). Without $X_{0}$ , if $N$ ever emptied its stack mid-input, $M$ would be stuck (no top symbol to read). $X_{0}$ guarantees there's always a symbol on top, so $M$ never dies from an empty stack; it only accepts by the deliberate $q_{f}$ jump. Note $M$ 's stack holds $\geq 1$ symbol ( $X_{0}$ ) at every configuration above.

Ex 8 — C9 · Real-world: balanced brackets

Rules (map ( $\to$ push, ) $\to$ pop; let $L =$ (, $R =$ )):

$δ (q, L, Z_{0}) = {(q, A Z_{0})}$ and $δ (q, L, A) = {(q, AA)}$ — every ( pushes an $A$ .
$δ (q, R, A) = {(q, ε)}$ — every ) pops one $A$ (matches an open bracket).
$δ (q, ε, Z_{0}) = {(q, ε)}$ — clear marker when all matched → empty stack.

Run on (()) (one $⊢$ -move per line):

$(q, (()), Z_{0}) ⊢ (q, ()), A Z_{0})$ — Why? rule 1: first ( pushes an $A$ (depth $1$ ).
$(q, ()), A Z_{0}) ⊢ (q,)), AA Z_{0})$ — Why? rule 1: second ( pushes an $A$ (depth $2$ ).
$(q,)), AA Z_{0}) ⊢ (q,), A Z_{0})$ — Why? rule 2: first ) pops one $A$ (depth $1$ ).
$(q,), A Z_{0}) ⊢ (q, ε, Z_{0})$ — Why? rule 2: second ) pops the last $A$ (depth $0$ ).
$(q, ε, Z_{0}) ⊢ (q, ε, ε)$ — Why? rule 3: pop $Z_{0}$ → accept: balanced.

Run on ())( (one $⊢$ -move per line):

$(q, ()) (, Z_{0}) ⊢ (q,)) (, A Z_{0})$ — Why? rule 1: first ( pushes an $A$ .
$(q,)) (, A Z_{0}) ⊢ (q,) (, Z_{0})$ — Why? rule 2: first ) pops the $A$ ; stack back to $Z_{0}$ .
Next symbol ) needs $δ (q, R, Z_{0})$ — undefined (a close bracket with nothing open) → dead → reject: unbalanced. ✓

Ex 9 — C10 · Exam twist: same string, opposite verdicts

Trace on $ab$ (one $⊢$ -move per line):

$(q_{0}, ab, Z_{0}) ⊢ (q_{0}, b, A Z_{0})$ — Why? rule 1: the $a$ pushes an $A$ .
$(q_{0}, b, A Z_{0}) ⊢ (q_{1}, ε, A Z_{0})$ — Why? rule 2: the $b$ reads top $A$ , moves to $q_{1}$ , leaves the stack as $A Z_{0}$ (peek, no pop).

Now judge under each mode from the final snapshot $(q_{1}, ε, A Z_{0})$ .

Final state: condition is $(q_{0}, ab, Z_{0}) ⊢^{*} (q, ε, γ)$ with $q \in F$ . Here $q = q_{1} \in F$ , input $= ε$ . Accept.
Empty stack: condition needs $γ = ε$ . Here $γ = A Z_{0} \neq = ε$ , and no rule can pop them — dead. Reject.

So $L_{F} (M) ∋ ab$ but $L_{N} (M) \neq ∋ ab$ . Same machine, same input, opposite results because the two acceptance conventions ask different questions. (Recall Mistake C from the parent: modes are equal in power across all machines — you can always convert — but on any fixed machine they can differ.)

Recall Self-test (reveal after guessing)

Ex 1 verdict on $aaabbb$ ::: Accept (empty stack, height returns to floor). Ex 2 stack contents when accepting $aabb$ by final state ::: $Z_{0}$ (non-empty — stack ignored). Ex 3 reason $aab$ is rejected ::: Input ends with $A$ still on top; rule 4 needs $Z_{0}$ on top → stuck. Ex 4 is $ε$ in ${a^{n} b^{n} ∣ n \geq 1}$ ? ::: No — that needs $n \geq 1$ ; $ε = a^{0} b^{0}$ . Ex 6 verdict on $abbb$ for $a^{n} b^{2 n}$ ::: Reject ( $3 \neq = 2 \cdot 1$ ). Ex 9 punchline ::: Same machine can accept a string by final state yet reject it by empty stack.

Flashcards

Why does

aab

fail on the empty-stack

a^{n} b^{n}

PDA?

One

A

remains on top when input ends; rule 4 needs

Z_{0}

on top, so no move → non-empty stack → reject.

In Ex 2 what is on the stack at the accepting moment?

Z_{0}

— final-state mode ignores stack contents.

How many

A

's does one

a

push in the

a^{n} b^{2 n}

machine?

Two (each

a

owes two

b

's).

Why must the

{w w^{R}}

PDA be nondeterministic?

It must guess the unmarked midpoint; a DPDA can't detect it.

What does the fresh marker

X_{0}

prevent during empty-stack→final-state conversion?

The simulated machine emptying its stack early and getting stuck;

X_{0}

keeps a symbol on top always.

Can one fixed PDA accept a string by final state but reject it by empty stack?

Yes (Ex 9) — the two modes ask different questions though they define the same language class.