Regular Expressions to NFA

A regular expression is a compact way to describe a language, but a computer cannot run a regular expression directly. Thompson's construction is the algorithm that bridges the gap: it turns any regular expression into an equivalent NFA, built up piece by piece from three primitive shapes.

The three building blocks

Every regular expression is built from three operations: concatenation (ab), alternation (a|b), and Kleene star (a*). Thompson's construction gives each operation a fixed NFA fragment with exactly one start state and one accept state, wired together with epsilon transitions. Because every fragment has the same shape, they compose cleanly: the accept state of one fragment becomes part of the wiring for the next.

A worked example

The automaton below was compiled from the expression (a|b)*abb, the classic "ends in abb" pattern. Run the input field to watch epsilon closures fire and the simulation step across states as each symbol is consumed.

Why NFAs, and not DFAs, come out of this step

Thompson's construction always produces an NFA, usually with epsilon transitions, even when the source expression is simple. That is fine: every NFA is equivalent to some DFA, and turning one into the other i separate step (subset construction) covered in the next lesson. Keeping the two steps apart is what makes the whole regex-to-DFA pipeline eas reason about: one algorithm handles structure, the other handles determinism.

Try it yourself

Build an NFA by hand for the expression a(b|c)*. Use epsilon transitions the same way the example above does: one to skip past alternation branches, one to loop back for the star.