FINITE MACHINES. INFINITE POSSIBILITIES.

A regex, under the hood.

Build it. Reduce it. Follow every transition.

THOMPSON → SUBSET → MINIMAL
AN INTERACTIVE COMPILER EXPLORER

02 / TEST STRING

Try a string, then walk through the machine.

✓

AcceptedThe complete string matches.

Language & limits +

ab concatenation · a|b choice · (ab) grouping

a* zero or more · a+ one or more · a? optional

. any printable ASCII character · [a-z] class · [^a] complement

Escape punctuation with \. Empty patterns and empty alternatives match the empty string.

Alphabet: 95 characters, space through ~. No Unicode, flags, anchors, lookaround, backreferences, \d, or counted repetition.

256 pattern characters · 512 input characters · 512 NFA states · 128 DFA states · 2M compilation operations. Compilation runs in a cancellable worker.

The smallest equivalent machine.

States with identical future behavior become one.

5 STATES

activeacceptingε = no input consumed

NFA STATES—

DFA STATES—

MINIMAL STATES—

COMPILER WORK—

Inspect a state

Outgoing transitions for the selected state
ON INPUT	GO TO	CHARACTERS

Compiling…

01 / THOMPSON CONSTRUCTION

Compose little machines.

Each syntax node becomes a fragment. Epsilon transitions connect them into a nondeterministic automaton.

02 / SUBSET CONSTRUCTION

Make every move certain.

Each DFA state represents a set of NFA states. Every character has exactly one destination, including a dead state when needed.

03 / PARTITION REFINEMENT

Keep only real distinctions.

Repeatedly split states with different futures. Equivalent states merge without changing the language the machine accepts.