Pushdown Automaton (PDA)

A Pushdown Automaton extends finite automata with a stack, an unlimited memory structure that lets it recognize languages no DFA or NFA can handle. If you've ever matched nested parentheses or parsed a programming language, you've encountered problems that need a PDA.

Theory

Formal definition

A PDA is defined as a 7-tuple (Q, Σ, Γ, δ, q₀, Z₀, F):

Symbol	Meaning
Q	Finite set of states
Σ	Input alphabet
Γ	Stack alphabet
δ	Transition function: Q × (Σ ∪ {ε}) × (Γ ∪ {ε}) → 𝒫(Q × Γ*)
q₀	Start state (q₀ ∈ Q)
Z₀	Initial stack symbol (Z₀ ∈ Γ)
F	Set of accepting/final states (F ⊆ Q)

The key difference from finite automata is Γ (the stack alphabet) and Z₀ (the initial stack symbol). These give the PDA memory that grows and shrinks as needed.

The stack

The stack is a LIFO (Last In, First Out) data structure. Think of it as a spring-loaded plate dispenser: you can only see and remove the top plate, and new plates go on top.

→Push: Place a symbol on top of the stack
→Pop: Remove the top symbol from the stack
→Peek: Read the top symbol without removing it

This stack gives PDAs "memory" that finite automata lack. A DFA has no way to count; it can't remember how many a's it's seen to match them with b's. A PDA can push a symbol for each a, then pop one for each b, accepting only when the counts match.

Transition function

Each PDA transition reads three things and produces two:

δ(current_state, input_symbol, stack_top) → (new_state, symbols_to_push)

