How to use the Pushdown Automaton Simulator
- 1. Type the transitionsOne per line: state, input, stack top -> new state, push string. Use ε for no input or for a pop.
- 2. Set the PDAEnter the start state, start stack symbol and final states, or choose acceptance by empty stack.
- 3. Run a stringSee whether it is accepted, the sequence of IDs (state, input left, stack) and whether the PDA is deterministic.
How a PDA moves
A move δ(q, a, X) = (p, γ) means: in state q, reading a (or nothing, for ε) with X on top of the stack, go to p and replace X by the string γ. The leftmost symbol of γ becomes the new top. γ = ε pops X; γ = X leaves it; γ = aX pushes a.
An instantaneous description (ID) (q, w, γ) records the state, the input still to read and the stack with its top on the left. A string is accepted by final state if some sequence of moves reads all of it and ends in a final state, or by empty stack if it ends with an empty stack.
Worked example: aⁿbⁿ
The default PDA pushes an a for each a, pops one for each b and moves to the final state q2 when only Z is left.
For aabb: (q0, aabb, Z) ⊢ (q0, abb, aZ) ⊢ (q0, bb, aaZ) ⊢ (q1, b, aZ) ⊢ (q1, ε, Z) ⊢ (q2, ε, Z). The input is used up and q2 is final, so aabb is accepted in 5 moves. For aab the stack still holds a when input runs out, so no move reaches q2.
Hopcroft–Ullman's PDA for wwR guesses the middle with ε-moves. It is nondeterministic, and the simulator tries every guess: 1111 is accepted in 6 moves.
Frequently asked questions
What makes a PDA deterministic?
From any state and stack top there is at most one move for each input symbol, and if there is an ε-move there is no input move at all. The tool checks this.
How does the simulator handle nondeterminism?
It explores every branch breadth-first and stops at the first accepting ID, so the sequence shown is the shortest.
Why might the result say the search limit was reached?
Some PDAs push forever on ε-moves. The tool stops after 20,000 configurations or a very deep stack.
Can stack symbols have more than one character?
Yes, like Z0. The push string is split using the symbols that appear as stack tops, longest first.