The theory of computation, made visible.
From finite automata to the P versus NP question — learn the mathematics of what computers can and cannot do, through interactive machines you can run yourself.
Automaton simulator
Build DFAs and NFAs, then step through any input and watch states light up.
Turing machine
Drive a head across an infinite tape and see real computation unfold.
Pumping & regex labs
Pump strings to prove non-regularity and test live regular expressions.
Three parts, one journey
Automata & Languages
Finite automata, regular expressions, and context-free grammars.
Finite Automata
The simplest model of computation: a machine with finitely many states that reads input one symbol at a time.
OpenNondeterminism
Allow a machine to be in several states at once. NFAs are no more powerful than DFAs — but far easier to design.
OpenRegular Expressions
A compact algebra for describing languages. Kleene’s theorem: regular expressions and finite automata describe exactly the same class.
OpenNonregular Languages
Some languages need unbounded memory. The pumping lemma is our tool for proving a language is not regular.
OpenContext-Free Languages
Grammars with recursive structure. They power programming-language parsers and describe nested, balanced patterns.
OpenComputability Theory
Turing machines, decidability, and the limits of computation.
Complexity Theory
Time, space, P vs NP, and the geography of hardness.
Ready to compute?
Start with the simplest machine there is and work your way up to the deepest open question in computer science.
Begin the course