Coursify

Pushdown Automata (PDA): Short Note + Core Formalism

Pushdown Automata (PDA): Short Note + Core Formalism

Verified Sources
Sep 12, 2026

A Pushdown Automaton (PDA) is an extension of a finite automaton that uses a stack as additional memory. In each step, the PDA uses the current state, the next input symbol (or varepsilon\\varepsilon), and the top stack symbol to choose a transition; that transition can read the input and also push or pop stack symbols.

A PDA accepts an input string if there exists a computation path that satisfies an acceptance condition—commonly either:

  1. the automaton ends in an accepting state after the input is fully read, or
  2. the stack becomes empty after the input is fully read.

A key result is that PDA-recognized languages are exactly the context-free languages (CFLs).

Footnotes

  1. Pushdown automaton - Wikipedia - Defines PDA components, transition mechanism using state, input, and top stack symbol. ↩

  2. Pushdown automaton - Wikipedia - Acceptance by final state or empty stack; formal 7-tuple definition and notation. ↩

  3. Pushdown Automata • Non-Context-Free Languages (TOC4 PDF) - States the theorem: a language is context-free iff some PDA recognizes it. ↩

Pushdown Automata (PDA) — example like a^n b^n

Formal Definition and Components

A PDA can be defined as a 7-tuple

M=(Q,Sigma,Gamma,delta,q0,Z,F)M = (Q, \\Sigma, \\Gamma, \\delta, q_0, Z, F)

where:

  • QQ is a finite set of states
  • Sigma\\Sigma is the input alphabet
  • Gamma\\Gamma is the stack alphabet
  • delta\\delta is the transition relation (depends on state, input symbol or varepsilon\\varepsilon, and top-of-stack symbol; can update stack via push/pop)
  • q0inQq_0 \\in Q is the start state
  • ZinGammaZ \\in \\Gamma is the initial stack symbol
  • FsubseteqQF \\subseteq Q is the set of accepting states 2

The transition mechanism is commonly described in terms of:

  • reading an input symbol from Sigmacupvarepsilon\\Sigma \\cup \\{\\varepsilon\\}
  • popping the current top symbol AinGammaA \\in \\Gamma
  • pushing a (possibly empty) string alphainGamma∗\\alpha \\in \\Gamma^{*} onto the stack

Instantaneous Description (ID)
An instantaneous description of a PDA includes its current state, the unread portion of the input, and the current stack contents; nondeterministic PDAs may have multiple possible next IDs from the same ID.

Footnotes

  1. Pushdown automaton - Wikipedia - Defines PDA components, transition mechanism using state, input, and top stack symbol. ↩ ↩2 ↩3

  2. Pushdown automaton - Wikipedia - Acceptance by final state or empty stack; formal 7-tuple definition and notation. ↩

How a PDA Step Works (Stack View)

Think of the PDA as a finite controller plus a stack that supports LIFO behavior:

Keywords to remember:

  • LIFO Stack
  • Stack Top Symbol
  • ε-Transition
  • Transition Relation

Core PDA computation on an input string

  1. 1
    Step 1

    Start in state q0q_0 with initial stack symbol ZZ and the full input string unread.

  2. 2
    Step 2

    Use the current state, the next input symbol (or ε\varepsilon), and the top stack symbol to select a rule from δ\delta.

  3. 3
    Step 3

    Pop the top stack symbol AA, then push the replacement string α\alpha (which may be empty).

  4. 4
    Step 4

    Move to the next state, and if the transition reads aa then advance input; otherwise keep input position (for ε\varepsilon).

  5. 5
    Step 5

    Accept if a computation path reaches an accepting state after consuming all input or if the stack becomes empty, depending on the PDA’s acceptance mode.

Language Power: PDA ↔ Context-Free Languages

The most important “short note” statement is the equivalence:

  • A language is context-free iff there exists a PDA that recognizes it.
  • Deterministic PDAs (DPDAs) recognize deterministic context-free languages (DCFLs), a proper subset of CFLs.

Determinism vs Nondeterminism

  • A Nondeterministic PDA can branch; acceptance means some branch accepts.
  • A Deterministic PDA (DPDA) restricts choices so that each configuration has at most one possible move; it cannot recognize all CFLs. 2

Footnotes

  1. Pushdown Automata • Non-Context-Free Languages (TOC4 PDF) - States the theorem: a language is context-free iff some PDA recognizes it. ↩

  2. Deterministic pushdown automaton - Wikipedia - DPDA accepts deterministic context-free languages, a proper subset of context-free languages. ↩ ↩2

  3. Pushdown automaton - Wikipedia - Defines PDA components, transition mechanism using state, input, and top stack symbol. ↩ ↩2

Language classes by PDA type (high-level)

Deterministic PDAs are weaker than nondeterministic PDAs in general.

Pro Tip: What the stack is really doing

For CFLs, the stack tracks “unmatched structure” (e.g., pending aa’s in anbna^n b^n or nested parentheses). The PDA can remember an unbounded amount because the stack size grows with input.

Acceptance condition matters

Two common acceptance criteria are: final accepting state vs empty stack. Many PDA definitions are equivalent up to standard transformations, but you should not mix the criteria casually in proofs.

Short examples (intuition for stack usage)

Where PDAs fit in the automata hierarchy

No stack

Finite automata

Recognize regular languages."

Add one unbounded LIFO stack

Pushdown automata

Recognize exactly context-free languages (CFLs)."

Unbounded tape/memory

Turing machines

Recognize recursively enumerable languages."

Knowledge Check

Question 1 of 4
Q1Single choice

Which formal mechanism distinguishes a pushdown automaton (PDA) from a finite automaton?

Explore Related Topics

1

Post Correspondence Problem (PCP): Short Notes for Computation Theory

2

Constructing a PDA for $L=\{a^{2n}bc\mid n\ge 0\}$ (Final State and Empty Stack)

3

Write Short Notes on UML Diagrams

Browse all research articles