Tools

Construct Pushdown Automata

Pushdown Automata (PDA)

A Pushdown Automaton (PDA) is a finite-state control augmented with a LIFO stack. Compared to a DFA (which has only finite memory), a PDA has unbounded memory via its stack, which lets it recognize all context‑free languages.

PDA ≈ “finite-state machine” + “stack”.

Core Components

  • Input tape: a read-only tape scanned left to right.
  • Finite control: the current state and transition logic.
  • Stack: unbounded height; top-only access (push/pop/replace).

Stack Operations

  • Push: write one or more symbols on top of the stack.
  • Pop: remove the top symbol.
  • Replace: pop the top symbol and push a (possibly empty) string of stack symbols (general form used by the transition function).

Formal Definition (corrected)

A PDA is a 7‑tuple M = (Q, Σ, Γ, δ, q0, Z0, F) where:

  • Q: finite set of states
  • Σ: input alphabet
  • Γ: stack alphabet
  • δ: transition function
    δ: Q × (Σ ∪ {ε}) × Γ → 𝒫(Q × Γ*)
    Intuition: if (p, γ) ∈ δ(q, a, X), then from state q, reading input symbol a (or ε), with X on top of the stack, the PDA may move to state p and replace X by the string γ (which may be ε).
  • q0 ∈ Q: initial state
  • Z0 ∈ Γ: initial stack symbol (bottom marker)
  • F ⊆ Q: set of accepting states

Acceptance

  • By final state: input is fully consumed and the current state is in F.
  • By empty stack: input is fully consumed and the stack is empty (besides the bottom marker, depending on convention).

These acceptance modes are equivalent in power: for any PDA using one mode, there exists an equivalent PDA using the other (possibly with minor construction changes).

Deterministic vs. Nondeterministic

  • NPDA (general case): δ may return multiple choices; used in most theoretical and tool settings.
  • DPDA: restricted so that each configuration has at most one move (no nondeterminism and no conflicting ε‑moves).

This revised theory corrects earlier inaccuracies—especially the transition function, which must map to a set of state/stack‑string pairs—and uses standard notation (Γ for stack alphabet, Z0 for the initial stack symbol, F ⊆ Q).