Kleene's Theorem: Regexes Are Finite Automata

Symptom

Your service goes down. CPU pinned at 100% on one core, no memory growth, no error logs, requests timing out.

The cause is a validation regex — something reasonable-looking like ^(a+)+$, or in real life a URL or email validator with nested quantifiers — matched against a 30-character string that happens not to match. The engine is exploring an exponential number of ways to split the input among the nested groups, and it will get there eventually, some time after the heat death of everything.

This has a name, ReDoS, and it has taken down Stack Overflow (2016, a trailing-whitespace regex) and Cloudflare (2019, a WAF rule that took out a large fraction of the internet for half an hour).

Here is the part that should bother you: matching a regular expression against a string can always be done in linear time. There is no exponential blowup anywhere in the theory. The engine that hung your service is not implementing the theory. It is implementing something more powerful and much worse, and the theorem explains exactly what got lost.

Statement

A language is describable by a regular expression if and only if it is recognized by a finite automaton.

Two formalisms that look nothing alike. One is an algebraic notation with concatenation, alternation, and Kleene star. The other is a machine with states and transitions. They have exactly the same expressive power, and the equivalence is constructive in both directions, which is what makes it an engineering result rather than a classification.

Combined with T038: this is the bottom rung of the Chomsky hierarchy, described three ways. The equivalence is why “regular” is a robust notion rather than an artifact of one notation.

Argument

Direction one: regex to NFA (Thompson’s construction). Structural induction on the expression, where each case builds a fragment with one start state and one accept state.

• $\emptyset$: two states, no transition. $\varepsilon$: an $\varepsilon$-edge. A single character $a$: an $a$-edge.
• Concatenation $RS$: $\varepsilon$-edge from $R$’s accept to $S$’s start.
• Alternation $R \mid S$: new start with $\varepsilon$-edges into both, and both accepts $\varepsilon$-edge to a new accept.
• Kleene star $R^*$: new start/accept pair, $\varepsilon$-edges to enter, to skip, and to loop back.

Each operator adds at most two states, so an expression of size $m$ yields an NFA with $O(m)$ states. Linear, which is the fact the whole practical story rests on.

Direction two: NFA to DFA (subset construction). A DFA state is a set of NFA states — everywhere the NFA could currently be. Start from the $\varepsilon$-closure of the NFA’s start; on input $a$, move to the closure of everything reachable by $a$; accept if the set contains an NFA accept state. Finitely many subsets, so it terminates.

The cost is that $n$ NFA states give up to $2^n$ DFA states, and this is sometimes unavoidable: the language “the $k$-th symbol from the end is $a$” needs $k+1$ NFA states and provably $2^k$ DFA states, because the DFA must remember the last $k$ symbols. At $k = 20$ that is 21 states versus 1,048,576.

Direction three: DFA to regex. State elimination. Label edges with regexes, then remove states one at a time, replacing paths $p \to q \to r$ with a direct edge labelled $R_{pq} R_{qq}^* R_{qr}$ — the star capturing loops at the eliminated state. When only start and accept remain, the edge label is the answer.

How this makes matching linear. Simulate the NFA directly, keeping the set of current states. Each input character updates the set once. With $m$ NFA states and length-$n$ input, that is $O(mn)$, and with on-the-fly DFA construction plus caching it is effectively $O(n)$.

No backtracking. No exponential blowup. The reason is structural: the NFA explores all alternatives simultaneously as a set, whereas backtracking explores them sequentially and re-explores overlapping work. Same automaton, different traversal, and the entire difference between microseconds and forever.

So why does Perl backtrack? Because it is not matching regular expressions. Backreferences — (a+)\1, meaning “some text, then the same text again” — are not regular. The language ${ww}$ is not even context-free. Once your syntax includes backreferences you have left the theorem’s scope entirely, and the only known general algorithm is backtracking. Lookahead, recursive patterns, and atomic groups similarly exceed it. The performance disaster is the price of features that are not regular, paid on every pattern including the ones that do not use them.

Watching the blowup happen. Take the pattern that hung the service, ^(a+)+$, against the input aaaaaaaaaaaaaaaaaaaaaaaaaaaaaa! — thirty as and a character guaranteeing failure. A backtracking engine must try every way to partition those thirty as among repetitions of the inner group, and the number of compositions of 30 is $2^{29} \approx 5.4 \times 10^8$. At a hundred million steps per second that is about five seconds. Add ten more as and it is an hour and a half; at sixty as it is roughly 180 years, and at seventy it is about 190,000.

