How Regular Expressions Work Under the Hood

A regular expression (regex) is a pattern language for matching text, and under the hood it’s executed by one of two fundamentally different kinds of engines: finite automata or backtracking. Which one a language uses explains a lot about regex behavior that otherwise looks mysterious — including why some patterns match instantly and others can hang a process indefinitely on ordinary-looking input.

Two engine families: DFA/NFA vs backtracking

A regex pattern first gets compiled into a state machine — a nondeterministic finite automaton, or NFA — the same underlying structure covered in what a finite state machine is. From there, engines split into two families based on how they walk that state machine against the input string.

Automata-based engines (used by tools like grep -E, RE2, and Rust’s regex crate) convert the NFA into a deterministic finite automaton, or simulate the NFA directly by tracking every possible state simultaneously. Either way, they process each input character exactly once, which guarantees matching time that scales linearly with input length — no matter how the pattern is written.

Backtracking engines (used by PCRE, and by most mainstream languages’ built-in regex — Python’s re, JavaScript’s native regex, Java’s Pattern) try one path through the pattern, and if it fails, they backtrack and try an alternative. This approach supports features automata-based engines can’t express, like backreferences and lookahead, but it gives up the linear-time guarantee.

Finite automata: fast and predictable

An automata-based engine’s worst case is bounded by the input length, because it never re-examines a character it’s already consumed for a given path. The tradeoff is expressiveness: constructs like backreferences (\1, matching whatever an earlier group captured) require remembering more than a state machine can represent, so tools like RE2 deliberately don’t support them, trading some regex features for a hard guarantee against pathological runtime.

This is why security-sensitive contexts — matching untrusted input against a pattern, for instance — often specifically choose an automata-based engine, since an attacker who controls the input can’t make a linear-time match run any slower than input length allows.

Backtracking: powerful but risky

A backtracking engine walks the pattern left to right, and when it hits a choice point — a quantifier like * or +, or an alternation like (a|b) — it commits to one option and keeps going. If a later part of the pattern fails to match, it backtracks to the last choice point and tries the next option. This is what makes lookahead, lookbehind, and backreferences possible: the engine can hold onto arbitrary state about what it’s already matched.

The cost shows up when a pattern has ambiguous quantifiers that let a substring be split multiple ways. Consider (a+)+b against a string of forty a characters with no trailing b. There are exponentially many ways to partition those as across the inner and outer +, and the engine tries all of them before giving up — this is catastrophic backtracking, and its runtime grows exponentially with input length rather than linearly.

Common regex building blocks

Regardless of engine, most regex syntax maps onto a small set of concepts:

• Anchors (^, $) pin a match to the start or end of a line rather than allowing it anywhere in the string.
• Quantifiers (*, +, ?, {n,m}) control how many times the preceding token can repeat.
• Character classes ([a-z], \d, \w) match one character from a set.
• Groups ((...)) capture a submatch for later use, or (?:...) group without capturing.
• Alternation (a|b) matches either branch.
• Lookahead/lookbehind ((?=...), (?<=...)) assert what follows or precedes a position without consuming it.

Lookahead, lookbehind, and backreferences are the features that specifically require a backtracking engine — if a pattern doesn’t use them, it’s often (though not always) safe from catastrophic backtracking regardless of how it’s written.

Catastrophic backtracking and ReDoS

When a backtracking-vulnerable pattern is applied to attacker-controlled input, the result is a ReDoS (regular expression denial of service) — a small, well-crafted input string that takes seconds or minutes to reject, tying up a thread or process the entire time. This is a genuine denial-of-service vector in production systems, not just a theoretical concern, and it’s shown up in real incidents where a single HTTP request with a crafted string in a header or form field pegged a server’s CPU.

The pattern to watch for is nested or adjacent quantifiers where the same substring could satisfy either one — (a+)+, (a*)*, (a|a)*. Rewriting the inner group to be more specific, or replacing the quantifier with a possessive or atomic group where the language supports it, removes the ambiguity that causes the blowup.

Practical tips for writing safer regex

• Prefer specific character classes over broad ones ([0-9] instead of .) so the engine has less ambiguity to explore.
• Avoid nested quantifiers on patterns that can match the same substring multiple ways.
• Test regex against long, adversarial-looking input during development, not just the happy path — this is closer in spirit to how backtracking algorithms are stress-tested generally.
• For matching untrusted input at scale, consider an automata-based engine or a length cap on the input before it ever reaches the regex.
• Remember that regex complexity analysis isn’t intuitive from reading the pattern alone — the same reasoning that applies to Big O notation for algorithms applies here: a pattern that looks simple can still hide exponential worst-case behavior.

The takeaway

Regex engines fall into two families: automata-based engines guarantee linear-time matching but can’t support backreferences or lookaround, while backtracking engines support the full feature set at the cost of potentially exponential runtime on adversarial input. Most mainstream languages default to backtracking engines, which makes catastrophic backtracking a real risk in any code path that runs a regex against input you don’t control — the fix is usually rewriting ambiguous nested quantifiers, not avoiding regex altogether.