Theory of Computation

Open-source · Browser-based · No install

Theory of
Computation

An Interactive Simulator

First online edition · DFA · NFA · PDA · TM · Mealy · Moore

Open the simulator →Contents ↓
q0q1q2ababba

q0⊢q0⊢q1⊢q2⊢∈ F

§1 · DFA / NFA

Finite Automata

Place states, draw transitions, and test strings on deterministic and nondeterministic finite automata. Convert NFA to DFA with one click via subset construction — every intermediate DFA state is labeled with the NFA states it represents.

Fig 1.1 — DFA accepting strings ending in "aa"q0q1q2ababba
Fig 1.1 — DFA accepting strings ending in "aa"

§2 · PDA / NDPA

Pushdown Automata

Model stack-based computation with full stack-alphabet support using input,pop/push notation. Deterministic and nondeterministic variants share the same canvas, with the stack contents rendered live as you step through an input.

Fig 2.1 — PDA recognizing aⁿbⁿq0q1q2a,Z/XZa,X/XXb,X/ε
Fig 2.1 — PDA recognizing aⁿbⁿ

§3 · Single & multi-tape

Turing Machines

Build Turing machines with accept, reject, and normal states. Multi-tape support uses semicolon-separated transition segments, so each tape head reads, writes, and moves independently on every step.

Fig 3.1 — TM incrementing a binary stringq0q_acc0/1,R_/_,R
Fig 3.1 — TM incrementing a binary string

§4 · Mealy / Moore

Sequential Machines

Design output-producing machines. Mealy outputs on transitions; Moore outputs on states. Both share the finite-automaton canvas workflow, so switching between them keeps your layout and only changes how output is read.

Fig 4.1 — Mealy machine, parity of 1sevenodd1/11/00/0
Fig 4.1 — Mealy machine, parity of 1s

§5 · Regex → NFA → DFA, GNFA, CFG

Conversions

Type a regular expression and watch it convert to an NFA via Thompson's construction, then optionally determinize to a DFA via subset construction. Run it in reverse with GNFA state elimination to recover a regex from a saved automaton, or extract a Context-Free Grammar skeleton.

Fig 5.1 — Thompson construction, a single symbolq0q1a
Fig 5.1 — Thompson construction, a single symbol

§6 · Teams

Working Together

Create a team, invite collaborators with a code, and organize automatons into projects. Every submission keeps its full canvas layout, so teammates can open it straight into the simulator with the states exactly where you left them.

Open Teams →