the Thompson construction

Suppose you have a regular expression and you want a machine that recognizes the same language. Rather than guess the whole machine at once, Thompson's construction builds it the way you build with LEGO: a tiny standard block for each piece of the expression, then snap the blocks together following the expression's structure. The result is an epsilon-NFA that you assemble compositionally.

Each base case gets a minimal machine: for a symbol a, a start state with a single a-arrow to an accept state; for ε, a start state with an ε-arrow (epsilon-transition) to an accept state; for ∅, a start and accept state with no arrow between them. Then each operator has a gluing rule. For union R+S, add a new start state with ε-arrows into the starts of R's and S's machines, and ε-arrows from their accepts to a new common accept. For concatenation RS, link R's accept to S's start with an ε-arrow. For the star R*, add a new start/accept pair with ε-arrows that let you skip R entirely (zero copies) or loop back through it (more copies). Because each piece keeps exactly one start and one accept state, the blocks always fit.

Thompson's construction proves the forward direction of Kleene's theorem and is the engine inside many real regex tools: it is simple, always succeeds, and runs in time and space linear in the length of the expression. The trade-off is that it produces lots of ε-transitions and nondeterminism, so for fast matching you usually then remove ε's and run subset construction to get a DFA, or simulate the NFA directly. Named after Ken Thompson, who used it in an early text-search tool.