Now run the same pattern through Thompson’s construction. The expression has about six operators, so the NFA has roughly a dozen states. Simulating it keeps a set of at most twelve states and updates that set once per input character. Thirty characters, twelve states, and the work is bounded by $12 \times 31 = 372$ state updates. Microseconds, and the growth is linear no matter how many as you append.

The two engines are exploring the same graph. The backtracker walks paths one at a time and revisits shared prefixes exponentially often; the automaton walks the frontier of all paths at once and visits each state at most once per position. The exponential is entirely an artifact of the traversal order, which is why the fix requires no cleverness about the pattern and no timeout tuning — only a different engine.

This is also why input length limits are a poor mitigation. The blowup is exponential in length, so the difference between a safe limit and a fatal one is a handful of characters, and it depends on the pattern in a way no reviewer can eyeball.

Forbids

Regexes matching balanced parentheses, or any properly nested structure. Requires unbounded counting, and a finite automaton has finitely many states. This is the theorem behind the famous refusal to parse HTML with a regex, and the reason is not stylistic.

Regexes recognizing $a^n b^n$, palindromes, or ${ww}$. All above the regular rung of T038.

A finite automaton counting without bound. “Even number of $a$s” is fine — two states. “Equal numbers of $a$s and $b$s” is not, at any state count.

Exponential worst-case matching for genuinely regular patterns. If your engine blows up on a regular pattern, the engine is at fault, not the pattern. This is a real and actionable distinction during an incident.

Does not forbid

It does not mean regex engines are broken, and treating backtracking as a bug misses what those engines are for. PCRE, Perl, Python’s re, Java’s java.util.regex, and JavaScript’s built-in engine all implement a strict superset of regular expressions. Backreferences and lookahead are genuinely useful and genuinely non-regular. The engineering error is not that these exist; it is deploying them on untrusted input without a timeout.

It does not mean you have to accept ReDoS, and the fix is to use an engine that made the other choice. RE2 (Google) and Rust’s regex crate guarantee linear time by refusing to implement backreferences — the theorem, as a product decision. Go’s regexp is RE2-based. Cloudflare rewrote its WAF onto RE2 after the 2019 outage, and Rust’s crate is what powers ripgrep, which is why it outruns grep on large trees. If your regex runs on user input, this is the choice to make, and the theorem is what guarantees it is safe to make it.

It does not forbid practical extensions that stay regular. Bounded repetition a{2,5}, character classes, anchors, and case-insensitivity are all syntactic sugar over the regular core, expanding to plain automata. Capture groups can be handled in linear time too — RE2 does it with tagged transitions. Only backreferences and unbounded lookahead genuinely escape.

It does not mean DFA conversion is always worth it. The $2^n$ blowup is real, which is why RE2 builds DFA states lazily and caches them, falling back to NFA simulation when the cache fills. You get DFA speed on common inputs and a bounded memory footprint on adversarial ones, which is the practical resolution of the exponential.

It does not say all regex features are equally costly. A pattern using only regular features runs in linear time even in a backtracking engine if the engine recognizes that. Some do optimize this. Relying on it is unwise, since whether your specific pattern hits the optimized path is an implementation detail that can change on upgrade.

Boundary

The theorem’s exact scope, in terms that matter when choosing a tool:

• Regular operations only. Union, concatenation, star, and anything definable from them, including intersection and complement, which are closed for regular languages but can blow up the automaton.
• Backreferences leave the class. Matching becomes NP-hard in general.
• Lookahead and lookbehind of bounded width stay regular in principle but are usually implemented by backtracking.
• Recursive patterns (PCRE’s (?R)) reach into context-free territory, at which point you should be using a parser.

The practical rule that falls out: if the input is untrusted, use an engine with a linear-time guarantee, and if you need backreferences on untrusted input, you need a different design rather than a longer timeout. And when you find yourself reaching for recursion or nested-structure matching, T038 already told you the answer, which is that you have a parsing problem and regular expressions are the wrong rung of the ladder.

Read next