Skip to content
Tutorials Center
My learning

Topics

Lesson 13 of 59 · Regular Expressions and Languages

From Regular Expressions to Finite Automata (Thompson's Construction)

Learn how to convert any regular expression into an ε-NFA with Thompson's construction, then to a DFA, with diagrams and a working Python regex compiler.

Regular expressions are convenient for people; finite automata are convenient for machines. Thompson's construction is the standard algorithm that turns any regular expression into an ε-NFA, building the machine piece by piece following the structure of the expression. It is the first half of the proof that regular expressions recognize regular languages, and it is the core of how regex engines like grep and RE2 work.

The building blocks

Every machine built by the construction has one start state and exactly one accepting state, with no arrows entering the start state and none leaving the accepting state. That clean interface lets pieces be glued together safely. Write a machine for R as a box with in and out terminals.

Base cases.

  • For a symbol a: two states connected by an arrow labeled a.
  • For ε: two states connected by an ε-arrow.
  • For ∅: two states with no arrow between them.
flowchart LR
    s1(("in")) -->|"a"| f1((("out")))
    s2(("in")) -->|"ε"| f2((("out")))

Left: a single symbol. Right: the empty string.

Union R + S. Make a new start state with ε-arrows into the starts of both machines, and ε-arrows from both of their accepting states into a new accepting state.

flowchart LR
    S(("in")) -.->|"ε"| R1["R"]
    S -.->|"ε"| S1["S"]
    R1 -.->|"ε"| F((("out")))
    S1 -.->|"ε"| F

Concatenation RS. Join the accepting state of R's machine to the start of S's machine with an ε-arrow (or merge the two states). The new start is R's start and the new accept state is S's accept.

Star R*. Add a new start and a new accepting state. Add ε-arrows: new start to R's start, R's accept to R's start (to repeat), R's accept to the new accepting state, and new start to the new accepting state (to allow zero repetitions).

flowchart LR
    S(("in")) -.->|"ε"| Rs["R"]
    Rs -.->|"ε (repeat)"| Rs
    Rs -.->|"ε"| F((("out")))
    S -.->|"ε (skip)"| F

Star: the repeat arrow loops back from R's end to R's start, and the skip arrow allows zero copies.

Because each construction step adds at most two states, the final machine has at most 2n states for an expression with n symbols and operators, and the number of transitions is also linear. The construction is fast and the machine is small, but it is nondeterministic and full of ε-moves.

A working compiler

The code below parses a regular expression string (union +, implicit concatenation, *, parentheses, and e for ε), builds the ε-NFA by Thompson's construction, and simulates it. The simulation tracks a set of states and uses ε-closures, just like in NFA and ε-moves.

Python Regex compiler: parser, Thompson construction and simulator

Press Run (or Ctrl + Enter) to see the result here.

Program input · what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

For (a+b)*abb the machine has 14 states and 16 edges, and every string agrees with Python's own engine. The second expression, b*(ab*ab*)*, accepts only strings with an even number of a's: ['', 'aa', 'abab', 'baab'] (a single a and bab are rejected).

From the ε-NFA to a DFA

A real scanner does not want to walk through ε-arrows at runtime. The standard pipeline is:

  1. Regex → ε-NFA with Thompson's construction (linear size).
  2. ε-NFA → DFA with the subset construction (up to exponential size, usually small in practice).
  3. DFA → minimal DFA with minimization.

Production engines often skip step 2 and simulate the NFA with a set of states, as in the code above, or build DFA states lazily on demand. That avoids exponential blowup while keeping time linear in the input, which is why RE2 and Rust's regex crate can promise worst-case linear matching.

Python Full pipeline: regex to DFA state count

Press Run (or Ctrl + Enter) to see the result here.

Program input · what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The determinized (ab)* machine has four DFA states: D2 (the start set, accepting), D1 (after reading a), D3 (after ab) and the dead state D0. D2 and D3 are different sets but behave identically (both accept and both move to D1 on a), so minimization merges them into a three-state machine. This is the whole path from a pattern to executable code.

Check your understanding

Quick check · 4 questions

of 4 answered You scored / 4 · perfect!

  1. 1. What property do all machines in Thompson's construction share?

    One start and one accept state with no arrows into the start or out of the accept state lets the pieces be combined safely.
  2. 2. In the construction for R*, which arrow allows the empty string?

    The 'skip' ε-arrow from the new start to the new accept state lets the machine accept without entering R at all.
  3. 3. How many states can Thompson's construction produce for a regular expression with n symbols and operators?

    Each symbol, union and star adds at most two states, so the size is linear in the expression.
  4. 4. Why do production regex engines avoid always converting to a full DFA?

    The subset construction can blow up exponentially in the worst case. Simulating the NFA with a state set keeps time linear in the input.

Summary

  • Thompson's construction turns a regular expression into an ε-NFA piece by piece: symbol, ε, union, concatenation, star.
  • Each fragment has one start and one accept state, giving a machine with at most 2n states.
  • Pipeline: regex, then ε-NFA, then DFA (subset construction), then minimal DFA.
  • Simulating the NFA directly keeps matching linear in the input without exponential blowup.

Next: From Finite Automata to Regular Expressions