Draw it, run it, prove it.

Theory of Computation

step by step

DeltaDraw is a free companion for a Theory of Computation course. Pick your chapter, draw the machine, and watch it compute one step at a time: finite automata, regular expressions, grammars, pushdown automata and Turing machines, through decidability and NP-completeness.

Follows Michael Sipser, Introduction to the Theory of Computation, 3rd edition (Cengage Learning, 2013). Section, example and theorem numbers on this site match the book.

Open finite automata See all chapters
q0 q1 q2 0,1 0 1
An NFA for binary strings that end in 01, drawn in DeltaDraw.

Chapters

Follows the chapter order of Sipser, Introduction to the Theory of Computation (3rd edition). Choose the section your class is on.

1

Regular languages

1.1Available

Finite automata

Draw DFAs, test strings, minimize step by step, and combine machines: union, intersection, complement and equivalence.
1.2Available

Nondeterminism

Simulate NFAs and ε-NFAs, and convert an NFA to a DFA step by step with the subset table.
1.3Available

Regular expressions

Regular expression to NFA and NFA to regular expression, step by step. Test strings and compare expressions.
1.4Available

Nonregular languages

Prove a language is not regular with the pumping lemma, played as a game against an adversary.
2

Context-free languages

2.1Available

Context-free grammars

Test strings, draw parse trees and leftmost derivations, find ambiguity, and convert to Chomsky normal form and CYK step by step.
2.2Available

Pushdown automata

Draw a PDA, run strings step by step with the stack drawn beside it, and convert a grammar to a PDA.
2.3Available

Non-context-free languages

Prove a language is not context-free with the pumping lemma for CFLs, case by case.
3

The Church–Turing thesis

3.1Available

Turing machines

Draw a Turing machine and watch the head move on the tape, with Sipser-style configurations at every step.
4–5

Decidability and reducibility

4.1Available

Decidable languages

Ask decidable questions about your own DFAs: is the language empty? Are two DFAs equal?
4.2Available

Undecidability

Diagonalization, shown step by step.
5.2Available

Post Correspondence Problem

An undecidable problem you can play as a domino puzzle.
7

Time complexity

7.1–7.2Available

Growth rates and P

Compare n², n³ and 2ⁿ as the input grows.
7.3–7.4Available

NP and NP-completeness

Small SAT and CLIQUE demos: easy to check an answer, hard to find one.
Practice

Exercises and exams

Chapter 1Available

Practice exercises

22 exercises on DFAs, NFAs, minimization and regular expressions. Press Check and get a counterexample if it is wrong.
Chapters 2–3Available

Practice: grammars, PDAs, TMs

28 exercises in the Practice tab of the Grammars (13), Pushdown automata (8) and Turing machines (7) pages, checked with counterexamples.
InstructorsAvailable

Exam mode

A drawing-only version for proctored online exams. Answers are saved as images for Canvas.

Draw it, run it, prove it

DeltaDraw is a free, browser-based learning platform for a Theory of Computation course, organized by the chapters of Sipser's Introduction to the Theory of Computation. Students draw and run machines, follow every construction one step at a time, and practice with exercises that are checked instantly. Nothing to install and no account: drawings stay in your own browser.

What you can do

  • Draw and run DFAs, NFAs, pushdown automata and Turing machines, with the input, stack or tape shown at every step
  • Convert step by step: NFA → DFA, DFA minimization, regex ⇄ NFA, grammar → Chomsky normal form, CYK, grammar → PDA
  • Prove: the pumping lemma as a game for regular and context-free languages, with a proof outline
  • Decide: run the EDFA, EQDFA and ECFG deciders, follow the diagonal proof that ATM is undecidable, and play the Post Correspondence Problem
  • Measure: compare growth rates, count a Turing machine's steps, and see the 3SAT → CLIQUE reduction
  • Practice: 50 exercises across Chapters 1–3, checked with counterexamples
  • Export diagrams as PNG, SVG, LaTeX (TikZ) or JFLAP, and use exam mode for proctored Canvas exams
Which textbook does it follow?
Michael Sipser, Introduction to the Theory of Computation, 3rd edition (Cengage Learning, 2013). The chapters, notation and numbering on every page follow the book. DeltaDraw is an independent study tool and is not affiliated with the author or the publisher.
Is DeltaDraw free?
Yes. It is free and open source, and your drawings stay in your own browser.
Can I use the diagrams in a LaTeX report?
Yes. Export LaTeX to get TikZ code, or export an SVG or high-resolution PNG.