Regular Expressions to NFA
Thompson's construction: every operator has one wiring pattern, and the whole machine is those patterns nested.
Skip to the animationThompson's construction converts any regular expression into an NFA by giving each operator a fixed wiring pattern and nesting those patterns the way the expression nests.
One invariant makes it work
Every fragment the construction builds has exactly one start state and exactly one accepting state. That is what lets fragments be plugged into each other without any case analysis — an operator never has to ask what shape its operands turned out to be.
| Expression | Construction | Adds |
|---|---|---|
| a single symbol | two states, one arrow labelled with it | 2 states |
| ε | two states, one ε-arrow | 2 states |
| R | S | new start with ε into both; new accept with ε out of both | 2 states, 4 ε |
| R S | join R's accept to S's start | 0 states |
| R* | new start and accept, ε skip forward, ε loop back | 2 states, 4 ε |
Because each operator adds at most two states, an expression of length n gives an NFA of at most 2n states — a bound you know before you begin.
The vocabulary
- Alphabet (Σ)
- The finite set of symbols the machine may read. For everything on this page,
Σ = {a, b}. - String and language
- A string is a finite sequence of symbols from Σ. A language is a set of strings — usually infinite. A machine does not compute a value; it answers one yes/no question about membership in a language.
- State
- The machine's entire memory. Not part of it — all of it. If two different inputs leave the machine in the same state, it can never again tell them apart.
- Transition function (δ)
- Where to go given the current state and the next symbol. For a DFA it is a function: exactly one answer, always. For an NFA it returns a set, possibly empty.
- Accepting state
- Drawn as a double circle. A string is accepted if the machine is in one of these when the input runs out — not if it merely passed through one on the way.
- Trap or dead state
- A non-accepting state with every symbol looping back to itself. Once you fall in you can never get out, so the answer is already no. Diagrams usually omit it and leave the arrow missing instead.
The two ε-arrows that define star
The Kleene star is the only operator worth staring at. It needs a loop back, so the fragment can be repeated, and a skip forward, so it can be taken zero times.
Drop the skip and you have built R+ instead — one or more, not zero or more. That single missing arrow is the most common error in the construction, and it is invisible until you test the empty string.
Why go through an NFA at all
Nothing stops you converting a regular expression straight to a DFA, and for anything non-trivial nobody does. The NFA step is mechanical, linear-time, and produces a machine whose size you can predict; the DFA step is then handled by subset construction, which is also mechanical.
So the full pipeline — regex → NFA → DFA → minimal DFA — is four mechanical steps, none of which requires insight. That is exactly how lex, flex and every regular-expression engine turn a pattern into a matcher.
Advantages and disadvantages
Advantages
- Completely mechanical and linear in the length of the expression.
- The state count is bounded by twice the expression length, always.
- Every fragment has one start and one accept, so the operators compose without special cases.
Disadvantages
- Produces many redundant states and ε-arrows — it never optimises.
- The resulting NFA is slow to run directly; it exists to be converted.
- Subset construction on the result can, in the worst case, blow up exponentially.
Watch it work
Check yourself
question 1 / 4
One question at a time. Pick an answer to see why it is right or wrong, then move on — there is no score to keep and nothing is saved.