→input_symbol can be ε (don't consume any input, i.e., an epsilon transition)
→stack_top can be ε (don't require any particular stack top)
→symbols_to_push can be ε (push nothing, effectively just popping)

For example, δ(q₀, a, Z) → (q₀, AZ) means: "In state q₀, reading a from input, with Z on top of the stack, move to state q₀, pop Z, and push AZ." The net effect is pushing A on top of Z.

Acceptance modes

There are two ways a PDA can accept a string:

By final state: The PDA accepts if, after consuming all input, it is in a state from F (an accepting state). The stack contents don't matter.

By empty stack: The PDA accepts if, after consuming all input, the stack is completely empty. The current state doesn't matter.

These two modes are equivalent in power: for any PDA accepting by final state, there exists a PDA accepting by empty stack for the same language, and vice versa. The constructions are straightforward but the resulting PDAs may look quite different.

Context-free languages

PDAs recognize exactly the class of context-free languages (CFLs). This is the same class of languages generated by context-free grammars (CFGs). The equivalence is fundamental:

→Every CFG has an equivalent PDA. Given a grammar, you can mechanically construct a PDA that simulates leftmost derivations.
→Every PDA has an equivalent CFG. Given a PDA, you can (less intuitively) construct a grammar that generates the same language.

This means PDAs sit squarely between finite automata and Turing machines in the Chomsky hierarchy:

Regular Languages ⊂ Context-Free Languages ⊂ Context-Sensitive Languages ⊂ Recursively Enumerable
   (DFA/NFA)              (PDA/CFG)                                           (Turing Machine)

Nondeterminism matters

Unlike finite automata (where DFA = NFA in power), nondeterministic PDAs are strictly more powerful than deterministic PDAs (DPDAs).

→A DPDA has at most one move in any configuration (no choices). DPDAs recognize a proper subset of CFLs called deterministic context-free languages (used in most programming language parsers).
→A nondeterministic PDA (NPDA) can have multiple possible transitions from the same configuration. It accepts if any computation path leads to acceptance.

The classic example: the language of even-length palindromes {wwᴿ | w ∈ {a,b}*} requires nondeterminism because the PDA must "guess" the middle of the string. No DPDA can recognize this language.

StateForge simulates the full nondeterministic PDA, exploring all possible computation paths simultaneously.

Classic examples

Language	Description	Key Insight
{aⁿbⁿ \| n ≥ 0}	Equal a's and b's	Push on `a`, pop on `b`
Balanced parentheses	Nested ( and )	Push on `(`, pop on `)`
{wwᴿ}	Even palindromes	Push first half, match second half (nondeterministic)
{wcwᴿ}	Palindromes with center	Push until `c`, then match (deterministic)

Limitations

PDAs cannot recognize everything. The language {aⁿbⁿcⁿ | n ≥ 0} (equal numbers of a's, b's, and c's) is not context-free because a single stack can't simultaneously track two independent counts. This language is context-sensitive, requiring a more powerful model (like a linear bounded automaton or Turing machine).

Other non-CFL examples: {aⁿ | n is prime}, {aⁿ² | n ≥ 0}, and the copy language {ww | w ∈ {a,b}*} (note: ww, not wwᴿ).

Using PDA in StateForge

Switching to PDA mode

Press 3 on your keyboard or select PDA from the mode dropdown in the sidebar. The editor switches to PDA mode with:

→Transition labels in input, pop → push format
→Stack visualization in the simulation panel
→Acceptance mode toggle (Final State / Empty Stack)

Transition format

PDA transitions in StateForge use the format:

input, pop → push

Part	Meaning	Example
input	Symbol to read from input (or ε to read nothing)	`a`, `b`, `ε`
pop	Symbol expected on top of stack (or ε for no requirement)	`Z`, `A`, `ε`
push	Symbols to push onto stack (or ε to push nothing)	`AZ`, `A`, `ε`

Examples:

→a, Z → AZ: read a, pop Z, push AZ (net: push A on top of existing Z)
→b, A → ε: read b, pop A, push nothing (net: just pop A)
→ε, Z → ε: read nothing, pop Z, push nothing (used for empty-stack acceptance)
→ε, ε → S: read nothing, require nothing on stack, push S

Stack symbol conventions

→Z: the initial bottom-of-stack marker. Every PDA in StateForge starts with Z on the stack. It's a sentinel; when you see Z on top, the stack is logically empty.
→ε: represents "nothing." As pop: don't check the stack. As push: don't push anything. As input: don't consume any character.

Push convention

When pushing multiple characters, the leftmost character ends up on top of the stack.

For push = AZ:

→Z is pushed first (goes deeper)
→A is pushed second (becomes the new top)

So after a, Z → AZ, the stack reads A on top, Z below, identical to the original stack with A added on top.

Internally, the push string is reversed and each character is pushed individually, so AZ means the top-of-stack (TOS) is A.

Multiple transitions

Unlike DFA (where each state has exactly one transition per symbol), PDA allows multiple transitions between the same pair of states, and even multiple transitions from the same state on the same input. This is where nondeterminism comes from.

Each transition edge can carry multiple PDA transition entries. Click a transition to edit, and add as many input, pop → push rules as needed.

Simulation

The PDA simulator explores all possible computation paths simultaneously. Each path is tracked as a configuration, a triple of (current state, input position, stack contents).

Controls:

Button	Action
▶ Start	Initialize simulation with input string
⏭ Step	Advance all active configurations by one step
⏩ Fast Run	Run up to 500 steps automatically
↺ Reset	Clear simulation state

What you see during simulation:

→Active Configs — Each row shows: state name, input position, and current stack contents in [brackets]
→Input Tape — Visual tape with highlighting for consumed/current positions
→Stack Visualization — A vertical stack display (desktop only) showing the top configuration's stack, with the top-of-stack highlighted

As you step through, configurations branch when nondeterministic choices exist (e.g., a state has both an ε-transition and an input-consuming transition). Dead-end branches are pruned as rejected.

Acceptance toggle

In the simulation panel header, toggle between:

→Final State — Accepts when all input is consumed AND the PDA is in an accepting state (double circle)
→Empty Stack — Accepts when all input is consumed AND the stack is completely empty

Choose the mode that matches your PDA's design. Some PDAs are naturally designed for one mode over the other.

Safety limits

Nondeterministic PDAs can produce an exponential number of configurations, especially with ε-transitions that loop. StateForge enforces a 10,000 configuration limit. If the total number of configurations created during simulation exceeds this, the simulation halts to prevent your browser from freezing.

If you hit this limit:

→Check for ε-transition loops (ε-transitions that cycle without consuming input or changing the stack)
→Simplify the PDA or test with shorter input strings

Fast run

Fast Run executes up to 500 steps in one click, giving you instant accept/reject results without stepping manually. Ideal for testing your PDA against multiple inputs quickly.

Gallery examples

StateForge includes pre-built PDA examples in the gallery:

Example	Language	Description
aⁿbⁿ	{aⁿbⁿ \| n ≥ 0}	The classic PDA example: push for a's, pop for b's
Balanced Parentheses	Matched ( and ) with nesting	Push on open, pop on close
Palindromes	{wwᴿ \| w ∈ {a,b}*}	Nondeterministic: must guess the middle
wcwᴿ	{wcwᴿ \| w ∈ {a,b}*}	Deterministic: center marker `c` eliminates guessing

Load these from the sidebar gallery to study how they work, then modify them or build your own.

Tips

→
Always use Z as your bottom marker. StateForge initializes every PDA stack with Z. Design your transitions around it; checking for Z tells you when the stack is "logically empty," which is essential for clean acceptance conditions.
→
Push ε to pop without pushing. The transition b, A → ε pops A and pushes nothing. This is how you consume stack symbols during the matching phase, like popping one A for each b in the aⁿbⁿ language.
→
Multiple active configurations = nondeterminism in action. If you see more than one active config during simulation, your PDA is exploring multiple branches. This is normal and expected. Remember, a nondeterministic PDA accepts if any branch accepts.
→
Test with empty string. Don't forget edge cases! The empty string (ε) should be accepted by {aⁿbⁿ} (when n=0) but rejected by many other languages.
→
Beware ε-loops. An ε-transition that doesn't change the stack or state creates an infinite loop. The 10,000-config safety limit will catch this, but it's better to design around it.
→
Start simple. Build the aⁿbⁿ PDA first. It's the "hello world" of pushdown automata. Once that clicks, palindromes and more complex languages follow naturally.

NFA

Turing Machine