⊢

PDA Simulator

Universal NPDA Engine
State Diagram Select a language to begin
◈ Run a simulation to see the current computation phase.
Input Tape
Stack
▩ Bottom (Z₀)
⚙ Step Explanation

Run the simulation or press Step to see detailed explanations for each transition.

Theory

What is a Pushdown Automaton?

A powerful computational model that extends Finite Automata with an unbounded stack memory.

🤖

Informal Definition

A PDA is like a Finite Automaton but with a stack (LIFO memory). It reads input symbols one at a time and can push or pop symbols from the stack. The stack gives it more power — PDAs can recognize all Context-Free Languages, which FAs cannot.

🧮

Formal Definition

A PDA is a 7-tuple M = (Q, Σ, Γ, δ, q₀, Z₀, F) where:

  • Q — finite set of states
  • Σ — finite input alphabet
  • Γ — finite stack alphabet
  • δ — transition function: Q × (Σ ∪ {ε}) × Γ → P(Q × Γ*)
  • q₀ ∈ Q — initial state
  • Z₀ ∈ Γ — initial stack symbol
  • F ⊆ Q — set of accepting states
📚

Acceptance

A string is accepted if the PDA reaches a final state after reading all input (acceptance by final state), or if the stack becomes empty (acceptance by empty stack).

Final State OR Empty Stack
⚡

vs Finite Automata

FeatureFAPDA
MemoryNoneUnbounded Stack
LanguagesRegularContext-Free
aⁿbⁿ❌✅
wcwᴿ❌✅

Acceptance Methods

In PDA theory, string acceptance determines whether a string belongs to the language. There are two equivalently powerful but conceptually distinct methods.

Method 1

Acceptance by Final State (L(P))

A PDA accepts a string if, after consuming the entire input, it is in one of the designated final states (F). The stack contents are completely ignored.

Formal Definition:

L(P) = { w | (q₀, w, Z₀) ⊢* (qf, ε, x), qf ∈ F }

Key Points:

  • Final state qf must be in F
  • Stack can contain any symbols x ∈ Γ*
  • Mimics how Finite Automata accept strings
  • Useful when language structure maps naturally to states
Simulation Example — L = { aⁿbⁿ | n ≥ 1 }
1Start at q₀, stack = [Z₀]
2Read each 'a' → push A onto stack
3Read each 'b' → pop A from stack
4ε-transition when stack top = Z₀ → move to qf
✓Halt at qf ∈ F — ACCEPTED by Final State
Method 2

Acceptance by Empty Stack (N(P))

A PDA accepts a string if, after consuming the entire input, the stack is completely empty (often called the "null" or initial state of the stack). The current state is irrelevant.

Formal Definition:

N(P) = { w | (q₀, w, Z₀) ⊢* (q, ε, ε), q ∈ Q }

Key Points:

  • Stack must be empty (ε) after all input consumed
  • Final state is irrelevant — any state q ∈ Q works
  • Often simpler for languages where symbols must be matched exactly
  • ε-transitions are crucial for "cleaning" the stack bottom Z₀
Simulation Example — L = { aⁿbⁿ | n ≥ 1 }
1Start at q₀, stack = [Z₀]
2Read each 'a' → push A (stack grows)
3Read each 'b' → pop A (stack shrinks)
4ε-transition on Z₀ → pop Z₀ (stack now empty)
✓Stack = ∅ — ACCEPTED by Empty Stack

Key Differences Summary

FeatureEmpty Stack (N(P))Final State (L(P))
Acceptance CriteriaStack is empty (ε)Machine is in qf ∈ F
Stack ContentMust be emptyIrrelevant (any x ∈ Γ*)
Final StateIrrelevant (any q ∈ Q)Must be in F ⊆ Q
EquivalenceYes (CFLs)Yes (CFLs)

⚡ Theorem: Both acceptance methods are equivalent in expressive power — every CFL accepted by one method can be accepted by the other. A PDA accepting by final state can always be converted to one accepting by empty stack, and vice versa.

ε-Transitions (Epsilon Moves)

What is an ε-Transition?

An ε-transition (epsilon move) allows the PDA to change state or manipulate the stack without consuming any input symbol. It is a "free move" purely driven by the stack top.

Notation: δ(q₁, ε, Z₀) = (qf, ε)

This means: from state q₁, if stack top = Z₀, move to qf and pop Z₀ — without reading any input.

Role in Acceptance

ε-transitions are critical for bridging between acceptance methods:

  • Final State PDA: Use ε-transition from matching state to qf
  • Empty Stack PDA: Use ε-transitions at end to pop remaining stack symbols
  • Phase Switching: Move between phases (push → pop) without consuming input
  • Multi-phase PDAs: ε-transitions connect computation phases cleanly

Classic Languages

L = { aⁿbⁿ | n ≥ 1 }

Equal number of a's and b's. Example: ab, aabb, aaabbb

Strategy: Push A for each 'a', pop A for each 'b'. Accept when stack returns to Z₀.

Balanced Parentheses

Correctly matched parentheses. Example: (), (()), (()())

Strategy: Push P for each '(' and pop for each ')'. Accept when stack empty at end.

L = { aⁿb²ⁿ | n ≥ 1 }

Twice as many b's as a's. Example: abb, aabbbb, aaabbbbbb

Strategy: Push 2 A's per 'a' (net +2). Pop 1 A per 'b'. Accept when 2n pops clear the stack.

L = { wcwᴿ | w ∈ {a,b}* }

Palindrome with explicit centre marker 'c'. Example: abcba, aabcbaa

Strategy: Push each symbol of w. On 'c', switch to pop mode and match wᴿ symbol by symbol.

Note: This requires a DPDA — the 'c' acts as an unambiguous pivot.

Summation Languages (Three-Variable)

These languages require multi-phase stack logic with ε-transitions between phases.

L = { aⁿbᵐcⁿ⁺ᵐ | n, m ≥ 1 }

Total c's = n+m. Example: abcc, aabccc, aabbcccc

Strategy: Push A for each 'a', push B for each 'b'. Stack depth = n+m. Pop one symbol per 'c'.

Phases: Push-a → Push-b → Pop-c

L = { aⁿbⁿ⁺ᵐcᵐ | n ≥ 1, m ≥ 0 }

First n b's match a's; extra m b's verified by c's. Example: ab, abbc, aabbbcc

Strategy: Push A per 'a'. Pop A per 'b' (n-match). When A's exhausted, push B for extra b's. Pop B per 'c'.

Phases: Push-a → Pop-A(b) → Push-B(b) → Pop-B(c)

L = { aⁿ⁺ᵐbᵐcⁿ | n, m ≥ 0 }

Push all a's (n+m), pop m for b's, pop n for c's. Example: ac, aabc, aaabcc

Strategy: Push A for every 'a'. Pop A per 'b' (the m-component). Pop A per 'c' (the n-component).

Phases: Push-a(n+m) → Pop-A(b) → Pop-A(c)

⚙ PDA Metadata
📋 Quick-Parse Textbook Rules
One rule per line. Formats accepted:
q0, a, Z0 -> q0, A Z0
q0, b, A  -> q1, ε
q1, ε, Z0 -> q2, Z0
↓ Load a Built-in Preset

Transition Rules

δ(From, Input, StackTop) → (To, Push)

0 rules
# From State Input (ε ok) Stack Top → To State Push (space-sep, ε=pop)