What this pushdown automata simulator does
A pushdown automaton combines a finite-state controller with a stack. In a Theory of Computation course, that extra memory lets you describe context-free languages such as balanced parentheses and equal-length runs of a followed by b. This PDA simulator tests a string against transition rules and shows the state, remaining input and stack along a computation. A working example is loaded, so you can study its behavior before editing the machine.
Searches for a PDA maker or pushdown automata generator can mean different things. This page runs a machine you describe in text; it does not automatically construct a PDA from a grammar, generate a state diagram or prove that your machine recognizes an entire language. Use it to check individual computations and find counterexamples while developing a separate correctness argument.
Transition notation and the stack update
Write each rule as current state, input symbol, popped symbol -> next state, pushed string. For example, q0, a, Z -> q0, AZ consumes a, removes the top Z, replaces it with AZ and stays in q0. The leftmost character of the push string becomes the new top. Z remains underneath A because it appears in the replacement; it is not preserved automatically.
The update rule is new stack = push string + old stack below the popped symbol. The machine must match the current state and top symbol before a rule can run. A nonempty input symbol must also match the next unread character. Each rule pops exactly one stack symbol, while the push can replace it with a string or with nothing.
Write ε, e, eps or epsilon to consume no input, or use one of those spellings in the push position to push nothing. An epsilon input does not mean the input must already be exhausted: it can run whenever the state and stack conditions match. To preserve a top symbol during such a move, push that symbol back explicitly.
Set the start and acceptance rules
Use start: q0 to name the initial state and stack: Z for the starting stack. With accept: q2, acceptance requires all input to be read and the state to be accepting; the stack may still contain symbols. With accept: empty, all input must be read and the stack must be empty, regardless of the state.
Those acceptance conventions characterize the same class of languages when machines are transformed appropriately. Merely changing the directive on an existing machine does not guarantee equivalent behavior. In particular, a final-state machine that deliberately leaves its bottom marker needs an additional design change before it can accept by empty stack.
Worked aⁿbⁿ example: aabb
Load aⁿbⁿ and use its default input aabb. Running the simulator library gives acceptance by final state in 5 moves. The computation table contains the starting configuration followed by each transition; ε below means an empty remaining input.
| Move | State | Remaining input | Stack, top first |
|---|---|---|---|
| 0 | q0 | aabb | Z |
| 1 | q0 | abb | AZ |
| 2 | q0 | bb | AAZ |
| 3 | q1 | b | AZ |
| 4 | q1 | ε | Z |
| 5 | q2 | ε | Z |
The a-reading phase pushes A markers. The first b changes to the popping phase, and subsequent b symbols remove matching markers. Once only Z remains, an epsilon move reaches q2. The final Z is valid because this example accepts by final state. The accepting branch consumes the whole string before the verdict becomes true.
Now change the input to aab. The library rejects it after exploring 5 configurations: the furthest displayed branch reads the input but leaves AZ in q1, so it cannot take the final transition requiring Z on top. The empty input is accepted in 1 move by the example's direct epsilon transition to q2. The string abab is rejected even though its symbol counts match, because this machine requires all a symbols before the b phase. These checks test different aspects of the intended language.
Nondeterminism and search limits
The even-palindrome example guesses the midpoint using epsilon moves. Several branches may fail while another accepts; a failed branch alone cannot establish rejection. The simulator searches configurations breadth-first, remembering configurations it has already visited. An accepting path it displays is a shortest accepting computation in number of moves, rather than a list of every branch considered.
For a rejected run, the table shows a furthest computation explored, not a proof covering every possible input string. A Search limit reached result is explicitly inconclusive. The implementation caps the search at 20,000 configurations and the stack at 200 symbols. A rule that repeatedly pushes on epsilon input can reach those limits without consuming more input. Simplify such cycles before interpreting a bounded run.
Common mistakes when testing a PDA
Check push order before changing the state logic: reversing AZ to ZA puts the bottom marker on top. Do not use epsilon as the popped symbol, because this format always requires a real top symbol. Do not assume reaching an accepting state early accepts an unread suffix. The input field expects a single string without whitespace; deleting its contents tests the empty string rather than typing an epsilon character there.
For homework, pair an accepted example with a missing-symbol case, a wrong-order case and the empty string. Explain the stack invariant in words alongside your trace. A successful test is evidence about that input, while an invariant explains why the construction works more generally.
Continue studying automata
Follow the PDA worked example for a longer construction walkthrough. Compare finite-state behavior with the NFA and DFA simulator, which has no stack. The Turing machine simulator uses a writable tape instead. To examine how a grammar derives a string, use the parse tree generator alongside your machine trace.