PDA acceptance: final state and empty stack
Compare and convert the two standard ways a pushdown automaton (PDA) can accept input: by empty stack and by final state; show formal definitions, constructions to convert one form to the other (for nondeterministic PDAs), worked examples, common mistakes and exam guidance.
Drafted with Aria, reviewed by the AiCanCode.org team · Updated . How we write and check our notes. Spotted an error? Use Give Feedback at the bottom of the page.
Why it matters
Two common ways to define when a pushdown automaton (PDA) accepts an input are by reaching a final state or by emptying its stack. Engineers who build parsers, compilers or translators use PDAs (and their equivalence with context-free grammars) to design syntax analyzers; knowing both acceptance modes and how to convert between them helps in proving properties of languages and in implementing parsers.
Key ideas
Transition function (non-deterministic PDA): δ : Q × (Σ ∪ {ε}) × Γ → P(Q × Γ). This means from state q, reading either a symbol a ∈ Σ or ε (no input), with top-of-stack X ∈ Γ, the PDA may move to any of a set of pairs (p, γ) where p ∈ Q is the next state and γ ∈ Γ is the string that replaces X on the stack.
Acceptance by final state: A PDA accepts an input string w by final state if there exists a sequence of moves starting from (q0, w, Z0) and ending in some configuration (qf, ε, α) where qf ∈ F (final state) and the unread input is empty (ε). The stack may be non-empty.
Acceptance by empty stack: A PDA accepts w by empty stack if there exists a sequence of moves starting from (q0, w, Z0) and ending in a configuration (q, ε, ε) where the unread input is empty and the stack is empty. The state q need not be in F (often F is empty in this mode).
Important theoretical fact (standard statement used in university courses): For nondeterministic PDAs (NPDA) the two acceptance modes are equivalent: the class of languages accepted by NPDA by final state equals the class accepted by empty stack; both describe exactly the context-free languages (CFLs). The usual proof is by construction in both directions (give constructions below).
Note about deterministic PDAs (DPDA): The equivalence of acceptance by final state and by empty stack does not hold automatically for deterministic PDAs under all model variants. There are subtleties involving end-marker handling and restrictions on ε-moves. I mark this as a verification point below because details depend on the exact DPDA definition used in courses/textbooks. In many standard definitions without a right end-marker, languages accepted by DPDA by empty stack are prefix-free (in particular, they cannot contain ε together with other strings), which is a key reason equivalence with final-state acceptance fails.
Constructions commonly required in exams:
- Convert a PDA that accepts by empty stack into one that accepts by final state.
- Convert a PDA that accepts by final state into one that accepts by empty stack.
- Trace a PDA run (show configurations) for a given input.
What to draw for diagrams: when the exam asks for a PDA diagram, draw states as circles labelled with names (q0, q1, ...). Draw directed arrows for transitions; label each arc with three-part label in the form input_symbol, stack_top → stack_replacement (use ε for empty). Mark start state with an incoming arrow and initial stack symbol in a small box near the start or note Z0 in the formal tuple. Mark final states by double circle when acceptance-by-final-state is intended.
Formulas
P = (Q, Σ, Γ, δ, q0, Z0, F) — P is a PDA; Q states, Σ input alphabet, Γ stack alphabet, δ transition function, q0 start state, Z0 initial stack symbol, F set of final states. Unit: none. Applies to any PDA definition.
δ : Q × (Σ ∪ {ε}) × Γ → P(Q × Γ*) — transition function for a nondeterministic PDA. Unit: none. Applies to NPDA.
L(P) = { w ∈ Σ* | (q0, w, Z0) ⊢* (qf, ε, α) for some qf ∈ F } — language accepted by final state. Unit: none. Applies when PDA acceptance mode is final state.
L(P) = { w ∈ Σ* | (q0, w, Z0) ⊢* (q, ε, ε) for some q ∈ Q } — language accepted by empty stack. Unit: none. Applies when PDA acceptance mode is empty stack.
(Here ⊢* denotes zero or more moves of the PDA.)
Worked examples
Example 1 — NPDA for L = { a^n b^n | n ≥ 0 } (empty stack acceptance), then convert to final-state acceptance.
A. NPDA P1 that accepts by empty stack.
Idea: push one stack symbol A for each a read; for each b pop one A. When input ends and stack has only the initial symbol Z0, pop it to make stack empty via an ε-move.
Formal 7-tuple (sketch): Q = {q_push, q_pop}, Σ = {a,b}, Γ = {A, Z0}, start q0 = q_push, F = ∅ (not used). δ defined as:
- δ(q_push, a, Z0) contains (q_push, A Z0) (push A above Z0)
- δ(q_push, a, A) contains (q_push, A A) (push A)
- δ(q_push, b, A) contains (q_pop, ε) (on first b, switch to pop phase and pop A)
- δ(q_push, ε, Z0) contains (q_pop, Z0) (allow ε-case by moving to pop phase)
- δ(q_pop, b, A) contains (q_pop, ε) (pop A for each b)
- δ(q_pop, ε, Z0) contains (q_pop, ε) (pop Z0 to make stack empty at the end)
Trace for input w = a a b b ("aabb"): show configurations (write them each on a new line):
- (q_push, aabb, Z0)
- after reading first a: (q_push, abb, A Z0)
- after reading second a: (q_push, bb, A A Z0)
- after reading first b (switch to pop phase): (q_pop, b, A Z0)
- after reading second b: (q_pop, ε, Z0)
- ε-move pop Z0: (q_pop, ε, ε) — stack empty and input consumed, accept.
B. Convert P1 to P2 that accepts by final state (standard construction):
Add a new final state q_f. Add ε-transitions that, when the unread input is ε and the stack-top is the bottom marker, move to q_f; you may either leave the bottom marker or pop it on that move. Concretely, for all q ∈ Q, add δ(q, ε, Z0) contains (q_f, Z0) or (q_f, ε); the move may be taken only when the unread input is ε. The goal is to move to q_f exactly when the stack has returned to the bottom marker and all input has been consumed.
Diagram note: from each state, add an arc labelled ε, Z0 → Z0 (or ε) to q_f, and annotate that it may be taken only when the unread input is ε. Make q_f double circled.
This construction ensures: when the NPDA would accept by empty stack, the new machine can take an ε-move to the final state with empty input remaining.
Example 2 — Convert a PDA accepting by final state into one accepting by empty stack (sketch).
- Given P = (Q, Σ, Γ, δ, q0, Z0, F). Create P' by adding a fresh bottom-of-stack symbol Z (not in Γ), a new start state q_s, and a new state q_accept. Make Z the initial stack symbol; add an ε-move δ(q_s, ε, Z) contains (q0, Z Z0) so Z sits below the old bottom marker Z0, then simulate P. From any final state f ∈ F add an ε-move that moves to q_accept and empties the stack by popping symbols until only Z remains, then pop Z to leave stack empty. This ensures that any accepting run of P can be turned into a run that empties the stack in P'.
- Exam answer must show the added states, transitions and explain that nondeterminism permits emptying.
(These are model answers: in exams you should write transitions explicitly and give a sample trace for a string.)
Common mistakes
- Omitting ε-transitions needed to move to final state or to pop Z0 at the end.
- Assuming deterministic properties when using NPDA constructions (DPDA subtleties matter).
- In conversion proofs, forgetting to preserve that the input must be fully consumed when accepting.
- Not handling the n = 0 case (e.g., empty string) explicitly — always check how your PDA accepts ε.
For your exam
Typical question types:
- Definition: Give formal definition of PDA and the two acceptance modes. A full-mark answer includes the 7-tuple and explanation of δ.
- Conversion derivation: Convert an NPDA that accepts by empty stack into one that accepts by final state (and vice versa). Full answer: give construction steps, state/transition additions, and a brief correctness argument.
- Trace: Given a PDA diagram and an input, write the sequence of configurations showing acceptance or rejection. Full answer: enumerate each configuration correctly and justify each transition using the label.
- Short notes: Explain equivalence of the two acceptance modes for NPDA. Full answer: state theorem and sketch the two constructions.
- Diagram question: Draw PDA for a simple CFL (like a^n b^n or (a|b)*abb) showing acceptance mode; label transitions precisely.
Exam tips: always specify whether machine is deterministic or nondeterministic; state whether ε-moves are allowed; show initial and final stack symbol handling explicitly.
Quick check
- Define acceptance by empty stack in one sentence.
- What is the transition function type for a nondeterministic PDA? (write the mapping)
- Give the single key step to convert an empty-stack NPDA into a final-state NPDA.
Answers: 1) A PDA accepts by empty stack if it can read the entire input and reach a configuration whose stack is empty (top-to-bottom) regardless of state. 2) δ : Q × (Σ ∪ {ε}) × Γ → P(Q × Γ*). 3) Add a new final state and an ε-transition that is taken when the unread input is ε and the stack has returned to the initial bottom marker (Z0), moving the machine into the final state (optionally popping Z0).
Notes for reviewer: I have kept explanations simple and included formal statements used in university answers. Where I am unsure I list verifications below.
Finished this topic? Mark it so your progress, study plan and readiness keep up.
Stuck on something here?