Regular Expressions to NFA: Thompson's Construction

Thompson's construction converts a regular expression into an equivalent NFA by recursion on the expression's structure. Every regex is either a base case or built from smaller regexes with concatenation, union (|), or Kleene star (*) — and each of those has a fixed NFA fragment, with exactly one start state and one accept state, that can be wired together.

The building blocks

• A single symbol a: two states with one transition, start --a--> accept.
• Concatenation RS: build the fragment for R, build the fragment for S, then glue R's accept state to S's start state with an ε-transition.
• Union R|S: a new start state ε-branches into both R's start and S's start; both R's accept and S's accept ε-transition into a new shared accept state.
• Kleene star R*: a new start/accept pair bypasses R entirely via ε (zero repetitions), ε-enters R's start, and R's accept ε-loops back to R's start (repeat) as well as ε-forward to the new accept (stop).

Because every fragment has exactly one entry and one exit point, these rules compose without ever having to look back at the rest of the machine — which is exactly what makes the construction mechanical enough to automate.

Worked example: ab*

The regex ab* means "an a, followed by zero or more bs". Applying the rules: build the single-symbol fragment for a, build the Kleene-star fragment for b, then concatenate them by ε-linking the first fragment's accept into the second fragment's start.

Trace a few strings through it: a takes the direct ε bypass around the star and accepts with zero bs; abb loops around the star fragment's ε-transition twice before taking the exit ε. Every accepted string reads exactly one a and then any number of bs — nothing else.

The app's built-in Regex → NFA tool (in the simulator's hamburger menu) runs this exact construction on any regex you type, so you can compare its output against a fragment you built by hand.

Your turn