A pushdown automaton (PDA) is a finite‑state machine that uses a stack to store and retrieve symbols, allowing it to process languages with nested structure.
Core components of a PDA
A PDA consists of five main parts:
- Finite‑state control – a set of states that drive the machine’s behavior.
- Input tape – a read‑only strip containing the string to be processed.
- Stack alphabet – symbols that can be pushed onto or popped from the stack.
- Stack – a last‑in, first‑out memory that can grow arbitrarily large.
- Transition function – determines how the machine moves between states and manipulates the stack.
Formal definition
A PDA is defined by the 7‑tuple M = (Q, Σ, Γ, δ, q₀, Z₀, F) where:
- Q is a finite set of states.
- Σ is the input alphabet.
- Γ is the stack alphabet.
- δ : Q × (Σ ∪ {ε}) × Γ → P(Q × Γ*) is the transition function.
- q₀ ∈ Q is the start state.
- Z₀ ∈ Γ is the initial stack symbol.
- F ⊆ Q is the set of accepting states.
How a PDA works
During computation a PDA’s configuration is represented as an instantaneous description (q, w, γ) where q is the current state, w is the remaining input, and γ is the stack content. A transition replaces the top stack symbol and may consume an input symbol, moving to a new state.
Recognizing a classic language
Consider the language {0ⁿ1ⁿ | n ≥ 0}. A PDA can:
- Read each 0 and push a marker onto the stack.
- When the first 1 appears, pop one marker for each 1 read.
- Accept if the input is exhausted exactly when the stack returns to its initial symbol.
Deterministic vs. nondeterministic PDAs
Deterministic PDAs (DPDA) have at most one transition for any combination of state, input symbol, and stack top. Nondeterministic PDAs (NPDA) may have multiple possible transitions, allowing them to guess which path leads to acceptance. Both recognize the same class of languages, but DPDA are less powerful in terms of the languages they can accept by state alone.
Why a stack matters
Finite‑state machines cannot count arbitrarily large numbers or remember nested structures because they lack memory. The stack gives a PDA the ability to store an unbounded sequence of symbols, enabling it to handle patterns like matched parentheses, nested loops, and balanced brackets—all characteristic of context‑free languages.