The idea: three machines for one pattern
A regular expression such as (a|b)*abb describes a set of strings: here, every string of a's and b's that ends in abb. A regex is easy to write but cannot run by itself. A DFA (deterministic finite automaton) runs fast: it reads one character, follows one edge, and never looks back. The classic way from one to the other goes through an NFA (nondeterministic finite automaton) in two steps, the ones the canvas animates: Thompson's construction turns the regex into an NFA, and the subset construction turns the NFA into a DFA.
Pick a regex, then press Build NFA, Build DFA and Run String in order. Each button builds the earlier stages at once if they are missing. Orange marks the set of NFA states being worked on; blue marks what was just added; red marks the edges being followed.
NFAs and ε edges
An NFA may have several edges with the same symbol out of one state, and ε edges that can be taken without reading anything. So after reading part of a string it can be in several states at once. It accepts if some path spells the whole string and ends in an accept state (drawn as a double circle). That freedom is what makes the NFA easy to build from a regex: pieces can be joined with ε edges without worrying how they interact.
Thompson's construction
Thompson's construction works from the inside of the regex out. Each symbol, each | and each * becomes a small fragment with exactly one start state and one accept state, and fragments are plugged into each other (Demo: Thompson NFA for (a|b)*abb).
| regex piece | fragment | new states |
|---|---|---|
symbol a | s –a→ f | 2 |
A|B | new start, ε into A and B; ε out of both into a new accept | 2 |
A* | new start and accept; ε to skip A, ε from A's accept back to A's start to repeat | 2 |
AB | A's accept state is B's start state | 0 |
Every rule adds at most two states, so a regex with n symbols and operators gives an NFA with at most 2n states, and every state has at most two edges out. The page uses the textbook form where concatenation merges two states instead of adding an ε edge; that is why (a|b)*abb gets exactly the states 0 to 10 of the Dragon Book.
ε-closure and move
Two operations on sets of NFA states do all the work. The ε-closure of a set is the set plus every state reachable from it by ε edges only. move(T, c) is the set of states reached from T by one edge labelled c. "Read c" for a set of states is then ε-closure(move(T, c)). For example, ε-closure({0}) = {0,1,2,4,7}: from 0 the ε edges reach 1 and 7, and from 1 they reach 2 and 4.
The subset construction
The DFA simulates the NFA ahead of time: each DFA state is a set of NFA states. The start state is A = ε-closure({start}). Then, for each DFA state T and each symbol c, compute U = ε-closure(move(T, c)). If U is a new set, it becomes a new DFA state; if it is already known, only the edge T –c→ U is added. The work stops when every row of the table is filled. A DFA state is accepting if its set contains the NFA's accept state (Demo: subset construction).
| DFA state | NFA states | on a | on b |
|---|---|---|---|
| A (start) | {0,1,2,4,7} | B | C |
| B | {1,2,3,4,6,7,8} | B | D |
| C | {1,2,4,5,6,7} | B | C |
| D | {1,2,4,5,6,7,9} | B | E |
| E (accepting) | {1,2,4,5,6,7,10} | B | C |
Different NFA paths that read the same characters end up in the same set, which is how nondeterminism disappears. In ab|ac both branches start with a, and after reading a the NFA is in both branches at once: one DFA state B = {2,5} stands for both (Demo: ab|ac). The DFA states carry meaning too: in the table above, D means "the input so far ends in ab" and E means "it ends in abb".
Running the DFA, and the dead state
To match a string, start in A and, for each character, look up one table entry: row = current state, column = the character. After the last character, the string matches if the current state is accepting. That is one lookup per character, with no guessing and no backtracking: aabb goes A → B → B → D → E and is accepted, abab goes A → B → D → B → D and is rejected (Demos: run aabb, run abab).
If move(T, c) is empty, the NFA has no state left: the DFA goes to the dead state ∅, which loops to itself on every symbol and never accepts. The table shows it as ∅, and pictures usually leave it out. In a(b|c)* the string babb dies on its first character (Demo: dead state). A character outside the alphabet also leads to ∅.
How big can the DFA get?
| NFA (Thompson) | DFA (subset construction) | |
|---|---|---|
| states for a regex of size n | at most 2n | up to 22n in theory; usually close to n |
| time to match a string of length m | O(n·m): track a set of states | O(m): one lookup per character |
| build cost | O(n) | can be exponential |
The blow-up is real: for (a|b)*a(a|b)(a|b)…(a|b) with k copies of (a|b) after the a, the DFA must remember the last k + 1 characters and needs 2k+1 states. Real engines such as RE2 and grep therefore build DFA states lazily, only for the sets the input actually reaches, and keep a cache. Backtracking engines (Perl, Java, Python re) skip automata altogether, which allows backreferences but can take exponential time on some patterns.
A DFA is the same kind of machine as the hardware Finite State Machines page: a state register and a next-state table. Knuth-Morris-Pratt builds a DFA-like failure table for one fixed pattern, and the states of a DFA are sets in the sense of Truth Tables and Sets. A lexer in a compiler is a DFA built this way from the token regexes; see Compiler vs Interpreter for where it sits.
A lexer is the classic use of a DFA; see the lexer phase in Inside a Tiny Compiler.
What the page leaves out
DFA minimization (Hopcroft's algorithm; the 5-state DFA for (a|b)*abb shrinks to 4 because A and C behave the same), the direct regex-to-DFA construction with followpos, Brzozowski derivatives, the reverse direction (DFA → regex), character classes, anchors, + and ? (they are shorthand: A+ = AA*, A? = A|ε), lazy DFA caches, backreferences, and proofs that regexes, NFAs and DFAs describe exactly the same languages (Kleene's theorem).