Regex to Automaton, Explained
After reading this you will be able to read a regular expression as a small machine, trace that machine over an input string character by character, and predict which strings it accepts and which it rejects.
What a regex really is
A regular expression looks like text, but it describes a machine. The machine has a set of states and labeled arrows between them. You start in one state, read the input one character at a time, and follow an arrow that matches each character. If you finish reading in an accepting state, the string is accepted. If not, it is rejected.
Take the regex a(a|b)*b over the alphabet {a, b}. In words: start with an a, then any mix of a and b (including none), then a final b. The string ab matches. So does aaabb and abb. The string ba does not, because it fails on the first character. The string aba does not, because it ends in a.
The tool draws this machine and lights up the active states as you feed it characters. Watching the lights is the fastest way to understand why aba fails: the machine reaches the state expecting a final b, reads a, and has nowhere legal to go.
When this view helps and when it does not
Use the automaton view when you want to understand why a pattern accepts or rejects a specific string, or when you want to see nondeterminism as a concrete thing rather than a definition. It is also the right lens for the classic theory result: regexes, NFAs and DFAs describe exactly the same set of languages, called the regular languages.
Do not use this view to reason about the regex features in a programming language such as backreferences, lookahead, or capture groups. Those extensions are strictly more powerful than regular languages and cannot be drawn as a finite automaton at all. The pattern (a+)\1, meaning "some a's repeated," is not regular. Everything on this page assumes the classic operators only: concatenation, union with |, and the Kleene star *.
A finite automaton has a fixed, finite number of states. That is why it cannot count without bound. The language "equal numbers of a's then b's" (a^n b^n) needs unbounded memory and is not regular, no matter how clever the regex looks. If a pattern seems to require counting, it is outside what these machines can do.
From regex to NFA: Thompson's construction
Thompson's construction builds an NFA (nondeterministic finite automaton) from a regex piece by piece. Each operator has a fixed gadget with a start state and one accepting state, glued together with \varepsilon-arrows. An \varepsilon-arrow moves the machine for free, consuming no input.
A single symbol a becomes two states joined by one arrow labeled a. Here q_0 is the start and q_1 accepts.
Union adds a new start q_s that branches by \varepsilon into both sub-machines R and S, and a new accept q_f that both feed into. The branch is where nondeterminism enters: the machine tries both paths at once.
The star wraps R with a loop-back \varepsilon-arrow so it can repeat, plus a skip arrow so it can be used zero times. The count of states stays small: Thompson's construction produces at most 2 states per symbol of the regex. The pattern a(a|b)*b has 5 symbols, so the NFA has at most 10 states.
From NFA to DFA: the subset construction
An NFA can sit in several states at once. To turn it into a deterministic machine (a DFA), track the set of NFA states you could be in. Each such set becomes one DFA state. This is the subset construction.
Start from the set reachable by \varepsilon-arrows from the NFA start. For each input symbol, compute the new set: take every arrow labeled that symbol out of the current set, then close under \varepsilon-arrows again. A DFA state is accepting if its set contains any NFA accepting state.
The number of DFA states can grow, in the worst case, to 2^{n} for an n-state NFA, since every subset is possible. In practice most patterns produce far fewer. For a(a|b)*b the DFA needs only 3 useful states plus a dead state, as the worked example shows.
Worked example: running a(a|b)*b on the string aabb
Use the default pattern a(a|b)*b and the input aabb. Here is the DFA built by the subset construction. Call the states S (start), A (seen the opening a, now in the loop), F (just read a b that could be the final one), and D (dead, no accept possible).
| State | on a | on b | accepting? |
|---|---|---|---|
| S | A | D | no |
| A | A | F | no |
| F | A | F | yes |
| D | D | D | no |
- Start in
S. - Read
a:Sgoes toA. - Read
a:Astays inA(the loop). - Read
b:Agoes toF. - Read
b:Fstays inF. - Input exhausted in
F, which accepts. The stringaabbis accepted.
Now try aba on the same table: S to A on a, A to F on b, then F to A on a. You end in A, which does not accept, so aba is rejected. The final a is the problem, exactly as the plain-English reading predicted.
Reading the colors and the active set
Three signals matter as you step through a string. First, the number of lit states. If several light up at once, the NFA is exploring multiple paths in parallel: that is nondeterminism made visible. Second, the moment all lights go dark except a dead state. That means no path can recover, and the string will be rejected no matter what follows. Third, the final color: green if the active set contains an accepting state when input runs out, red otherwise.
For (a|b)* nearly every state stays lit throughout, because that pattern accepts everything over the alphabet, including the empty string. For a(a|b)*b the active set is narrow: you stay on a single spine. Comparing the two side by side is the clearest way to feel what the N in NFA buys you.
Common mistakes
The most frequent error is reading | too greedily. In a|b*, the star binds tighter than the union, so this means "a single a, or any number of b's," not "(a or b) repeated." Write (a|b)* if you mean the latter. The parentheses change the language completely: a|b* accepts a and bbb but rejects ab, while (a|b)* accepts all three.
The second mistake is forgetting the empty string. The star allows zero copies, so (a|b)* accepts the empty input, and its start state is already accepting. If your machine rejects an empty string that you expected to accept, check whether a required symbol sits outside every star.
The third mistake is expecting anchoring. These machines match the entire input, start to finish. There is no partial match and no "contains" semantics unless you write it, for example by wrapping the target in (a|b)* on both sides.
Related tools
If finite machines interest you, step up in power with the Turing Machine Simulator, which adds an unbounded tape and can do the counting an automaton cannot. To see how states and arrows behave as a general structure, build one by hand in the Graph Algorithm Playground. For a different flavor of state exploration, the Pathfinding Visualizer shows search frontiers spreading much like an NFA's active set. And to feel how the worst-case 2^{n} blow-up of the subset construction compares to gentler growth, race it in the Big-O Complexity Race.
Frequently asked questions
Why does one regex light up many states at once?
Because the NFA is nondeterministic. Union and star create branches, so the machine follows every possible path in parallel. The lit states are exactly the set of NFA states you could legally be in after the characters read so far.
Are NFA and DFA equally powerful?
Yes, for the classic operators. The subset construction converts any NFA to a DFA that accepts the same language. The DFA may have more states, up to 2^{n} in the worst case, but it recognizes exactly the same strings.
Why is a^n b^n not expressible here?
Matching equal counts of a's and b's requires remembering how many a's you saw, an unbounded number. A finite automaton has finitely many states and cannot store an unbounded count, so no regex over these operators describes that language.
Does the empty string count as input?
Yes. It is a valid string of length 0. A pattern like (a|b)* accepts it, while a(a|b)*b rejects it because at least two characters are required.
What is an epsilon-arrow?
An arrow the machine can follow without reading any input. Thompson's construction uses them to glue gadgets together. The active set always includes everything reachable by epsilon-arrows from the states you can reach.
Related tools
Dynamic Programming Visualizer
Watch edit distance and knapsack fill their tables cell by cell — dynamic programming with the lid off.
Graph Algorithm Playground
Build a graph by clicking, then watch BFS, DFS, Dijkstra and Prim explore it live.
Huffman Coding Visualizer
Type any text and watch the optimal prefix code assemble itself as a tree, rare letters sinking deepest.
Pathfinding Visualizer
Draw walls and watch A*, Dijkstra, greedy and breadth-first search hunt for the shortest path.
Sorting Algorithm Visualizer
Watch bubble, insertion, merge, quick and heap sort race through the same shuffled bars.
Turing Machine Simulator
Watch a Turing machine read, write and shuffle along its tape — computation stripped to its atoms.