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

Before the traps, let us re-anchor every symbol used below, so nothing is invoked before it is named. Look at the picture: the stack is a vertical pile of plates, growing upward, with the very first plate ( $Z_{0}$ ) glued to the floor.

Figure — Pushdown automata (PDA) — configuration, acceptance by empty stack - final state

Definition The symbols you must have in hand

$Γ$ = the stack alphabet — the finite set of symbols that are allowed to sit on the stack (in the picture: the letters printed on the plates, like $A$ , $B$ , $Z_{0}$ ). It is different from $Σ$ , the input alphabet you read.
$Z_{0} \in Γ$ = the initial stack symbol, the bottom-of-stack marker. Before any input is read, the stack holds exactly this one plate. Its job: tell the machine "you have hit the floor."
$γ \in Γ^{*}$ = any string of stack symbols — i.e. a whole stack's worth of plates, written top-leftmost. So " $γ \in Γ^{*}$ " just means " $γ$ is a possible stack content."
$A β$ is the same idea zoomed in: $A$ is the single symbol on top, and $β \in Γ^{*}$ is the rest of the stack below it. So $A β$ and $γ$ describe the same thing — $γ$ named as a whole, $A β$ split into "top" plus "tail $β$ ."

Reminder of the other moving parts:

A configuration (ID) is the triple $(q, w, γ)$ = (state, remaining unread input, whole stack $γ$ with top written leftmost).
Empty-stack acceptance $L_{N}$ : reach $(q, ε, ε)$ — stack literally has zero symbols.
Final-state acceptance $L_{F}$ : reach $(q, ε, γ)$ with $q \in F$ — stack contents ignored.
$⊢$ = one legal step; $⊢^{*}$ = zero or more steps.

The next figure shows one $⊢$ step visually — how the ID changes when a plate is pushed:

And here is a full stepwise visual trace of ${a^{n} b^{n}}$ on input $aabb$ , so you can watch the stack rise and fall and empty — the picture the "empty-stack" trap questions are really about:

True or false — justify

TRUE/FALSE: A PDA that accepts by final state must also have an empty stack to accept.

False.

L_{F}

ignores the stack content

γ

entirely; you can end in a final state with junk symbols still on the stack and still accept. Only

L_{N}

demands the stack be empty.

TRUE/FALSE: For empty-stack acceptance you must also pop the bottom marker

Z_{0}

True. "Empty" means zero symbols including $Z_{0}$ . If

Z_{0}

is still sitting there the stack isn't empty, so no acceptance — you need an explicit

ε

-move that pops it.

TRUE/FALSE: Every language accepted by empty stack is also accepted by some final-state PDA.

True. Both modes recognise exactly the context-free languages, and there is a mechanical conversion (add a fresh marker

X_{0}

below

Z_{0}

, reach a final state when

X_{0}

resurfaces). See Context-Free Grammars.

TRUE/FALSE: In the ID

(q, w, A β)

the symbol

A

is at the bottom of the stack.

False. By convention the top is written leftmost, so here

A

is the top and

β

is everything below it (the tail of the stack). Reading it backwards breaks every transition rule.

TRUE/FALSE: A DPDA (deterministic PDA) recognises exactly the same languages as a general PDA.

False. The stack blocks the subset-construction trick that makes NFAs and DFAs equal. DPDAs are strictly weaker;

{w w^{R}}

is context-free but not accepted by any Deterministic PDA (DPDA).

TRUE/FALSE: Every regular language is accepted by some PDA.

True. A PDA is an NFA plus a stack; just never touch the stack (always push back what you pop) and you have an NFA, which already covers all regular languages (Nondeterministic Finite Automata).

TRUE/FALSE: If

δ (q, ε, A)

is defined, the PDA can move without reading any input.

True.

ε

