Computer Engineering is coming soon

We're still writing and reviewing the notes for every subject, and we'll open it when every subject is ready. Meanwhile you can practise aptitude, ask Aria about any subject, or see the branches that are ready.

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:

    1. Convert a PDA that accepts by empty stack into one that accepts by final state.
    2. Convert a PDA that accepts by final state into one that accepts by empty stack.
    3. 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):

    1. (q_push, aabb, Z0)
    2. after reading first a: (q_push, abb, A Z0)
    3. after reading second a: (q_push, bb, A A Z0)
    4. after reading first b (switch to pop phase): (q_pop, b, A Z0)
    5. after reading second b: (q_pop, ε, Z0)
    6. ε-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

  1. Define acceptance by empty stack in one sentence.
  2. What is the transition function type for a nondeterministic PDA? (write the mapping)
  3. 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?