Automata Playground

Alphabet Σ 0

Stack Γ 0

Output Δ 0

States Q 0

No states

Transitions δ 0

No transitions

Overview

Language DFA

—

M = (Q, Σ, δ, q₀, F)

Simulate

Run a string to simulate…

Batch Test

Foundations

Chomsky Hierarchy Finite Automata Regular Languages Regular Grammars Regex and Automata DFA Decision Procedures

Grammar and PDAs

Context-Free Languages CFG Analysis Normal Forms and CYK DPDA, NPDA, CFG

Computability

Turing Machines UTM and NDTM Undecidability Complexity Theory

Reference Cards

Key Algorithms Closure Properties Myhill-Nerode

Transducers & Extensions

Moore Machines Mealy Machines Multi-Tape TMs

Interactive

RL Pumping Lemma CFL Pumping Lemma Closure Table Decidability Table

Revision

Revision Summary

Chomsky Hierarchy

Classification of formal languages by generative power (Type 3 → Type 0)

RL Pumping Lemma Explorer

Verify or disprove pumping conditions for regular languages

If L is regular, ∃p≥1 s.t. ∀w∈L with |w|≥p, ∃xyz=w where:
(1) |xy|≤p (2) |y|≥1 (3) ∀i≥0, xyⁱz ∈ L

Pump length p String w

Split |x| Split |y| Pump i

Strategy for Minimum Pumping Length:
The minimum pumping length $p$ is the smallest integer where the rule holds. To find it, hunt for the shortest string in the language that cannot be pumped. If a string of length $k$ cannot be split into $xyz$ such that $xy^iz \in L$ for all $i \ge 0$, then $p$ must be at least $k+1$.

Closure Properties Table

Click operations to see which language classes are closed under each

CFL Pumping Lemma Explorer

Interactive tool for Context-Free Languages — Ogden's Lemma variant

If L is CFL, ∃p≥1 s.t. ∀w∈L with |w|≥p, ∃uvxyz=w where:
(1) |vxy| ≤ p (2) |vy| ≥ 1 (3) ∀i≥0: uvⁱxyⁱz ∈ L

Pump length p String w

|u| |v| |x| |y| Pump i

Decidability Reference

Decision problems by language class

Language Class	Membership	Emptiness	Equivalence	Universality
Regular (DFA)	Decidable	Decidable	Decidable	Decidable
CFL (CFG/DPDA/NPDA)	Decidable (CYK)	Decidable	Undecidable	Undecidable
CSL (LBA)	Decidable	Undecidable	Undecidable	Undecidable
RE (TM)	Semi-decidable	Undecidable	Undecidable	Undecidable
Non-RE	Undecidable	Undecidable	Undecidable	Undecidable

Rice-Shapiro Rule (Recognizability):
A property is Turing-recognizable (RE) if it satisfies the Finite Subset Rule (if $L$ has the property, a finite subset must trigger it) and Monotonicity (if finite $L_1$ has it, any $L_2 \supseteq L_1$ also has it). Properties like "is finite" or "is empty" fail these and are strictly unreachable by finite proof.

Green = Decidable (always halts, correct answer) Orange = Semi-decidable (halts on yes, may loop on no) Red = Undecidable (no algorithm exists)

Esc	Pointer — normal cursor, drag states to move
V	Pan — drag canvas to pan, drag states to move
S	State — click canvas to place state
T	Transition — click source then target state
D	Delete — click state to remove
X	Clear — delete all states and transitions

1	Switch to Build view
2	Switch to Algorithms view
3	Switch to Grammar view
4	Switch to Theory view

Ctrl+Z	Undo last action
Ctrl+Y	Redo last undone action
Ctrl+S	Save automaton as JSON

Arrow Right / Enter	Step simulation forward
Arrow Left	Step simulation backward
Escape	Cancel current action / close modal

Scroll Wheel	Zoom in / out
+ / =	Zoom in
− / _	Zoom out
H	Fit to screen (show all states)
F	Fullscreen mode
Middle Mouse / Alt+Drag	Pan the canvas
Double-click state	Toggle accept state
Right-click state / transition	Context menu (state and transition actions)
Space + drag	Pan the canvas temporarily
Drag toolbar handle	Dock the toolbar to any canvas edge
Click the active tool button	Return to Pointer

Context-Free Grammar