-moves consume no input; they let the machine rearrange the stack or change state "for free," which is essential for guessing (e.g. a palindrome's midpoint).

TRUE/FALSE: A single PDA move can push more than one symbol onto the stack.

True. The output string

γ \in Γ^{*}

can be long:

γ = B A

replaces top

A

with

B

above

A

, netting a push. Pop (

γ = ε

) and peek (

γ = A

) are just other choices of

γ

TRUE/FALSE: The transition function output being a set is only about handling

ε

-moves.

False. The set encodes nondeterminism — multiple legal (state, push-string) choices from one situation.

ε

-input is a separate feature; a set is needed even for ordinary input symbols.

TRUE/FALSE: PDAs and Turing Machines have equal recognising power.

False. A stack is LIFO-restricted memory; a Turing tape is freely readable/writable. PDAs recognise only context-free languages, a strict subset of what Turing machines recognise.

Spot the error

Someone writes the yields rule as

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

. What's wrong?

Here

A

is the top plate and

β

is the stack below it. The input still shows

a w

after the step — but reading

a

must consume it, so it should become

(p, w, γ β)

. Only an

ε

-move leaves the input unchanged.

"For

{a^{n} b^{n}}

I'll pop an

A

on each

a

." Why does this fail?

You have nothing to pop yet — the stack starts with just

Z_{0}

. You must push an

A

per

a

(build the count), then pop per

b

. Popping during the

a

's underflows immediately.

A student claims

L_{N} (M) = {a^{n} b^{n}}

but forgot rule

δ (q, ε, Z_{0}) = (q, ε)

. What breaks?

After matching all

a

's and

b

's the stack is

Z_{0}

, not empty, so nothing is accepted. Without the marker-popping

ε

-move the empty-stack machine accepts no strings.

"To convert final-state to empty-stack, just add

ε

-moves that pop everything from final states." What's the hidden bug?

A string that momentarily empties the stack mid-run could be accepted early. You must first add a fresh bottom marker

X_{0}

that only the new dumping states can remove, so the original machine never empties by accident.

Someone models balanced brackets but keeps

F = \emptyset

and uses final-state acceptance. Result?

With no final states,

L_{F} = \emptyset

— nothing is ever accepted.

F = \emptyset

only makes sense with empty-stack acceptance, where final states are irrelevant.

A PDA has

δ (q, a, A) = {(p, ε)}

used as "read

a

and clear the whole stack." Why is that description wrong?

The output

γ = ε

pops only the top symbol

A

, not the entire stack. One move touches exactly one stack top; clearing the stack needs repeated

ε

-moves.

Why questions

Why is the "already-read" portion of the input not part of a configuration?

Look at figure s02 — only the remaining input

w

and the current stack

γ

feed the next move. The consumed prefix can never influence a later move, so storing it would be redundant.

Why does adding a stack lift a machine from regular to context-free languages?

Finite states are like a robot with a few moods and no notepad — bounded memory, so it can't count arbitrarily high. The stack (figure s01's growing plate pile) is unbounded LIFO memory, so it can match nested/counted structure like

a^{n} b^{n}

that no finite state set can track.

Why is nondeterminism essential (not just convenient) for accepting

{w w^{R}}

The midpoint is unmarked, so a deterministic machine cannot know when to switch from pushing to matching. A nondeterministic PDA guesses every possible midpoint (imagine many parallel copies of the trace in figure s03, each switching at a different plate) and one guess succeeds; see Pumping Lemma for CFLs for why some CFLs resist any DPDA.

Why does replacing "top by a string" unify push, pop, and peek into one rule?

Picture the top plate being swapped for a small pile: choosing

γ = B A

pushes,

γ = ε

pops, and

γ = A

leaves the top unchanged (peek). One transition schema

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

covers all three by picking

γ

Why do we bother with two acceptance modes if they have equal power?

Different constructions are cleaner in each mode — grammar-to-PDA conversions naturally give empty-stack machines, while human-designed recognisers often read more naturally as final-state machines. Equal power means you can freely pick whichever is convenient.

Why can't the subset construction (which makes NFA = DFA) be reused to make PDA = DPDA?

Subset construction tracks the set of possible states, but a PDA's configuration also includes an unbounded stack — you cannot bundle infinitely many possible stacks into one finite deterministic state. Determinism therefore genuinely restricts PDAs. See Closure Properties of CFLs.

Edge cases

What does a PDA do on the empty input

ε

, and can it accept it?

With no input to read it can still take

ε

-moves. If those reach an empty stack (or a final state) it accepts

ε

; e.g. a machine for

{a^{n} b^{n} ∣ n \geq 0}

accepts

ε

by immediately popping

Z_{0}

What happens if the machine reads all input but has

ε

-moves left it could take — is it stuck?

Nothing is forced. Because of nondeterminism, if any sequence of remaining

ε

-moves leads to acceptance the string is accepted; otherwise this branch just fails. Other branches may still succeed.

What if the stack becomes empty before all input is read?

That branch simply halts — with no stack top, no transition applies (every

δ

needs a top symbol), so it can make no further move and reads no more input. It cannot accept (input isn't finished); this is exactly why

L_{N}

needs the marker to survive until the end.

Can a PDA be in a configuration with no applicable transition? What then?

Yes — a "dead" configuration. That computation branch just stops without accepting. It only matters whether some branch reaches an accepting configuration.

{ε}

(the language containing only the empty string) accepted by some PDA?

Yes. Make the start state accept by empty stack via

δ (q_{0}, ε, Z_{0}) = (q_{0}, ε)

and provide no way to consume a real symbol, so only

ε

succeeds.

If a PDA never uses its stack (always pushes back exactly what it pops), what class does it recognise?

Exactly the regular languages — it behaves as a plain NFA. The stack is present but inert, so no extra power is gained.

Can an empty-stack PDA accept a language whose only string is long and non-nested, like

{aaaa}

Yes. Any finite/regular language is context-free, so an empty-stack PDA works; it just pushes/pops trivially and empties

Z_{0}

at the end. The stack's power is unused but not required to be.

Recall Self-test: the four traps in one breath

Final ignores the stack; Empty means zero symbols including $Z_{0}$ ; top is leftmost; DPDA is strictly weaker than PDA. Which mode ignores stack contents? ::: Final-state acceptance ( $L_{F}$ ). Where is the stack top written in an ID? ::: Leftmost in $γ$ . Is DPDA equal to PDA? ::: No, strictly weaker (e.g. ${w w^{R}}$ ).

The mnemonic below is anchored to the picture: four coloured plates, one per trap letter.