Pushdown automata

PDA drawer · Chapter 2.2

Automaton

Color states: start, accepting

Selection

Nothing selected. Click a state or an arrow to edit it.

Input string

Test many strings at once

Draw and simulate pushdown automata

A pushdown automaton is an NFA with a stack (Sipser, Chapter 2.2). Draw one with Sipser's labels, run strings through it and watch the stack change step by step, read off its formal definition, and build a PDA from any context-free grammar.

Writing transition labels

Type	Means
`a,b->c` or `a,b→c`	read a, pop b, push c
`ε` (or leave it out)	read nothing, pop nothing or push nothing
`0,ε→0; 1,ε→1`	two rules on one arrow, drawn on two lines
`ε,ε→S$`	push a string: S ends up on top
`$`	a symbol like any other, usually marking the bottom of the stack

How a PDA runs

It starts in the start state with an empty stack.
A rule a,b→c can be used when the next input symbol is a (or a is ε) and b is on top of the stack (or b is ε).
The PDA is nondeterministic: it accepts when some branch reads the whole input and is then in an accepting state. The stack does not have to be empty.
Test finds the shortest accepting computation and steps through it with the stack drawn beside it.

Drawing

Double-click to add a state, and Shift + drag (or the Transition tool) to add an arrow.
Select an arrow and type its rules. Use ; new rule to stack another rule on the same arrow.
Export as PNG, SVG, LaTeX (TikZ) or JFLAP. JFLAP starts its PDAs with Z on the stack; DeltaDraw follows Sipser and starts with an empty stack.