Regular expression to NFA, the textbook way
Every regular expression has an equivalent NFA, and Thompson's construction builds it mechanically from the expression's structure. The converter parses your expression (respecting precedence: * binds tightest, then concatenation, then |), then combines small NFAs bottom-up:
- A symbol
abecomes two states joined by an a-transition. - Union
r|sadds a new start state with ε-moves into both machines, and ε-moves from both accepting states into a new accepting state. - Concatenation
rsjoins the accepting state of r to the start of s. - Kleene star
r*adds a new start and accepting state, an ε-move that skips r entirely (zero repetitions) and an ε-move from r's end back to its start (more repetitions).
The result always has exactly one start state and one accepting state, and at most two transitions leaving any state, which is what makes Thompson NFAs easy to simulate.
Worked example: (a|b)*abb
The default expression is the classic from the "Dragon Book" (Aho, Lam, Sethi and Ullman): all strings over {a, b} ending in abb.
- a and b each become a two-state NFA (4 states).
a|bwraps them with a new start and accepting state: 6 states.(a|b)*wraps that again for the star: 8 states.- Concatenating a, b and b adds one new state each: 11 states in total, the same count as the Dragon Book's figure.
Trace babb through it and the ε-closures behave exactly like the hand-built four-state NFA for "ends in abb" in the NFA & DFA simulator: Thompson's version is bigger because every operator adds its own ε-glue, but it accepts the same language.
Syntax the converter accepts
| Write | Meaning |
|---|---|
a, 0, x |
one input symbol (any single character except the operators) |
rs |
r followed by s (no operator needed) |
r|s |
r or s |
r* |
zero or more r |
r+ |
one or more r |
r? |
r or nothing |
ε |
the empty string |
( … ) |
grouping |
+ and ? get their own Thompson pictures: r+ is the star construction without the ε-move that skips r, and r? is the star construction without the ε-move that loops back. Spaces are ignored, and a malformed expression (an unclosed bracket, an empty side of |) is pointed out with its position.
From regex to minimal DFA
This is the first step of the standard pipeline in compiler design and theory-of-computation courses: regex → NFA (here) → DFA by the subset construction → smallest DFA with the DFA minimizer. For (a|b)*abb that pipeline ends in the well-known four-state DFA. Lexer generators such as lex and flex follow the same route to turn token patterns into fast scanners; the regular expressions guide covers the practical side.