A regular expression looks like a cryptic string of symbols, but it’s really a program for a tiny machine. Compiling a(b|c)*d produces a nondeterministic finite automaton (NFA): a handful of states connected by edges that either consume a character or take a free epsilon jump (the “or” and the “repeat” become branch and loop edges). The word nondeterministic sounds spooky, but the way you actually run it is beautifully concrete: instead of guessing which branch to take and backtracking when you’re wrong, you keep track of the entire set of states the machine could be in at once. Each input character advances every active state in parallel; epsilon edges are followed for free to expand the set (the “epsilon closure”). If, after the last character, any accept state is in the set, the string matches. This set-of-states trick is why a properly built regex engine matches in linear time — it never re-examines a character — and never suffers the catastrophic backtracking that can hang a naive engine for seconds on an evil input. Feed characters into the machine and watch the active states move.
regex → NFA · track the SET of states · epsilon closure · one char at a time · linear time, no backtracking
NFA
A state machine where a state can have several edges on the same symbol, or free “epsilon” edges — so it can be in many states at once.
epsilon edge
A transition taken for free, without consuming a character — how “or” and “repeat” are wired.
epsilon closure
The full set of states reachable from the current set by following epsilon edges — computed after every step.
active set
The set of states the machine could currently be in. Matching advances this whole set in parallel.
nfa.js — advance the whole set of states
Ready
This machine matches a(b|c)*d. Feed it characters one at a time. The active set (highlighted states) advances in parallel; free epsilon jumps expand it. If an accept state is active when you stop, the string so far matches.
—
input so far
{0}
active states
—
accepts?
How it works
The engine that runs a regex safely is the Thompson NFA simulation, and its whole secret is refusing to guess. A regex has choice built in — b|c could go either way, * could loop again or stop — and a naive engine handles this by picking one path and backtracking when it fails, which on adversarial patterns explodes into exponential time (the infamous “catastrophic backtracking” that turns a regex into a denial-of-service bug). The NFA simulation sidesteps the whole problem by exploring all paths simultaneously: it maintains the set of states the machine could be in, and processes each input character exactly once by computing, for every active state, where that character leads, then taking the epsilon closure of the result to fold in all the free jumps (entering and re-entering the star, choosing either side of the alternation). Because the set of states can never be larger than the machine itself, each character costs at most O(states) work, so the total time is O(text × states) — linear in the input, with a hard ceiling that no crafted string can breach. This is exactly the guarantee that RE2 (Google’s regex engine) and Rust’s regex crate provide and that backtracking engines like PCRE cannot: the price is that pure NFA simulation gives up a few features (notably backreferences) that fundamentally require remembering matched text, but for the vast majority of patterns it delivers matching that is both correct and immune to blowup.
1
Start with the epsilon closure of the start
Before reading any input, the active set is the start state plus everything reachable from it by free epsilon edges. The machine is already “in several places at once.”
2
Each character advances the whole set
For a character, look at every active state, follow its edges labelled with that character, and collect all the destinations. States with no matching edge simply drop out of the set.
3
Take the epsilon closure again
From the new set, follow all epsilon edges for free to expand it — re-entering loops, choosing either side of an alternation. This is the epsilon closure, recomputed after every character.
✓
Accept if an accept state is active
If the active set is ever empty, the string can’t match. If, when the input ends, an accept state is in the set, it matches. Each character was processed once — linear time, no backtracking.
Regex
compiles to an NFA
Matching
track the set of states
Time
O(text × states), linear
Backtracking
none — no blowup
The code
# Thompson NFA simulation — no backtracking, linear timedefmatches(nfa, text):
active = eps_closure({nfa.start}) # set of states, not one statefor ch in text:
nxt = set()
for s in active: # advance EVERY active state
nxt |= nfa.move(s, ch) # edges labelled ch
active = eps_closure(nxt) # follow free epsilon jumpsif not active: return False # the set died — no matchreturn any(s in nfa.accepts for s in active)
Quick check
1. When simulating an NFA, what do you track as you read the input?
The core idea of NFA simulation is tracking the entire set of possible states simultaneously, rather than committing to one branch. Every input character advances all active states in parallel, so no guessing or backtracking is ever needed.
2. What is an epsilon closure?
Epsilon edges are taken for free without consuming a character — they wire up alternation and repetition. The epsilon closure expands the active set to include every state reachable through those free jumps, and it’s recomputed after each input character.
3. Why does the NFA simulation run in linear time with no catastrophic backtracking?
Because it explores all paths at once via the set of states, each input character costs at most O(states) work and is examined exactly once. Total time is O(text × states) — linear in the input — with a hard ceiling no crafted string can breach, unlike backtracking engines that can explode exponentially.
FAQ
How does a regular expression actually work under the hood?
A regex is compiled into a small state machine — usually an NFA — with edges that consume a character or take a free epsilon jump; alternation becomes branching and repetition becomes a loop. Matching runs the machine by tracking the set of states it could be in, advancing every active state per character and following epsilon edges to expand the set. If an accept state is active when the input ends, it matches. This set-tracking (Thompson) approach runs in linear time.
What is the difference between an NFA and a DFA regex engine?
Both come from the same regex. An NFA can be in many states at once and is simulated by tracking the active set; it’s compact and quick to build. A DFA precomputes one next state per (state, character), so runtime is a single table lookup per character — faster, but the table can be exponentially large to build. Real engines like RE2 do both: simulate the NFA while lazily building and caching DFA states on the fly, getting DFA speed without the full upfront cost.
What is catastrophic backtracking and how is it avoided?
Catastrophic backtracking is when a backtracking engine tries a path, fails, backs up, and retries — and for certain patterns the number of paths explodes exponentially, so a short input can hang the engine (a ReDoS denial-of-service risk). It’s avoided by NFA/DFA simulation that tracks the set of states instead of backtracking: all paths are explored at once, each character processed once, so matching is linear with a hard bound. RE2 and Rust’s regex guarantee this; the trade-off is dropping backreferences.
Why can’t linear-time regex engines support backreferences?
A backreference requires remembering the actual text a previous group matched and comparing it later. The NFA/DFA model only tracks which states the machine is in — a fixed, finite amount of information — not arbitrary captured text, which is what lets it guarantee linear time. Backreferences make matching fundamentally harder (NP-hard in general), so engines supporting them must backtrack and risk exponential blowup. That’s why engines split into fast/safe backreference-free (RE2, Rust regex) and feature-rich backtracking (PCRE) families.