ToolSphere

PDA Simulator

Computer science

Simulate a pushdown automaton: write the transitions, test a string and see the stack at every move. Handles ε-moves and nondeterminism.

Pushdown automaton (PDA) simulator

Type an input to test the loaded example; edit its rules below. A PDA is a state machine with a stack, and ε means a move without reading input.

Accepted by final state in 5 moves.

Directives: accept: q2 (final state) or accept: empty (empty stack), stack: Z (start symbol), start: q0. Write ε as ε, e or eps.

Accepting computation

#StateRemaining inputStack (top first)Move
0q0aabbZstart
1q0abbAZδ(q0, a, Z) = (q0, AZ)
2q0bbAAZδ(q0, a, A) = (q0, AA)
3q1bAZδ(q0, b, A) = (q1, ε)
4q1εZδ(q1, b, A) = (q1, ε)
5q2εZδ(q1, ε, Z) = (q2, Z)

Each row is an instantaneous description (state, remaining input, stack). The search is breadth-first, so an accepting computation shown is the shortest one.

On this browser only

Give feedback

Did this tool help?

Tell us what worked, what didn’t, or what you’d like next.

Opens Google Forms in a new tab with this tool’s name filled in. No sign-in or email required. Feedback is optional.

Coming from JFLAP? See what carries over and what JFLAP still does better →

How to use PDA Simulator

  1. 1Load aⁿbⁿ, Even palindrome or Balanced brackets to start with working rules and a test input.
  2. 2Edit one transition per line as state, input, pop -> state, push. The push string lists the new stack top first.
  3. 3Set start: q0 and stack: Z as needed. Choose accept: q2 for final-state acceptance or accept: empty for empty-stack acceptance.
  4. 4Type a string without spaces; leave the input blank to test the empty string. Use ε, e, eps or epsilon in rules for empty input or an empty push.
  5. 5Read the verdict and the configuration table. Treat Search limit reached as inconclusive, and test both strings that should accept and strings that should reject.

About PDA Simulator

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.

Guides and tutorials

Frequently asked questions

Is this a PDA generator or a PDA simulator?

It simulates transition rules that you enter or load from examples. It does not generate a machine from a grammar or draw an editable state diagram.

How do I write an epsilon transition?

Use ε, e, eps or epsilon in the input position to move without consuming a character. The same notation in the push position means push nothing after popping the required top symbol.

Which end of the stack is the top?

The leftmost character is the top in both the rule replacement and the table. A replacement AZ puts A above Z, so keep the existing marker in the replacement if you need to preserve it.

How do I test the empty string?

Clear the Input string field completely. Do not type the epsilon character into that field, because epsilon notation belongs in the rules rather than in the tested string.

Can this simulate a nondeterministic pushdown automaton?

Yes, it explores alternative transitions breadth-first, including epsilon moves. A string accepts if a branch meets the acceptance condition after consuming all input, subject to the bounded search.

What is the difference between final-state and empty-stack acceptance?

Final-state acceptance checks the accepting state after all input is read. Empty-stack acceptance checks that the stack is empty after all input is read; switching directives may require changing the machine too.

Why is there still a stack symbol after acceptance?

Final-state acceptance does not require an empty stack. A bottom marker can remain when the entire input has been consumed and the machine is in an accepting state.

Does Search limit reached mean my string is rejected?

No, it means the bounded search did not establish acceptance or complete a rejection search. Check epsilon-push cycles and simplify the machine before drawing a conclusion.

Does the trace show all nondeterministic branches?

No, it shows a shortest accepting computation when one is found. Otherwise it shows a furthest explored computation, with the verdict distinguishing rejection from a search limit.

Can I prove a PDA is correct by testing strings?

Tests can expose a counterexample but do not prove a language-level claim. Describe a stack invariant and justify both acceptance of intended strings and rejection of unintended ones.

Have a suggestion for PDA Simulator?Share your feedback ↗