Learn, Define, and SimulatePushdown Automata
A modern, interactive tool to build PDAs, visualize state transitions, and watch the stack evolve in real time. Perfect for students learning Theory of Computation and educators explaining context-free language recognition.
- Define
States, alphabets, and transitions
- Simulate
Step-by-step execution with stack
- Visualize
Graph view of states and edges
- Share
Import/export example machines
Tip: Use example PDAs like balanced parentheses, a^n b^n, palindromes, and wcw^R to get started fast.
How it works
Three simple steps to explore how PDAs recognize context-free languages.
Build your PDA
Add states, pick input/stack alphabets, and specify transitions with reads, pops, and pushes.
Run inputs
Execute step-by-step or auto-play. Watch the stack mutate and track branches with epsilon transitions.
Understand decisions
Inspect the execution steps and acceptance conditions: final state with empty input.
How it works
Three simple steps to explore how PDAs recognize context-free languages.
Build your PDA
Add states, pick input/stack alphabets, and specify transitions with reads, pops, and pushes.
Run inputs
Execute step-by-step or auto-play. Watch the stack mutate and track branches with epsilon transitions.
Understand decisions
Inspect the execution steps and acceptance conditions: final state with empty input.
What is a Pushdown Automaton (PDA)?
A Pushdown Automaton (PDA) is an extension of a finite automaton that has access to a stack. The stack gives the automaton extra memory, allowing it to recognize context-free languages (CFLs). Examples of context-free languages include balanced parentheses (), strings of the form a^n b^n, even-length palindromes, and mirrored patterns like w c w^R.
Formal Definition
A PDA is formally defined as a 7-tuple:
M = (Q, Σ, Γ, δ, q₀, Z₀, F) where:
- Q: finite set of states
- Σ: input alphabet
- Γ: stack alphabet
- δ: transition function
δ: Q × (Σ ∪ {ε}) × Γ → P(Q × Γ*)
(maps current state, input symbol, and stack top to next states and symbols to push) - q₀ ∈ Q: start state
- Z₀ ∈ Γ: initial stack symbol
- F ⊆ Q: set of accepting states
Acceptance Condition
A PDA accepts an input string if, after reading the entire string, it reaches an accepting state and the stack is in a valid final configuration. Epsilon (ε) transitions allow the PDA to change states or modify the stack without consuming input symbols.
Stack Behavior
The stack operates as a Last-In-First-Out (LIFO) memory. Push sequences are applied so that the leftmost symbol becomes the top of the stack. Pop operations compare against the top symbol of the stack. This mechanism enables recognition of nested and mirrored structures in the input.
Example: Balanced Parentheses PDA
This PDA accepts strings like (), (()), ()():
- δ(q0, '(', Z) = {(q1, XZ)}
- δ(q1, '(', X) = {(q1, XX)}
- δ(q1, ')', X) = {(q1, ε)}
- δ(q1, ')', Z) = {(q0, Z)}
Example: aⁿbⁿ PDA
Accepts strings with equal numbers of a's followed by b's, e.g., aaabbb:
- δ(q0, 'a', Z) = {(q0, AZ)}
- δ(q0, 'a', A) = {(q0, AA)}
- δ(q0, 'b', A) = {(q1, ε)}
- δ(q1, 'b', A) = {(q1, ε)}
- δ(q1, ε, Z) = {(q2, Z)}
Example: Even-length Palindrome PDA
Accepts strings like abba, baab:
- δ(q0, 'a', Z) = {(q0, AZ)}
- δ(q0, 'b', Z) = {(q0, BZ)}
- δ(q0, 'a', A) = {(q0, AA)}
- δ(q0, 'b', B) = {(q0, BB)}
- δ(q0, ε, Z) = {(q1, Z)}
- δ(q1, 'a', A) = {(q1, ε)}
- δ(q1, 'b', B) = {(q1, ε)}
- δ(q1, ε, Z) = {(q2, Z)}
Example: wcw⁻¹ PDA
Accepts strings of the form w c w^R:
- δ(q0, 'a', Z) = {(q0, AZ)}
- δ(q0, 'b', Z) = {(q0, BZ)}
- δ(q0, 'a', A) = {(q0, AA)}
- δ(q0, 'b', B) = {(q0, BB)}
- δ(q0, 'c', Z) = {(q1, Z)}
- δ(q1, 'a', A) = {(q1, ε)}
- δ(q1, 'b', B) = {(q1, ε)}
- δ(q1, ε, Z) = {(q2, Z)}
This PDA uses the stack to store symbols while reading the first part of the string and then matches them in reverse after the separator c. Acceptance occurs when the stack returns to its initial symbol and the PDA reaches an accepting state.
Solved Examples
Explore classic PDAs and try their inputs directly in the app.
Accepts strings of () that are properly balanced, e.g., "()", "(())", "()()".
Accepts strings where the number of a's equals the number of b's, e.g., "ab", "aabb", "aaabbb".
Accepts even-length palindromes over a small alphabet by mirroring symbols with the stack.
Accepts strings of the form w c w^R, using cas a separator between mirrored substrings.