- Home
- Theory of Computation
Theory of Computation
What computers can and cannot compute: automata, grammars and Turing machines.
DFA & NFA (Finite Automata)
The simplest model of a computer — states, transitions and accepting states. Run strings through DFAs and NFAs and watch every state light up in 3D.
DFA Minimization
Many DFAs accept the same language. Remove unreachable states, then split groups of states until only truly equivalent states share a group.
Regular Expressions
Patterns for text — and the automata hidden inside them. Type a regex, watch Thompson's construction turn it into an NFA, and run it on your text in 3D.
Pushdown Automata (PDA)
A finite automaton plus a stack. Watch it count a's and b's and check balanced brackets — something no DFA can do — with a 3D stack that grows and shrinks.
Turing Machine
The simplest machine that can compute anything a computer can. Watch the head read, write and move along the tape to add numbers and check palindromes.
CYK Algorithm (Parsing Context-Free Grammars)
Decide if a grammar can generate a string by filling a triangular table with dynamic programming, one substring length at a time.
NFA to DFA Conversion (Subset Construction)
Turn a nondeterministic automaton into a deterministic one by treating each set of NFA states as a single DFA state.
About Theory of Computation
Theory of computation asks what machines can compute. Run strings through DFAs and NFAs, turn a regular expression into an NFA with Thompson's construction, watch a pushdown automaton use its stack, and step through a Turing machine's tape rule by rule — the models behind compilers, regex engines and the limits of computing. The CYK parser and the NFA-to-DFA subset construction connect grammars and automata.