PDA, Stack

Pushdown Automata (PDA)

Finite Automata with Stack Memory for context-free Languages

What is a Pushdown Automaton?

A Pushdown Automaton (PDA) is a finite automaton equipped with a stack (LIFO memory). PDAs are more powerful than finite automata and can recognize context-free languages, which include nested structures like balanced parentheses, palindromes, and programming language constructs.

Formal Definition: A PDA is a 7-tuple M = (Q, Σ, Γ, δ, q₀, Z₀, F) where:
  • Q: Finite set of states
  • Σ: Input alphabet
  • Γ: Stack alphabet
  • δ: Transition function δ: Q × (Σ ∪ @{ε@}) × Γ → P(Q × Γ*)
  • q₀: Initial state
  • Z₀: Initial stack symbol
  • F: Set of final states
Example Language: L = @{a^n b^n | n ≥ 1@} = @{ab, aabb, aaabbb, ...@}

Visual PDA simulator

Interactive simulation of a PDA that accepts L = @{a^n b^n | n ≥ 1@}

PDA for L = @{a^n b^n | n ≥ 1@}
Input Tape
Position: 0
Stack
Z₀
Top: Z₀
Current State
q₀
Status: Running
1000ms

Transition Table

PDA transitions for L = @{a^n b^n | n ≥ 1@}

State Input Stack Top Next State Stack operation
q₀ a Z₀ q₁ Push A
q₁ a A q₁ Push A
q₁ b A q₂ Pop A
q₂ b A q₂ Pop A
q₂ ε Z₀ q₃ -

Interactive PDA Tester

Test strings with the PDA for L = @{a^n b^n | n ≥ 1@}