ToolSphere
Back to all articles
student

Thompson's Construction: Regex to NFA to DFA

2026-10-148 min read

Try it: free Regex to NFA Converter

Turn a regular expression into an NFA diagram

Open →

Every regular expression describes the same set of strings as some finite automaton, and Thompson's construction is the mechanical way to build one. It is also the first step of a pipeline every compiler course and theory-of-computation exam uses: regular expression → NFA (Thompson) → DFA (subset construction) → minimal DFA. This guide works through all three on the classic example (a|b)*abb, the language of strings over {a, b} that end in abb.

The rules: one small NFA per operator

Thompson's construction builds the NFA bottom-up from the expression's structure. Every piece it builds has exactly one start state with no arrows in and one accepting state with no arrows out. That invariant is what lets the pieces snap together.

  • A symbol a: two states, start and accept, with one transition on a.
  • ε (the empty string): two states joined by an ε-move.
  • Union r | s: a new start state with ε-moves into the starts of r and s, and ε-moves from both their accepting states into a new accepting state. Two states added.
  • Concatenation r s: the accepting state of r becomes the start state of s. No states added (some textbooks join them with an ε-move instead, which adds a transition but changes nothing else).
  • Kleene star r*: a new start and accepting state. ε-moves go from the new start into r and straight to the new accept (zero repetitions), and from r's accepting state back to r's start (more repetitions) and on to the new accept.
  • r+ and r? are shorthand. r+ is the star without the skip move, so r must happen at least once. r? is the star without the loop back, so r happens at most once.

Precedence decides how to read an expression: star binds tightest, then concatenation, then union, so ab*|c means (a(b*))|c.

Because each symbol adds two states and each union or star adds two more, the NFA never has more than twice as many states as the expression has symbols and operators. That is what keeps Thompson's construction practical even for long patterns.

Step 1: Build the NFA for (a|b)*abb

Work from the inside out:

  1. a and b: two small NFAs, two states each (4 states).
  2. a|b: a new start and accepting state around them (6 states).
  3. (a|b)*: the star adds another start and accepting state (8 states).
  4. Concatenate a, b and b: each symbol adds one new state, because its start merges into the previous accept (11 states).

The result has 11 states and 13 transitions, the same 11 states as the figure in the "Dragon Book" (Aho, Lam, Sethi and Ullman). The numbering below is breadth-first from the start state, so it differs from the book's, but the machine is the same.

The Thompson NFA for (a|b)*abb: 11 states q0 to q10, with ε-moves forming the star around the a and b branches, followed by a chain on a, b, b into the accepting state q10

The Thompson NFA for (a|b)*abb, as the regex to NFA converter draws it. q0 is the start, q10 the accepting state, and the moves labelled ε read no input.

Notice how much of it is ε "glue". That is the price of the construction being mechanical: every operator brings its own ε-moves, so the NFA is easy to build and easy to simulate, but not small.

Step 2: Subset construction, NFA to DFA

To turn the NFA into a DFA, let each DFA state stand for the set of NFA states the NFA could be in at once.

  • Start with the ε-closure of the NFA's start state: everything reachable from q0 by ε-moves alone. Here that is {q0, q1, q2, q3, q4}, the DFA's start state A0.
  • For each DFA state and each symbol, take every NFA move on that symbol from the states in the set, then take the ε-closure of the result. If that set is new, it becomes a new DFA state.
  • Repeat until no new sets appear. A DFA state is accepting if its set contains the NFA's accepting state.

The subset construction table for (a|b)*abb: five DFA states A0 to A4 with their NFA subsets and transitions on a and b, and the equivalent DFA drawn below with A4 as the accepting state

The subset construction for this NFA: five DFA states, A0 to A4. Only A4 contains q10, so only A4 accepts.

Five DFA states come out, matching the book's A to E. Read the table as a DFA: from A0, a goes to A1 and b to A2. From A1, b goes to A3. From A3, b reaches A4, the accepting state, which is the "abb" at the end of the string. Any a from anywhere goes back to A1, because an a might be the start of a new abb.

Step 3: Minimise the DFA

The subset construction often produces more states than needed. Two states are equivalent if no input string can tell them apart. Here A0 and A2 behave identically: on a both go to A1, and on b both go to A2. Neither accepts. Merging them gives the 4-state minimal DFA, which is the smallest DFA for "strings ending in abb".

The minimal DFA for (a|b)*abb: four states, where {A0,A2} is the start state, {A1} follows an a, {A3} follows ab, and {A4} is the accepting state reached after abb

The minimal DFA. Each state remembers how much of "abb" has just been read: nothing useful, a, ab, or abb.

That last reading is the intuition worth keeping. A minimal DFA for "ends in abb" needs exactly four states, because it only ever has to remember which of four suffixes the input currently ends with.

Common mistakes in exam answers

  • Forgetting the ε-closure. The DFA's start state is the ε-closure of the NFA's start, not just {q0}. Close again after every move, too.
  • Skipping the star's bypass move. Without the ε-move from the new start straight to the new accept, r* cannot match the empty string.
  • Reading precedence wrongly. ab* is a(b*), not (ab)*. Bracket the expression before you build anything.
  • Minimizing without removing unreachable states first. Subset construction never makes unreachable states, but a hand-drawn DFA can.
  • Stopping the minimization early. Keep splitting groups until a round changes nothing.

Try it yourself

Type any expression into the regex to NFA converter and press Convert this NFA to a DFA: the NFA to DFA converter opens with your NFA loaded and runs the subset construction. Then Minimize this DFA sends the result to the DFA minimizer, which shows both the partition method and the table-filling method. To check that strings really are accepted, trace them in the NFA & DFA simulator. The theory behind each step is in the subset construction explained and DFA minimization algorithms.

Looking for other tools?

Explore ToolSphere Homepage →