Pushdown automata
Pushdown automata (PDA): machines with a stack that accept exactly the context-free languages; definitions, constructions between CFG and PDA, examples, traces, and exam tips.
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
Pushdown automata (PDA) model programs and compilers that need a memory with LIFO behaviour (a stack). Engineers use PDA ideas when writing parsers (especially for programming languages described by context-free grammars), for designing syntax analyzers, and for proving whether a language (set of strings) is context-free or not.
Key ideas
Definition (PDA): A PDA is a 7-tuple (Q, Σ, Γ, δ, q0, Z0, F) where
- Q is a finite set of states.
- Σ is the input alphabet (finite set of input symbols).
- Γ is the stack alphabet (finite set of stack symbols).
- δ is the transition function: δ: Q × (Σ ∪ {ε}) × Γ → P(Q × Γ*). (P(X) means the power set of X.)
- q0 ∈ Q is the start state.
- Z0 ∈ Γ is the initial stack symbol (bottom marker).
- F ⊆ Q is the set of accepting (final) states.
Explanation of δ: from state p, if the current input symbol is a (or ε) and top of stack is X, the PDA may nondeterministically move to a state q and replace X by a possibly empty string of stack symbols (β ∈ Γ*). Because δ maps to a set, the PDA is generally nondeterministic.
Configuration — a triple (q, w, γ) where q ∈ Q is current state, w ∈ Σ* is remaining input, and γ ∈ Γ* is current stack content (top at left or right depending on convention; I will use leftmost symbol as stack top when writing sequences). A move applies a δ transition, consumes either an input symbol or ε, pops the top stack symbol and pushes the replacement string.
Acceptance by final state — A string w ∈ Σ* is accepted if there is a sequence of moves starting from (q0, w, Z0) that ends in (qf, ε, γ) where qf ∈ F and γ ∈ Γ* (stack may be non-empty). This is one standard acceptance mode.
Acceptance by empty stack — A string w ∈ Σ* is accepted if there is a sequence of moves starting from (q0, w, Z0) that ends in (q, ε, ε) with empty stack (stack exactly empty) for some q ∈ Q. This is the other standard acceptance mode.
Important relation: For nondeterministic PDAs (NPDA), acceptance by final state and acceptance by empty stack are equivalent in expressive power: any NPDA using one mode can be converted to an NPDA using the other mode that accepts the same language (construction involves adding new start/accept states or new stack marker and ε-transitions). Be prepared to show this construction in exam answers. Note: for deterministic PDAs (DPDAs), these two acceptance modes are not equivalent as language families without an explicit end-marker; acceptance by empty stack is strictly weaker than acceptance by final state.
Deterministic PDA (DPDA) — a PDA is deterministic if for every (q, a, X) at most one transition is defined and if an ε-transition exists for (q, ε, X) then no transition exists for any (q, a, X) with a ∈ Σ (to avoid choice between consuming input and taking ε). DPDAs are strictly less powerful than NPDAs: some CFLs (e.g., { a^n b^n | n ≥ 0 } is DPDA-acceptable), but some CFLs like L = { ww^R : w ∈ {a,b}* } are not accepted by any DPDA (i.e., they are not deterministic context-free). State this carefully in exams.
Equivalence with context-free grammars (CFGs): The class of languages accepted by NPDAs is exactly the class of context-free languages (CFLs).
- Theorem (Equivalence): A language L ⊆ Σ* is context-free iff there exists an NPDA that accepts L (by empty stack or by final state). Typical exam asked proofs:
- From CFG to PDA: Construct a PDA that simulates leftmost derivations by using the stack to hold a sentential form and nondeterministically rewriting a nonterminal on stack using grammar productions (push RHS in reverse order), and matching terminals by consuming input.
- From PDA to CFG: Construct variables A_{pXq} that generate the strings taking the PDA from state p with stack-top symbol X to state q after X has been removed; use productions to simulate PDA moves. This construction is longer; give the idea and write main productions.
- Theorem (Equivalence): A language L ⊆ Σ* is context-free iff there exists an NPDA that accepts L (by empty stack or by final state). Typical exam asked proofs:
What to draw on blackboard for a PDA: draw states as circles labelled with state names (q0, q1,...), arrows for transitions labelled with triple format
input, pop → pushwhereinputmay be ε,popis the symbol removed from stack, andpushis the string written to stack (use ε for push of empty). Mark start state with an incoming arrow and final states with double circles when acceptance-by-final-state is used. Also show the initial stack symbol Z0 pushed implicitly on start.
Formulas
PDA = (Q, Σ, Γ, δ, q0, Z0, F) — Q states, Σ input alphabet, Γ stack alphabet, δ transition function, q0 start, Z0 initial stack symbol, F final states. Applies always as the formal definition.
δ : Q × (Σ ∪ {ε}) × Γ → P(Q × Γ*) — transition function type; maps (state, input-or-ε, stack-top) to set of (next-state, string-to-push). Use this when writing transitions.
Configuration: (q, w, γ) — q current state, w remaining input (Σ*), γ stack contents (Γ*). Use this to write traces.
(q, aw, Xα) ⊢ (p, w, βα) when (p, β) ∈ δ(q, a, X) — single transition relation meaning: from state q with input starting a and stack top X followed by α, you move to p, consume a, pop X and push β on top of α. Use this format in derivation steps.
L(P) = { w ∈ Σ* | (q0, w, Z0) ⊢* (qf, ε, γ) for some qf ∈ F } — acceptance by final state.
L(P) = { w ∈ Σ* | (q0, w, Z0) ⊢* (q, ε, ε) for some q ∈ Q } — acceptance by empty stack.
Worked examples
Example 1 — NPDA for L = { a^n b^n | n ≥ 0 } and trace for "aaabbb":
- Idea: push one X for each a seen, then on b pop one X. Use ε-transition to switch from pushing to popping.
- States: q_push (start), q_pop (final). Stack alphabet Γ = {Z0, X}.
- Transitions (write as δ-moves / draw as labels):
- From q_push:
a, Z0 → X Z0(push X when Z0 on bottom) anda, X → X X(push X on X) — these model reading 'a' and pushing X. - Epsilon transitions from q_push to q_pop that leave the stack unchanged, one for each possible top-of-stack symbol:
ε, Z0 → Z0andε, X → X. Both are needed (e.g., to accept n = 0). - From q_pop:
b, X → ε(read b and pop one X). Make q_pop accepting.
- From q_push:
- Trace for input w = "aaabbb":
- Start (q_push, aaabbb, Z0).
- Read a, apply
a, Z0 → X Z0: (q_push, aabbb, X Z0). - Read a,
a, X → X X: (q_push, abbb, X X Z0). - Read a,
a, X → X X: (q_push, bbb, X X X Z0). - Take ε-transition to q_pop without consuming input, stack unchanged: (q_pop, bbb, X X X Z0).
- Read b,
b, X → ε: (q_pop, bb, X X Z0). - Read b,
b, X → ε: (q_pop, b, X Z0). - Read b,
b, X → ε: (q_pop, ε, Z0). - Now input is empty; if using final-state acceptance, accept since q_pop is final. If using empty-stack acceptance, include the transition
ε, Z0 → εin q_pop and take it now to pop Z0, then accept. So w is accepted. Show stack content at each step in answer.
- Mark the diagram: two circles q_push and q_pop, arrow into q_push, double circle on q_pop. Label transitions as
a, X→XXetc.
Example 2 — Convert CFG G: S → a S b | ε into an NPDA (construction + trace for "aabb"):
- Grammar generates a^n b^n. Standard CFG→PDA construction:
- Use Γ that includes nonterminals and terminals: e.g., Γ contains S, a, b, and bottom Z0.
- Start by pushing start symbol S on stack:
ε, Z0 → S Z0from q0 to q_loop. - For each production A → Y1 Y2 ... Yk add δ-transitions that replace A by Y1...Yk on stack using ε while staying in the same state. Practically:
ε, A → Y1 Y2 ... Yk(push RHS). Push order must make Y1 appear on top last if you want leftmost expansion; so push RHS in reverse when implementing on a real PDA diagram. - For matching terminals:
a, a → εconsumes input a when top of stack is terminal a.
- For S → a S b and S → ε we add:
ε, S → a S b(push b then S then a if your push writes left-to-right? Explain: when writing transition label, state it as replace S by a S b; in implementation push b, then S, then a so that a is on top to match input next).ε, S → ε(for S→ε).- Matching transitions:
a, a → εandb, b → ε.
- Trace for input "aabb":
- (q, aabb, Z0) — apply
ε, Z0 → S Z0→ (q, aabb, S Z0). - Replace S with a S b using
ε, S → a S b→ (q, aabb, a S b Z0). - Match terminal a:
a, a → εconsuming first a → (q, abb, S b Z0). - Replace S → a S b again → (q, abb, a S b b Z0).
- Match a with top a: consume 2nd a → (q, bb, S b b Z0).
- Replace S → ε using
ε, S → ε→ (q, bb, b b Z0). - Match b:
b, b → ε→ (q, b, b Z0). - Match b:
b, b → ε→ (q, ε, Z0). - If using acceptance-by-final-state, make the state final and accept. If using empty-stack acceptance, include the transition
ε, Z0 → εand take it now to pop Z0, then accept. So "aabb" is accepted.
- (q, aabb, Z0) — apply
Example 3 — Outline: From PDA to CFG (exam-level sketch):
- Introduce variables A_{pXq} meaning: strings that take the PDA from state p with stack-top symbol X to state q after removing X (formal details vary). Create productions based on PDA transitions that either consume a terminal and change stack, or use sequences of variables to simulate push/pop. State the result: you get a CFG that generates exactly the language of the original NPDA. Give a reference to standard textbooks for full construction steps.
Common mistakes
- Confusing acceptance modes: final-state and empty-stack are different definitions; they are equivalent for NPDA only after a construction; do not assume DPDA has same power as NPDA.
- Writing δ as Q × Σ × Γ → Q × Γ* (forgetting the power set) — this misses nondeterminism.
- Using ε-transitions carelessly in a DPDA; deterministic machines cannot have conflicting ε and non-ε choices.
- In traces, not showing stack contents step-by-step or mixing top-left/top-right conventions for stack representation.
For your exam
Kinds of questions:
- Definitions: give formal 7-tuple and explain each component.
- Short notes: compare DPDA vs NPDA, acceptance modes, or show closure properties of CFLs (refer to CFG topic for deeper properties).
- Constructions/derivations: convert a given CFG to an NPDA (full construction) or convert a simple NPDA to a CFG (sketch expected for complex PDA).
- Diagrams: draw a PDA (states and labelled transitions) for small languages like a^n b^n or balanced parentheses.
- Traces: give a step-by-step configuration trace for a given input string.
What full-marks answers include:
- For a definition: the full 7-tuple, the exact type of δ, and explanation of acceptance modes.
- For a CFG→PDA construction: the list of transitions (show how to push start symbol, how to replace nonterminals, how to match terminals), a clear diagram, and a short trace for one example string.
- For PDA→CFG: state the idea with variables A_{pq}, show main types of productions, and argue correctness (that the CFG generates exactly strings the PDA accepts). If asked to provide full formal construction, write every production rule pattern.
- For traces/diagrams: show every configuration step, stack content, and input remainder.
Quick check
- Give the formal type/signature of the transition function δ for a nondeterministic PDA.
- How does a PDA simulate the CFG production A → XYZ on its stack? (mention push order)
- State the equivalence theorem connecting PDAs and CFGs.
Answers: 1) δ : Q × (Σ ∪ {ε}) × Γ → P(Q × Γ*). 2) Replace A by XYZ using an ε-transition that pops A and pushes Z then Y then X so X is on top (push RHS in reverse). 3) A language is context-free iff some NPDA accepts it (NPDA and CFG are equivalent).
Finished this topic? Mark it so your progress, study plan and readiness keep up.
Stuck on something here?