Back to home

Regex → NFA → DFA

A regular expression and a finite-state machine are the same thing written two ways. This page performs the translation in front of you, in two stages.

Stage 1 — Regex → NFA (Thompson's construction)

Build a non-deterministic machine directly from the shape of the expression.

What this stage is doing

Thompson's construction turns any regular expression into a machine, mechanically. It never has to be clever, because it never looks at the expression as a whole.

For a*b it first builds a two-state machine for the single character 'a'. Then the star wraps that in a loop, adding a bypass edge so zero repetitions is allowed. Then it builds another two-state machine for 'b'. Finally concatenation joins the two pieces end to end with an empty (ε) edge. Four steps, four small machines, one result.

The ε edges are transitions that consume no input — they exist purely to glue fragments together, which is what makes the construction so mechanical.

  1. 1.Type a regular expression, e.g. a*b (zero or more a's, then a b)
  2. 2.Press Run
  3. 3.Watch the NFA assemble one construct at a time, then the DFA appear below it

letters, digits and ( ) | * + ? — up to 64 characters

The NFA appears here once you press Run

What the code is doing under the hood

Thompson's construction is NOT one large function with a switch over regex syntax. It is a set of tiny builders — one per construct: match a single character, handle star, handle concatenation, handle alternation — each about ten lines long.

Every builder returns a fragment with exactly ONE entry state and ONE exit state. Because every fragment has that same shape, fragments plug into each other, and the whole machine is assembled by walking the expression's syntax tree bottom-up. The recursion does the work; no builder knows about any other.

Code card

Run this demo to see the code that executed.

Stage 2 — NFA → DFA (subset construction)

Collapse the non-deterministic machine into one with a single active state.

What this stage is doing

The NFA above can be in several states at once. A DFA cannot — so subset construction makes each SET of NFA states into a single DFA state.

It starts from the set of states reachable from the NFA's start without consuming anything, and calls that D0. Then for each input symbol it works out which set of NFA states you could reach, and if that set has not been seen before it becomes a new DFA state. Repeat until no new sets turn up.

The table below shows the correspondence: which NFA states each DFA state stands for. A DFA state is accepting exactly when its set contains the NFA's accepting state.

  1. 1.This stage runs automatically as part of stage 1 — no separate button

Driven by the expression above. Build one to populate this stage.

The DFA appears here after the NFA is built

What the code is doing under the hood

Subset construction is essentially ONE LOOP over a worklist. Take a state-set off the queue, compute where each symbol leads, and push any set you have not seen before. When the queue empties, the DFA is complete.

This is also where the theory bites: n NFA states could in principle produce 2^n subsets, so the DFA can be exponentially larger than the NFA. That is exactly why this page caps the expression length — the cap is not arbitrary tidiness, it bounds a real exponential.

Code card

Run this demo to see the code that executed.

Stage 3 — Test the DFA

Walk a string through the deterministic machine, one lookup per character.

What this stage is doing

This runs the DFA produced above. There is nothing non-deterministic left: one state, one lookup per character, accept or reject at the end.

If a character has no transition out of the current state, the machine is stuck and the string is rejected immediately — there is nowhere left to go.

  1. 1.Build a machine in stage 1 first
  2. 2.Type a test string, e.g. a a b
  3. 3.Press Test and watch the single active state move

Build a machine in stage 1 first.

The walk appears here once you press Test

What the code is doing under the hood

The loop here is the same core as the hand-written DFA on the Automaton page: look up (state, character), move, repeat, then one final check for an accepting state. The machine was generated rather than written by hand, but the recogniser is identical.

Code card

Run this demo to see the code that executed.