How Regex Engines Work
Why this exists
On 20 July 2016, Stack Overflow went down for 34 minutes. No server crashed and no database failed. One user had posted text containing about 20,000 consecutive whitespace characters, and a regular expression meant to trim whitespace from the ends of a line spent so long on that post that the home page timed out. The load balancer's health check fetched the home page, saw it was slow, and took every web server out of rotation. Three years later, on 2 July 2019, a single new rule in Cloudflare's web application firewall pushed the CPUs that serve HTTP traffic to nearly 100% across its whole network for 27 minutes. The rule was a regular expression. Both postmortems are cited at the end of this page, and both incidents are walked through below.
Both regexes were correct. They matched what the authors wanted. The problem was how the engine ran them. A regular expression is a tiny program, and the engine is its interpreter. Some engines run every regex in time proportional to the length of the text. Others, including the ones built into Python, Java, JavaScript, PHP, Ruby and .NET by default, can take time exponential in the text length on an innocent-looking pattern. Knowing which kind you are using, and why the two kinds exist, is the difference between "regex is fine" and a 3 a.m. page.
This lesson opens the box. You will:
- See what a regular language is and which patterns can and cannot describe one.
- Compile a regex into a nondeterministic finite automaton (NFA) with Ken Thompson's construction (1968), one small diagram per operator.
- Run that NFA over a text by keeping a set of current states, which costs for a text of length and a pattern of length , never more. This is the idea behind the Pike VM used by RE2, Go and Rust.
- Turn the NFA into a deterministic automaton (DFA) with the subset construction, watch the number of states explode to on a pattern only long, and see how lazy DFAs dodge the explosion.
- Build a backtracking matcher, measure it doing steps on
(a+)+, and learn why backtracking engines exist anyway: backreferences, which no automaton can handle and which make matching NP-hard. - Write a complete tiny regex engine in four languages, tested against each language's own regex library on 60,000 random cases.
What this page is not. It does not teach regex syntax or how to write good patterns; Regex Mastery does that, and the regex cheat sheet is the quick reference. It does not re-derive the dynamic-programming solution to LeetCode's "regular expression matching"; String DP does, and this page shows that the DP table is an NFA simulation in disguise.
A word about the word "NFA"
Jeffrey Friedl's book Mastering Regular Expressions and many tutorials (including the performance section of Regex Mastery) call backtracking engines "NFA engines" and automaton-based engines "DFA engines". In computer science, an NFA is a mathematical object, and both kinds of engine start from one. The real difference is the search strategy: a backtracking engine explores the NFA's choices one at a time, depth-first; an automaton engine explores all of them at once. This page uses "backtracking engine" and "automaton engine" (or "linear-time engine") to avoid the clash.
Pattern triggers
| If the problem says or has… | Think of… |
|---|---|
"implement . and * matching", "wildcard ? and *" | NFA simulation, or the equivalent DP table (String DP) |
| "validate a number / identifier / token with these rules" | Draw a small DFA by hand; one table lookup per character |
| "count strings of length that match this regex" | Regex → NFA → DFA, then count paths of length (matrix exponentiation) |
| "match a regex against untrusted input", "user-supplied patterns" | A linear-time engine (RE2, Go regexp, Rust regex, .NET NonBacktracking) |
| A regex is slow on long inputs that almost match | Catastrophic backtracking: nested or overlapping quantifiers |
"the same text must appear twice" ((\w+) \1) | Backreferences: only a backtracking engine can do this, and the worst case is exponential |
| Many fixed strings at once (`foo | bar |
| "build a lexer / tokenizer" | Union of token regexes → one DFA (what lex and flex generate) |
Intuition & first principles
Regular languages, in plain words
Fix an alphabet, a finite set of symbols such as or all bytes. A string is a finite sequence of symbols; the empty string is written . A language is any set of strings, finite or infinite. "All strings that end in abb" is a language. So is "all strings with as many as as bs".
A regular expression describes a language using three operations on top of single symbols:
| Regex | Language | Example |
|---|---|---|
a (one symbol) | just the one-letter string | a → |
| (concatenation) | a string of followed by a string of | ab → |
| (alternation, union) | strings of or of | `a |
| (Kleene star) | zero or more strings of glued together | a* → |
Everything else in "classic" regex syntax is shorthand: r+ is rr*, r? is (r|), . is "any symbol" (a big alternation), [a-z] is a 26-way alternation, r{3} is rrr. Precedence goes star (and +, ?) first, then concatenation, then |: ab*|c means (a(b*))|c.
A language is regular if some regular expression describes it. Kleene's theorem (1956) says the regular languages are exactly the languages that a finite automaton can recognise: a machine with a fixed, finite number of states that reads the string one symbol at a time and never looks back. That equivalence is the whole foundation of this page. The proof in one direction is Thompson's construction below; the other direction (automaton → regex) exists too but is not needed here.
What is not regular? Anything that needs unbounded counting. (some as, then the same number of bs) is not regular: a machine with states reading must visit some state twice (pigeonhole), so it cannot tell from for some , and then it must treat and the same way. This is the pumping lemma argument (Sipser, ch. 1.4). Balanced parentheses, nested HTML tags and arithmetic expressions fail for the same reason, which is why you parse them with a stack or a real parser, not a "pure" regex.
A finite automaton is a board game
Draw states as circles and transitions as arrows labelled with symbols. Put a token on the start state. Read the string left to right; for each symbol, move the token along an arrow with that label. When the string ends, you accept if the token sits on an accepting state.
- In a DFA (deterministic finite automaton), every state has exactly one arrow per symbol. There is never a choice, so one token suffices. Matching costs one table lookup per character: , the fastest possible.
- In an NFA (nondeterministic finite automaton), a state may have several arrows with the same label, none, or arrows labelled that you may follow without reading anything. The NFA accepts if some sequence of choices ends on an accepting state.
NFAs are easy to build from a regex (each operator is a small gadget with arrows). DFAs are fast to run. Everything in this lesson is about getting from one to the other, or running the NFA without paying for the conversion.
Two ways to run an NFA
Take the NFA for (a|b)*abb ("strings over a, b that end in abb") and the input babb. At the very first a the machine has a real choice: is this the a of the final abb, or just another letter inside (a|b)*?
- Guess and back up. Pick one option, carry on, and if you get stuck, return to the last choice and try the other. This is depth-first search over choices: backtracking. It is simple, it uses little memory, and it can try combinations.
- Keep every option alive. Instead of one token, put a token on every state you could be in. On each symbol, move all tokens at once, merge tokens that land on the same state, and drop the ones with no arrow to follow. This is breadth-first search over the NFA, one layer per input character. The number of tokens can never exceed the number of states, , so each character costs and the whole match .
Ken Thompson's 1968 paper did option 2 and compiled it to IBM 7094 machine code. Henry Spencer's widely copied 1986 regex library did option 1. Perl's engine grew out of Spencer's code, and PCRE, Python's re, Java's java.util.regex and the JavaScript engines are independent implementations of the same backtracking approach. Russ Cox's 2007 article Regular Expression Matching Can Be Simple And Fast tells this history and is the best short companion to this page.
Mechanics
The pipeline every automaton engine follows:
flowchart LR
SRC["pattern text"] --> PARSE["parse: precedence, groups"]
PARSE --> NFA["Thompson NFA, O(m) states"]
NFA --> SIM["simulate: set of states, O(nm)"]
NFA --> DFA["subset construction: DFA, up to 2^m states"]
DFA --> RUN["run DFA: O(n)"]
NFA --> LAZY["lazy DFA: build states on demand"]
LAZY --> RUN
Step 0: parse the pattern
The pattern ab*|c must become a tree that respects precedence. A recursive-descent parser has one function per precedence level, the same shape as the expression parsers in Stacks:
alt := concat ('|' concat)* lowest precedence
concat := repeat* (may be empty: matches "")
repeat := atom ('*' | '+' | '?')* highest precedence
atom := '(' alt ')' | '.' | '\' char | char
Our engine does not build the tree explicitly. Each grammar function returns an NFA fragment for the piece of pattern it parsed, and the caller glues fragments together. That is Thompson's construction done on the fly.
Step 1: Thompson's construction, one operator at a time
A fragment is a little NFA with exactly one start state (drawn on the left) and exactly one accept state (on the right) that has no outgoing arrows yet. Fragments are combined by adding arrows, never by changing their insides. Here is the gadget for each operator. Boxes labelled r and s stand for whole sub-fragments.
A single symbol a (or ., which matches any one symbol): two states, one labelled arrow.
flowchart LR
S0(("s")) -->|"a"| A0(("f"))
Concatenation rs: an arrow from r's accept state to s's start state. (Textbooks often merge the two states instead; the language is the same.)
flowchart LR
R["fragment r"] -->|"ε"| S["fragment s"]
Alternation r|s: a new start state with arrows into both branches, and a new accept state that both branches lead to.
flowchart LR
S0(("s")) -->|"ε"| R["fragment r"]
S0 -->|"ε"| S["fragment s"]
R -->|"ε"| F(("f"))
S -->|"ε"| F
Star r*: a new start state that can enter r or skip it; from r's accept, either loop back to r's start or leave.
flowchart LR
S0(("s")) -->|"ε enter"| R["fragment r"]
S0 -->|"ε skip"| F(("f"))
R -->|"ε again"| R
R -->|"ε leave"| F
Plus r+: the same as star without the skip arrow (at least one pass through r).
flowchart LR
S0(("s")) -->|"ε"| R["fragment r"]
R -->|"ε again"| R
R -->|"ε leave"| F(("f"))
Optional r?: the same as star without the loop arrow (at most one pass).
flowchart LR
S0(("s")) -->|"ε enter"| R["fragment r"]
S0 -->|"ε skip"| F(("f"))
R -->|"ε"| F
(The "again" arrow in the star and plus diagrams goes from r's accept state back to r's start state.)
Size. Each symbol adds 2 states and each operator adds at most 2, and every state ends up with at most one labelled arrow or at most two arrows. So a pattern of length gives an NFA with at most about states and arrows. This linear size is what makes everything after it efficient.
Worked example: (a|b)*abb
Building it by hand in the order the parser does (left to right, inner first), and numbering states in creation order exactly as the code below does:
a→ states 0 →a→ 1.b→ states 2 →b→ 3.a|b→ new start 4 (ε to 0 and 2), new accept 5 (ε from 1 and 3).(a|b)*→ new start 6, new accept 7. Arrows: 6 →ε→ 4 (enter), 6 →ε→ 7 (skip), 5 →ε→ 7 (leave), 5 →ε→ 4 (again).a,b,b→ 8 →a→ 9, 10 →b→ 11, 12 →b→ 13, glued by 7 →ε→ 8, 9 →ε→ 10, 11 →ε→ 12.
Start state 6, accept state 13, 14 states in total (the program's len(nfa.label) prints 14).
flowchart LR
s6(("6 start")) -->|"ε"| s4((4))
s6 -->|"ε"| s7((7))
s4 -->|"ε"| s0((0))
s4 -->|"ε"| s2((2))
s0 -->|"a"| s1((1))
s2 -->|"b"| s3((3))
s1 -->|"ε"| s5((5))
s3 -->|"ε"| s5
s5 -->|"ε"| s7
s5 -->|"ε"| s4
s7 -->|"ε"| s8((8))
s8 -->|"a"| s9((9))
s9 -->|"ε"| s10((10))
s10 -->|"b"| s11((11))
s11 -->|"ε"| s12((12))
s12 -->|"b"| s13(("13 accept"))
Step 2: simulate by keeping a set of states
Two helper operations:
- ε-closure of a set : every state reachable from using only arrows. Computed by a graph search (DFS with a stack) over arrows.
- step on symbol : from every state in the set that has an arrow labelled (or
.), follow it; then take the ε-closure of where you landed.
The algorithm:
current = closure({start})
for each character c of the text:
current = step(current, c)
if current is empty: return no match (no thread survives)
return accept ∈ current (full-match semantics)
Trace on babb (produced by the program; "accept?" means state 13 is in the set):
| After reading | Active states | accept? | What the states mean |
|---|---|---|---|
| (nothing) | {0, 2, 4, 6, 7, 8} | no | inside `(a |
b | {0, 2, 3, 4, 5, 7, 8} | no | b was consumed by the loop (2→3); state 8 is waiting again |
a | {0, 1, 2, 4, 5, 7, 8, 9, 10} | no | the a was both a loop letter (0→1) and the final a (8→9): two threads, no guessing |
b | {0, 2, 3, 4, 5, 7, 8, 11, 12} | no | the "final a" thread advanced to 11, 12 |
b | {0, 2, 3, 4, 5, 7, 8, 13} | yes | the thread reached 13: match |
On abab the sets after each letter are {…, 9, 10}, {…, 11, 12}, {…, 9, 10}, {…, 11, 12}: the thread that bet on "this is the final a" reaches 12 twice but never 13, so the answer is no.
Notice the third row. A backtracking engine would have had to guess whether that a belonged to the loop or to the suffix, and maybe back up. The simulation carries both possibilities in one set. The set never holds a state twice, so at most 14 states are touched per character, however long the text.
The DP table you already know is this set
In String DP, dp[i][j] is true when the first i text characters can match the first j pattern tokens. Row i of that table, read as "the set of j that are true", is exactly the set of active NFA states after i characters, for an NFA whose states are pattern positions. Filling the table row by row is NFA simulation.
The Pike VM: the same simulation, compiled to instructions
Production engines (RE2, Go's regexp, Rust's regex) store the NFA as a small program for a virtual machine, with four instructions: char c (consume c or die), split x, y (fork into two threads), jmp x, and match. (a|b)*abb compiles to:
0 split 1, 6 loop: try another letter (1) or leave (6)
1 split 2, 4 a or b
2 char a
3 jmp 5
4 char b
5 jmp 0
6 char a
7 char b
8 char b
9 match
A thread is a program counter. Running all threads in lock step, one input character at a time, and refusing to add a thread whose program counter is already in the list, is exactly the set simulation above: split and jmp are arrows, char is a labelled arrow. Rob Pike used this design in his sam text editor in the 1980s, and Russ Cox named it the Pike VM in Regular Expression Matching: the Virtual Machine Approach (2009).
The Pike VM adds two things the bare simulation lacks:
- Submatch capture. Each thread carries an array of saved positions; a
save kinstruction records the current text position in slotk. That is how(\w+)@(\w+)reports both groups in linear time. - Priority. Threads are kept in the order a backtracking engine would have tried them (left branch of
splitfirst). When two threads reach the same instruction, the higher-priority one wins, so the reported submatches are the same ones Perl or Python would report ("leftmost-first" semantics), even though no backtracking happens.
Step 3: the subset construction (NFA → DFA)
If the simulation always moves from one set of states to another, why not precompute those moves? Treat each distinct set as one state of a DFA. This is the subset construction (Rabin and Scott, 1959):
D0 = closure({start}); queue = [D0]
while queue not empty:
S = queue.pop()
for each symbol c:
T = step(S, c)
if T is new: give it a number, push it
record transition S --c--> T
accepting DFA states = sets that contain the NFA's accept state
For (a|b)*abb over the alphabet it finds 5 sets:
| DFA state | NFA states | on a | on b | accepting? |
|---|---|---|---|---|
| D0 (start) | {0, 2, 4, 6, 7, 8} | D1 | D2 | |
| D1 | {0, 1, 2, 4, 5, 7, 8, 9, 10} | D1 | D3 | |
| D2 | {0, 2, 3, 4, 5, 7, 8} | D1 | D2 | |
| D3 | {0, 2, 3, 4, 5, 7, 8, 11, 12} | D1 | D4 | |
| D4 | {0, 2, 3, 4, 5, 7, 8, 13} | D1 | D2 | yes |
flowchart LR
D0(("D0 start")) -->|"a"| D1((D1))
D0 -->|"b"| D2((D2))
D1 -->|"a"| D1
D1 -->|"b"| D3((D3))
D2 -->|"a"| D1
D2 -->|"b"| D2
D3 -->|"a"| D1
D3 -->|"b"| D4(("D4 accept"))
D4 -->|"a"| D1
D4 -->|"b"| D2
Read the states as "how much of abb have I just seen at the end": D1 = "…a", D3 = "…ab", D4 = "…abb", D0 and D2 = "nothing useful". Running this DFA on any text costs one lookup per character.
State blowup: when the DFA is exponentially bigger
The subset construction can create up to sets, and sometimes it really does need exponentially many. The standard example is
The pattern has length , and Thompson's NFA has states with our construction. But a DFA reading left to right never knows where the end is, so it must remember each of the last symbols: two different memories of length differ at some position , and appending more symbols moves that position to -th from the end, where one string has an a and the other a b. So no two of the possible memories can share a state (this is a fooling-set argument, the Myhill–Nerode theorem in miniature). Measured with the lab code below:
| NFA states | DFA from subset construction | minimal DFA | ||
|---|---|---|---|---|
| 0 | 10 | 3 | 2 | 2 |
| 1 | 16 | 5 | 4 | 4 |
| 2 | 22 | 9 | 8 | 8 |
| 3 | 28 | 17 | 16 | 16 |
| 5 | 40 | 65 | 64 | 64 |
| 8 | 58 | 513 | 512 | 512 |
| 10 | 70 | 2,049 | 2,048 | 2,048 |
So the minimal DFA for has exactly states (the subset construction finds one extra, the start set, which minimisation merges away). If you prefer the statement " states", it is the language "the -th symbol from the end is a", that is . A 40-character pattern like (a|b)*a(a|b)(a|b)… with needs two million DFA states; at 256 transitions of 4 bytes each, that is 2 GB of table. This is why no serious engine builds the full DFA up front for arbitrary patterns.
Lazy DFA: build only the states you visit
A lazy DFA (also called an on-the-fly or hybrid DFA) does the subset construction during the match. It keeps a cache from (set of NFA states, symbol) to the next set. On a cache hit, a step is one lookup, like a real DFA. On a miss, it does one NFA step, stores the result, and continues. A text of length can create at most new states, so the worst case is still , and the cache never holds more than states (and, in practice, a bounded number: when it fills, it is flushed).
In the lab below, on 200,000 random a/b characters and , the plain set simulation took 0.61 s, while the lazy DFA took 0.05 s (Python 3.12, Apple-silicon laptop; your numbers will differ). Random text visits all 2,048 states, so the lazy DFA built them all, but it paid the NFA-step price only 4,096 times (once per state and symbol) instead of 200,000 times. On real text with real patterns, the number of states visited is typically tiny.
This is what RE2 (Google, 2010) and Rust's regex crate do. RE2's DFA uses a fixed memory budget; if the cache has to be flushed too often, RE2 gives up on the DFA and falls back to NFA simulation, so the linear-time guarantee always holds (Cox, Regular Expression Matching in the Wild, 2010). A DFA can only say whether and where a match ends; to report capture groups, RE2 and Rust run the DFA to find the match boundaries and then run a Pike VM (or a bounded backtracker, which is safe because it is limited to the matched span and remembers which states it has tried) on just that span.
DFA minimisation
Different DFAs can recognise the same language. D0 and D2 above behave identically (from either one, every future input leads to the same verdict), so they can be merged. Minimisation finds the unique smallest DFA:
- Start with two groups: accepting and non-accepting states.
- Split a group whenever two of its states go, on some symbol, to different groups.
- Repeat until nothing splits. Each final group is one state.
This is Moore's algorithm, in the worst case. Hopcroft's algorithm (1971) refines more cleverly ("process the smaller half") and runs in . The result is unique up to renaming by the Myhill–Nerode theorem: its states correspond one-to-one to the classes of "strings that no future input can tell apart". Lexer generators minimise their DFAs to shrink the tables; regex engines usually skip minimisation because the lazy DFA never builds the whole thing.
Backtracking engines
How they work
A backtracking engine walks the regex like a recursive function: try the first alternative; if the rest of the pattern fails, come back and try the second. For a greedy quantifier, take as many repetitions as possible, then give them back one at a time. This is backtracking exactly as you know it from N-Queens: depth-first search over choices, undoing on failure.
It is used by Perl, PCRE (Philip Hazel, 1997; inside PHP, R, nginx and many more), Python's re, Java's java.util.regex, JavaScript engines (V8's Irregexp compiles regexes to machine code but still backtracks), Ruby's Onigmo and .NET's default engine.
The backtracking matcher in the Implementation section is 80 lines of Python. Its core is one function m(node, i, k): "match node starting at text position i, then call the continuation k with the position where it ended". A continuation is "the rest of the pattern, as a function". Alternation tries m(left, i, k) or m(right, i, k). A greedy star tries one more repetition first and calls k only if that fails. The function returns as soon as any path reaches the end.
Why they exist: features beyond regular languages
If automaton engines are always linear, why does anyone backtrack?
- Backreferences.
(\w+) \1matches a repeated word:\1must equal whatever group 1 captured. No finite automaton can do that, because the language is not regular (the machine would have to remember all of ). With backreferences, a "regex" can test for composite numbers:(aa+)\1+fully matches exactly when is composite (checked in Python for : it fails on exactly the primes 2, 3, 5, …, 37). - Lookaround.
(?=…),(?!…),(?<=…),(?<!…)assert something about the text around a position without consuming it. Backtracking makes these trivial to implement. (Some lookarounds can be compiled into automata, and some linear-time engines now support restricted forms, but the classic linear engines RE2, Go and Rust omit them.) - Leftmost-first submatches, lazy quantifiers, recursion, conditionals, atomic groups. These are all easy to define as "the order in which the backtracker tries things". Perl's semantics are literally "whatever the backtracker finds first".
- Simplicity and constant factors. On typical patterns and inputs, a backtracker with good optimisations (literal prefix scans, first-character tables, JIT compilation) is very fast and needs almost no memory.
Backreferences make matching NP-hard
How hard can matching with backreferences be? NP-complete, when the pattern is part of the input. Alfred Aho proved this in "Algorithms for finding patterns in strings" (Handbook of Theoretical Computer Science, vol. A, ch. 5, 1990), by reducing an NP-complete problem to "does this regex with backreferences match this string". So unless P = NP, no engine can match every backreference pattern in polynomial time, and backtracking engines are not lazy for using exponential search: for this feature, nobody knows anything fundamentally better.
For a fixed pattern with capture groups that are referenced, matching is polynomial but with a degree that grows with : guess the start and end of each referenced group ( choices each), then the rest is an ordinary regular match. The NP-hardness comes from letting the number of groups grow with the input.
This is the honest trade-off at the heart of the two engine families:
Automaton engines (RE2, Go, Rust, .NET NonBacktracking) | Backtracking engines (PCRE, Perl, Python, Java, JS, .NET default) | |
|---|---|---|
| Worst-case time | ; lazy DFA usually | exponential in |
| Backreferences | no | yes |
| Lookaround | no (or restricted) | yes |
| Memory | DFA cache, bounded | recursion/backtrack stack |
| Safe on untrusted patterns and input | yes (with size limits on the pattern) | no, without timeouts |
Catastrophic backtracking
(a+)+ walked through
Match (a+)+ against aaab with full-match semantics (as re.fullmatch does). The text cannot match because of the b, but the engine does not know that until it reaches the b, and there are many ways to split aaa among the inner a+ and the outer +:
| Attempt | How the three as are grouped | What happens |
|---|---|---|
| 1 | [aaa] | inner a+ greedily takes all three; outer + tries another round, fails at b; end of pattern, but b is left over: fail |
| 2 | [aa][a] | inner gives back one a; outer starts a second round with it; b left: fail |
| 3 | [a][aa] | inner gives back another; second round takes aa; fail |
| 4 | [a][a][a] | three rounds; fail. No choices left: answer "no match" |
There are ways to cut letters into non-empty consecutive groups (choose, for each of the gaps, whether to cut there). The engine tries every one of them before giving up, and each attempt costs work too. Add one a and the work doubles.
Measured: steps in the toy backtracker
The backtracking matcher on this page counts how many times its recursive function is called. On (a+)+ against :
| steps | ratio to the row above | |
|---|---|---|
| 10 | 4,097 | |
| 12 | 16,385 | 4.00 |
| 14 | 65,537 | 4.00 |
| 16 | 262,145 | 4.00 |
| 18 | 1,048,577 | 4.00 |
| 20 | 4,194,305 | 4.00 |
The count is exactly : it doubles with every extra a. At it would be about calls, hours of CPU. The Thompson engine on the same input tracks at most 6 states per character, and on it answers "no" in about 4 ms (in Python).
Measured: Python's re
re.compile(r"(a+)+$").match("a" * n + "b"), best of 3 runs, CPython 3.12 on an Apple-silicon laptop. These timings are specific to that machine; the doubling is not.
| time | |
|---|---|
| 16 | 1.3 ms |
| 18 | 5.0 ms |
| 20 | 19.9 ms |
| 22 | 78.5 ms |
| 24 | 314 ms |
| 26 | 1,275 ms |
Every two extra characters multiply the time by four. A 30-character input would take about 20 seconds and a 40-character one about 6 hours. A single HTTP request with a 40-character form field can therefore pin a CPU core for hours. That attack is called ReDoS (regular-expression denial of service).
The danger signs are a quantified group whose body can match the same text in more than one way, followed by something that can fail: (a+)+, (a|a)*, (a|ab)*c, (\w+\s?)*$, (.*,){12}x. In 2018 Davis, Coghlan, Servant and Lee found super-linear regexes in thousands of npm and PyPI modules ("The impact of regular expression denial of service (ReDoS) in practice", ESEC/FSE 2018).
Polynomial is also bad
Not every slow regex is exponential. \s+$ searched (unanchored) over spaces followed by x tries every start position, and from each one matches spaces to the end before failing: about steps. Measured with Python's re on the same laptop: 46 ms at 5,000 spaces, 152 ms at 10,000, 608 ms at 20,000, 2.5 s at 40,000 (×4 per doubling). Quadratic is enough to take down a website, as the next section shows.
Two real outages
Stack Overflow, 20 July 2016 (34 minutes)
A post contained roughly 20,000 consecutive whitespace characters on one line. The code that rendered posts ran a regex meant to trim Unicode space from the start and end of each line, ^[\s]+|[\s]+$. The second alternative is the \s+$ pattern from the warning above: for each of the ~20,000 start positions, the engine consumed the rest of the whitespace run and then failed, because the run was followed by other text, not the end of the line. That is about character checks for one page view. The post appeared on the home page, the home page was also the load balancer's health check, the health checks timed out, and the load balancer removed the servers from rotation. Fix: "This regular expression has been replaced with a substring function." Source: Stack Exchange, "Outage Postmortem – July 20, 2016".
Cloudflare, 2 July 2019 (27 minutes)
At 13:42 UTC an automated deployment pushed a new rule to Cloudflare's WAF Managed Rules globally (not in a staged rollout). The rule, meant to improve the blocking of inline JavaScript used in attacks, contained a regex with the sub-pattern .*(?:.*=.*). Two adjacent .* with a = between them means that for an input without the expected structure, the engine tries every way of splitting the text between the two stars, at every start position: super-linear backtracking. CPUs serving HTTP traffic hit nearly 100% across the network. The postmortem says the Lua-based WAF "uses backtracking for matching and has no mechanism to protect against a runaway expression". Cloudflare killed the WAF globally at 14:07; traffic and CPU recovered by 14:09. Their remediation list included re-introducing CPU-usage protection, auditing all 3,868 managed rules for excessive backtracking, performance profiling of rules in the test suite, staged rollouts, and switching to the RE2 or Rust regex engine, which "both have run-time guarantees". Source: John Graham-Cumming, "Details of the Cloudflare outage on July 2, 2019", Cloudflare blog.
Mitigations
From most to least robust:
- Use a linear-time engine for untrusted input or untrusted patterns. RE2 (C++, with bindings for most languages, including
google-re2for Python), Go'sregexp(Russ Cox's design: a Pike VM, a one-pass matcher and a bounded backtracker, all linear; no DFA, so slower than RE2 but always linear), Rust'sregex(lazy DFA plus Pike VM; used by ripgrep), .NET 7+RegexOptions.NonBacktracking(released November 2022; an automaton engine built on regex derivatives, from Microsoft Research's symbolic regex work), and Intel's Hyperscan for high-throughput multi-pattern scanning. V8 also ships an experimental linear-time engine behind a flag (--enable-experimental-regexp-engine, announced on the V8 blog in January 2021). All of these drop backreferences and (most) lookaround. - Rewrite the pattern so each piece of text can be matched only one way.
(a+)+is justa+.(\w+\s?)*becomes\w+(\s\w+)*.\s+$for trimming becomes a plain loop orrstrip(), which is what Stack Overflow did. - Atomic groups and possessive quantifiers.
(?>…)anda++tell the engine "once this part has matched, never give characters back".(?>a+)+fails on in linear time. Supported by PCRE, Perl, Java, .NET, Ruby, and Python'sresince 3.11; not by JavaScript. See Regex Mastery for the syntax. - Limits and timeouts. .NET's
Regexconstructor takes amatchTimeoutand throwsRegexMatchTimeoutException. PCRE2 has a match limit (default 10,000,000 internal calls). Ruby 3.2 addedRegexp.timeoutand a memoization cache that makes most patterns linear (memoizing the backtracker is the DP idea from the ladder below). Python's built-inrehas no timeout; the third-partyregexmodule accepts atimeoutargument. Java has none built in. Even libc++'sstd::regexgives up: while testing the C++ code below, it threwerror_complexityon the 8-character inputbbccacacfor the random pattern((.?|(.|.)))*((bb|b)|b). - Limit input length before matching. A 20-character cap on a field makes even survivable. It is a cheap last line of defence, not a fix.
- Test for it. Fuzz your regexes with long near-miss inputs (
"a" * 30 + "!"), and use static ReDoS detectors in CI where your ecosystem has one.
The ladder: brute force → better → optimal
Problem: does pattern (length ) fully match text (length )?
Rung 1: plain backtracking. Try choices depth-first. Simple, supports everything, near-instant on typical inputs. Worst case time (or worse with nested quantifiers), stack.
Rung 2: memoized backtracking (the DP). The backtracker's state is really just (position in pattern, position in text). There are only such pairs, and the answer for a pair never changes, so remember it. Now the worst case is . This is the String DP solution, and Ruby 3.2's fix. Cost: memory for the memo table (unless you go row by row).
Rung 3: Thompson NFA simulation (Pike VM). Process the text left to right, holding the set of live pattern positions. Same time, but only memory, one pass over the text (so it works on streams), and with the Pike VM, captures with leftmost-first priority.
Rung 4: DFA. Precompute the transitions between sets: matching with one table lookup per character, but up to build time and memory.
Rung 5: lazy DFA with fallback. Build DFA states only when reached, cache them in bounded memory, fall back to rung 3 when the cache thrashes. in practice, guaranteed. This is RE2 and Rust regex.
| Approach | Time to match | Extra memory | Backreferences | Captures |
|---|---|---|---|---|
| Backtracking | worst | stack | yes | yes |
| Memoized backtracking / DP | no (memo key breaks) | yes | ||
| Thompson / Pike VM | no | yes (Pike VM) | ||
| Full DFA | + build | no | no (needs a second pass) | |
| Lazy DFA + fallback | typical, worst | bounded cache | no | via second pass |
Correctness
Claim 1 (Thompson's construction). For every regex , the fragment built for has one start state and one accept state , has no outgoing arrows at the moment the fragment is finished, and a string labels a path from to if and only if .
Proof by structural induction. A single symbol: the only path is . Concatenation : any path from 's start to 's accept must cross the single new arrow from to (it is the only arrow leaving 's fragment, because had none and nothing else points outside), so it spells with , , and conversely. Alternation: a path from the new start enters exactly one branch (the two fragments share no states) and leaves it only through that branch's accept. Star: a path from the new start either skips straight to (spelling ) or enters , and each time it reaches it either loops back to or leaves; cutting the path at the loop arrows splits into pieces, each in by the hypothesis. Plus and optional are star with one arrow removed. Because has no outgoing arrows when the fragment is finished, wrapping it later cannot create a path that sneaks out of a fragment and back in.
Claim 2 (the simulation). After reading , current equals the set of states such that some path from the start to spells (counting arrows as spelling nothing).
Proof by induction on . For , those are exactly the states -reachable from the start: the closure. For : a path spelling ends with a last labelled arrow on , followed by arrows; the part before that arrow spells , so it ends in current by the hypothesis; step follows exactly those labelled arrows and then closes under . Conversely, every state step adds has such a path. With Claim 1, the accept state is in the final set if and only if .
Claim 3 (the subset construction). The DFA state reached on input is exactly the set from Claim 2 after reading , because the DFA's transition function is step. So the DFA accepts exactly when the simulation does.
Complexity
Let be the pattern length, the text length, the alphabet size.
| Operation | Time | Space | Why |
|---|---|---|---|
| Parse + Thompson construction | states and arrows | constant work per pattern symbol | |
| ε-closure of one set | DFS over ε arrows per state, each state visited once | ||
| NFA simulation | worst, best (stops when the set is empty) | one closure per character | |
| Subset construction | worst | up to sets, each stepped on each symbol | |
| DFA match | table | one lookup per character | |
| Moore minimisation | for DFA states | at most refinement rounds | |
| Hopcroft minimisation | each state moves to a "smaller half" times | ||
| Lazy DFA match | per cached step, per miss; worst | cache, bounded by policy | at most one miss per (state, symbol) |
| Backtracking match | worst for regular patterns; NP-hard with backreferences | stack | every split may be tried |
Search instead of full match ("is there a match anywhere?") costs the same for the simulation: add the start state's closure to the set at every position, which is equivalent to prefixing the pattern with .* (the capstone's grep mode does exactly this). A backtracker instead retries from every start position, multiplying its worst case by .
Implementation
The engine below supports literals, ., *, +, ?, |, parentheses and \ escapes (\* is a literal star). It uses full-match semantics: matches("a+", "aaa") is true, matches("a+", "aab") is false, like Python's re.fullmatch and Java's String.matches. Each main checks hand-picked cases, confirms that (a+)+ on 30 as and a b returns instantly, and then compares the engine with the language's own regex library on 3,000 random patterns × 20 random strings: 60,000 cases, all agreeing. (The C++ version anchors with ^(?:…)$ for std::regex_search and counts the cases where libc++'s std::regex gave up; in our run it gave up on 4 of 60,000.)
Every snippet was run: Python 3.12, Java 21 (javac TinyRegex.java && java TinyRegex), C++17 with Apple clang 21 and libc++ (g++ -std=c++17 -O2 -Wall), TypeScript with Node 24 (type stripping).
"""A tiny regex engine: literals, ., *, +, ?, |, ( ) and \\ escapes.
parse (recursive descent) -> Thompson NFA -> set-of-states simulation.
Full-match semantics: the whole text must match, like re.fullmatch.
"""
class NFA:
"""States are integers. Each state has at most one labelled edge
(a character, or ANY for '.') and any number of epsilon edges."""
ANY = object()
def __init__(self) -> None:
self.label: list = [] # label[s]: char, NFA.ANY or None
self.target: list[int] = [] # where the labelled edge goes
self.eps: list[list[int]] = [] # epsilon edges
self.start = self.accept = -1
def new_state(self) -> int:
self.label.append(None)
self.target.append(-1)
self.eps.append([])
return len(self.label) - 1
class Parser:
"""Grammar: alt := concat ('|' concat)*
concat := repeat*
repeat := atom ('*' | '+' | '?')*
atom := '(' alt ')' | '.' | '\\' char | literal char
Every rule returns a fragment (start, accept) of a Thompson NFA."""
def __init__(self, pattern: str) -> None:
self.p, self.i, self.nfa = pattern, 0, NFA()
def peek(self):
return self.p[self.i] if self.i < len(self.p) else None
def parse(self) -> NFA:
start, accept = self.alt()
if self.i != len(self.p):
raise ValueError(f"unexpected {self.p[self.i]!r} at {self.i}")
self.nfa.start, self.nfa.accept = start, accept
return self.nfa
def alt(self):
s1, a1 = self.concat()
while self.peek() == "|":
self.i += 1
s2, a2 = self.concat()
s, a = self.nfa.new_state(), self.nfa.new_state()
self.nfa.eps[s] += [s1, s2] # choose a branch
self.nfa.eps[a1].append(a) # both branches rejoin
self.nfa.eps[a2].append(a)
s1, a1 = s, a
return s1, a1
def concat(self):
if self.peek() in (None, "|", ")"): # empty: matches ""
s = self.nfa.new_state()
return s, s
s, a = self.repeat()
while self.peek() not in (None, "|", ")"):
s2, a2 = self.repeat()
self.nfa.eps[a].append(s2) # glue with an epsilon edge
a = a2
return s, a
def repeat(self):
s1, a1 = self.atom()
while self.peek() in ("*", "+", "?"):
op = self.p[self.i]
self.i += 1
s, a = self.nfa.new_state(), self.nfa.new_state()
self.nfa.eps[s].append(s1) # enter the body
if op in "*?":
self.nfa.eps[s].append(a) # or skip it
self.nfa.eps[a1].append(a) # leave after the body
if op in "*+":
self.nfa.eps[a1].append(s1) # or go round again
s1, a1 = s, a
return s1, a1
def atom(self):
c = self.peek()
if c is None or c in "*+?":
raise ValueError(f"expected an atom at {self.i}")
if c == "(":
self.i += 1
frag = self.alt()
if self.peek() != ")":
raise ValueError("missing )")
self.i += 1
return frag
if c == "\\":
self.i += 1
if self.peek() is None:
raise ValueError("trailing backslash")
c = self.p[self.i]
label = c
else:
label = NFA.ANY if c == "." else c
self.i += 1
s, a = self.nfa.new_state(), self.nfa.new_state()
self.nfa.label[s], self.nfa.target[s] = label, a
return s, a
def compile_regex(pattern: str) -> NFA:
return Parser(pattern).parse()
def closure(nfa: NFA, states) -> set[int]:
"""All states reachable from `states` by epsilon edges only."""
seen, stack = set(states), list(states)
while stack:
s = stack.pop()
for t in nfa.eps[s]:
if t not in seen:
seen.add(t)
stack.append(t)
return seen
def step(nfa: NFA, current: set[int], ch: str) -> set[int]:
moved = [nfa.target[s] for s in current
if nfa.label[s] is NFA.ANY or nfa.label[s] == ch]
return closure(nfa, moved)
def full_match(nfa: NFA, text: str) -> bool:
current = closure(nfa, [nfa.start])
for ch in text:
current = step(nfa, current, ch)
if not current: # no thread survives
return False
return nfa.accept in current
def matches(pattern: str, text: str) -> bool:
return full_match(compile_regex(pattern), text)
def random_pattern(rng, depth: int = 0) -> str:
"""A random pattern over {a, b, .} using every operator."""
x = rng.random()
if depth > 3 or x < 0.35:
return rng.choice("ab.")
if x < 0.55:
return random_pattern(rng, depth + 1) + random_pattern(rng, depth + 1)
if x < 0.70:
return "(" + random_pattern(rng, depth + 1) + "|" + random_pattern(rng, depth + 1) + ")"
if x < 0.85:
return "(" + random_pattern(rng, depth + 1) + ")" + rng.choice("*+?")
return rng.choice("ab.") + rng.choice("*+?")
if __name__ == "__main__":
import random
import re
assert matches("(a|b)*abb", "babb") and not matches("(a|b)*abb", "abab")
assert matches("a+b?c*", "aaacc") and not matches("a+b?c*", "bc")
assert matches("h.llo|bye", "hallo") and matches("(ab)+", "ababab")
assert matches("a\\*b", "a*b") and matches("", "") and matches("(a|)", "")
assert not matches("(a+)+", "a" * 30 + "b") # instant, unlike backtracking
assert len(compile_regex("(a|b)*abb").label) == 14
rng = random.Random(1)
checked = 0
for _ in range(3000): # compare with Python's re
pattern = random_pattern(rng)
nfa, theirs = compile_regex(pattern), re.compile(pattern)
for _ in range(20):
s = "".join(rng.choice("abc") for _ in range(rng.randint(0, 8)))
assert full_match(nfa, s) == bool(theirs.fullmatch(s)), (pattern, s)
checked += 1
print(f"all tests passed; {checked} random cases agree with re.fullmatch")
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Random;
import java.util.regex.Pattern;
/** Tiny regex engine: literals, ., *, +, ?, |, ( ), \ escapes. Thompson NFA + simulation. */
public class TinyRegex {
static final char NONE = 0, ANY = 1; // label kinds besides real chars
// --- the NFA: parallel arrays indexed by state id
final List<Character> label = new ArrayList<>(); // NONE, ANY or a character
final List<Integer> target = new ArrayList<>(); // destination of the labelled edge
final List<List<Integer>> eps = new ArrayList<>(); // epsilon edges
int start, accept;
private final String p;
private int i = 0;
private TinyRegex(String pattern) {
p = pattern;
int[] f = alt();
if (i != p.length()) throw new IllegalArgumentException("unexpected '" + p.charAt(i) + "' at " + i);
start = f[0];
accept = f[1];
}
public static TinyRegex compile(String pattern) { return new TinyRegex(pattern); }
private int newState() {
label.add(NONE);
target.add(-1);
eps.add(new ArrayList<>());
return label.size() - 1;
}
private char peek() { return i < p.length() ? p.charAt(i) : '\0'; }
private boolean atEnd() { return i >= p.length(); }
// alt := concat ('|' concat)*
private int[] alt() {
int[] a = concat();
while (!atEnd() && peek() == '|') {
i++;
int[] b = concat();
int s = newState(), f = newState();
eps.get(s).add(a[0]);
eps.get(s).add(b[0]);
eps.get(a[1]).add(f);
eps.get(b[1]).add(f);
a = new int[] {s, f};
}
return a;
}
private boolean concatEnds() { return atEnd() || peek() == '|' || peek() == ')'; }
// concat := repeat*
private int[] concat() {
if (concatEnds()) {
int s = newState();
return new int[] {s, s};
}
int[] f = repeat();
while (!concatEnds()) {
int[] g = repeat();
eps.get(f[1]).add(g[0]);
f = new int[] {f[0], g[1]};
}
return f;
}
// repeat := atom ('*' | '+' | '?')*
private int[] repeat() {
int[] f = atom();
while (!atEnd() && (peek() == '*' || peek() == '+' || peek() == '?')) {
char op = p.charAt(i++);
int s = newState(), a = newState();
eps.get(s).add(f[0]);
if (op != '+') eps.get(s).add(a);
eps.get(f[1]).add(a);
if (op != '?') eps.get(f[1]).add(f[0]);
f = new int[] {s, a};
}
return f;
}
// atom := '(' alt ')' | '.' | '\' char | char
private int[] atom() {
if (atEnd() || "*+?".indexOf(peek()) >= 0) throw new IllegalArgumentException("expected an atom at " + i);
char c = p.charAt(i++);
if (c == '(') {
int[] f = alt();
if (atEnd() || peek() != ')') throw new IllegalArgumentException("missing )");
i++;
return f;
}
char lab = c == '.' ? ANY : c;
if (c == '\\') {
if (atEnd()) throw new IllegalArgumentException("trailing backslash");
lab = p.charAt(i++);
}
int s = newState(), a = newState();
label.set(s, lab);
target.set(s, a);
return new int[] {s, a};
}
/** Adds every state reachable by epsilon edges to the set (in-place). */
private void closure(boolean[] in, ArrayDeque<Integer> stack) {
while (!stack.isEmpty()) {
int s = stack.pop();
for (int t : eps.get(s)) {
if (!in[t]) { in[t] = true; stack.push(t); }
}
}
}
public boolean fullMatch(String text) {
int n = label.size();
boolean[] cur = new boolean[n];
ArrayDeque<Integer> stack = new ArrayDeque<>();
cur[start] = true;
stack.push(start);
closure(cur, stack);
for (int k = 0; k < text.length(); k++) {
char ch = text.charAt(k);
boolean[] next = new boolean[n];
boolean any = false;
for (int s = 0; s < n; s++) {
char lab = label.get(s);
if (cur[s] && lab != NONE && (lab == ANY || lab == ch)) {
int t = target.get(s);
if (!next[t]) { next[t] = true; stack.push(t); any = true; }
}
}
if (!any) return false;
closure(next, stack);
cur = next;
}
return cur[accept];
}
public static boolean matches(String pattern, String text) { return compile(pattern).fullMatch(text); }
// --- random patterns over {a, b, .} to compare with java.util.regex
static String gen(Random r, int depth) {
double x = r.nextDouble();
String atoms = "ab.";
if (depth > 3 || x < 0.35) return String.valueOf(atoms.charAt(r.nextInt(3)));
if (x < 0.55) return gen(r, depth + 1) + gen(r, depth + 1);
if (x < 0.70) return "(" + gen(r, depth + 1) + "|" + gen(r, depth + 1) + ")";
if (x < 0.85) return "(" + gen(r, depth + 1) + ")" + "*+?".charAt(r.nextInt(3));
return "" + atoms.charAt(r.nextInt(3)) + "*+?".charAt(r.nextInt(3));
}
public static void main(String[] args) {
if (!matches("(a|b)*abb", "babb") || matches("(a|b)*abb", "abab")) throw new AssertionError();
if (!matches("a+b?c*", "aaacc") || matches("a+b?c*", "bc")) throw new AssertionError();
if (!matches("h.llo|bye", "hallo") || !matches("(ab)+", "ababab")) throw new AssertionError();
if (!matches("a\\*b", "a*b") || !matches("", "") || !matches("(a|)", "")) throw new AssertionError();
if (matches("(a+)+", "a".repeat(30) + "b")) throw new AssertionError();
if (compile("(a|b)*abb").label.size() != 14) throw new AssertionError();
Random r = new Random(1);
int checked = 0;
for (int t = 0; t < 3000; t++) {
String pat = gen(r, 0);
TinyRegex mine = compile(pat);
Pattern theirs = Pattern.compile(pat);
for (int k = 0; k < 20; k++) {
StringBuilder sb = new StringBuilder();
int len = r.nextInt(9);
for (int j = 0; j < len; j++) sb.append("abc".charAt(r.nextInt(3)));
String s = sb.toString();
if (mine.fullMatch(s) != theirs.matcher(s).matches())
throw new AssertionError(pat + " on " + s);
checked++;
}
}
System.out.println("all tests passed; " + checked + " random cases agree with java.util.regex");
}
}
// Tiny regex engine: literals, ., *, +, ?, |, ( ), \ escapes. Thompson NFA + simulation.
#include <cassert>
#include <iostream>
#include <random>
#include <regex>
#include <stdexcept>
#include <string>
#include <utility>
#include <vector>
class TinyRegex {
public:
static constexpr int NONE = -1, ANY = -2; // label kinds besides real chars
explicit TinyRegex(const std::string& pattern) : p_(pattern) {
auto f = alt();
if (i_ != p_.size()) throw std::invalid_argument("unexpected character in pattern");
start_ = f.first;
accept_ = f.second;
}
bool fullMatch(const std::string& text) const {
const int n = static_cast<int>(label_.size());
std::vector<char> cur(n, 0), next(n, 0);
std::vector<int> stack;
cur[start_] = 1;
stack.push_back(start_);
closure(cur, stack);
for (char ch : text) {
std::fill(next.begin(), next.end(), 0);
for (int s = 0; s < n; ++s) {
int lab = label_[s];
if (cur[s] && lab != NONE && (lab == ANY || lab == static_cast<unsigned char>(ch))) {
int t = target_[s];
if (!next[t]) { next[t] = 1; stack.push_back(t); }
}
}
if (stack.empty()) return false; // no thread survives
closure(next, stack);
std::swap(cur, next);
}
return cur[accept_];
}
std::size_t stateCount() const { return label_.size(); }
private:
using Frag = std::pair<int, int>; // (start, accept)
std::string p_;
std::size_t i_ = 0;
std::vector<int> label_, target_;
std::vector<std::vector<int>> eps_;
int start_ = 0, accept_ = 0;
int newState() {
label_.push_back(NONE);
target_.push_back(-1);
eps_.emplace_back();
return static_cast<int>(label_.size()) - 1;
}
bool atEnd() const { return i_ >= p_.size(); }
char peek() const { return atEnd() ? '\0' : p_[i_]; }
bool concatEnds() const { return atEnd() || peek() == '|' || peek() == ')'; }
void closure(std::vector<char>& in, std::vector<int>& stack) const {
while (!stack.empty()) {
int s = stack.back();
stack.pop_back();
for (int t : eps_[s])
if (!in[t]) { in[t] = 1; stack.push_back(t); }
}
}
Frag alt() { // alt := concat ('|' concat)*
Frag a = concat();
while (!atEnd() && peek() == '|') {
++i_;
Frag b = concat();
int s = newState(), f = newState();
eps_[s] = {a.first, b.first};
eps_[a.second].push_back(f);
eps_[b.second].push_back(f);
a = {s, f};
}
return a;
}
Frag concat() { // concat := repeat*
if (concatEnds()) { int s = newState(); return {s, s}; }
Frag f = repeat();
while (!concatEnds()) {
Frag g = repeat();
eps_[f.second].push_back(g.first);
f.second = g.second;
}
return f;
}
Frag repeat() { // repeat := atom ('*' | '+' | '?')*
Frag f = atom();
while (!atEnd() && (peek() == '*' || peek() == '+' || peek() == '?')) {
char op = p_[i_++];
int s = newState(), a = newState();
eps_[s].push_back(f.first);
if (op != '+') eps_[s].push_back(a);
eps_[f.second].push_back(a);
if (op != '?') eps_[f.second].push_back(f.first);
f = {s, a};
}
return f;
}
Frag atom() { // atom := '(' alt ')' | '.' | '\' char | char
if (atEnd() || peek() == '*' || peek() == '+' || peek() == '?')
throw std::invalid_argument("expected an atom");
char c = p_[i_++];
if (c == '(') {
Frag f = alt();
if (atEnd() || peek() != ')') throw std::invalid_argument("missing )");
++i_;
return f;
}
int lab = (c == '.') ? ANY : static_cast<unsigned char>(c);
if (c == '\\') {
if (atEnd()) throw std::invalid_argument("trailing backslash");
lab = static_cast<unsigned char>(p_[i_++]);
}
int s = newState(), a = newState();
label_[s] = lab;
target_[s] = a;
return {s, a};
}
};
bool matches(const std::string& p, const std::string& t) { return TinyRegex(p).fullMatch(t); }
std::string gen(std::mt19937& r, int depth) { // random pattern over {a, b, .}
std::uniform_real_distribution<double> u(0, 1);
const std::string atoms = "ab.", ops = "*+?";
double x = u(r);
if (depth > 3 || x < 0.35) return std::string(1, atoms[r() % 3]);
if (x < 0.55) return gen(r, depth + 1) + gen(r, depth + 1);
if (x < 0.70) return "(" + gen(r, depth + 1) + "|" + gen(r, depth + 1) + ")";
if (x < 0.85) return "(" + gen(r, depth + 1) + ")" + ops[r() % 3];
return std::string(1, atoms[r() % 3]) + ops[r() % 3];
}
int main() {
assert(matches("(a|b)*abb", "babb") && !matches("(a|b)*abb", "abab"));
assert(matches("a+b?c*", "aaacc") && !matches("a+b?c*", "bc"));
assert(matches("h.llo|bye", "hallo") && matches("(ab)+", "ababab"));
assert(matches("a\\*b", "a*b") && matches("", "") && matches("(a|)", ""));
assert(!matches("(a+)+", std::string(30, 'a') + "b"));
assert(TinyRegex("(a|b)*abb").stateCount() == 14);
std::mt19937 r(1);
int checked = 0, gaveUp = 0;
for (int t = 0; t < 3000; ++t) {
std::string pat = gen(r, 0);
TinyRegex mine(pat);
std::regex theirs("^(?:" + pat + ")$"); // ECMAScript grammar, anchored
for (int k = 0; k < 20; ++k) {
std::string s;
int len = r() % 9;
for (int j = 0; j < len; ++j) s += "abc"[r() % 3];
bool want;
try {
want = std::regex_search(s, theirs);
} catch (const std::regex_error&) { // libc++ backtracker hit its step limit
++gaveUp;
continue;
}
if (mine.fullMatch(s) != want) {
std::cerr << "MISMATCH " << pat << " on " << s << '\n';
return 1;
}
++checked;
}
}
std::cout << "all tests passed; " << checked << " random cases agree with std::regex ("
<< gaveUp << " where std::regex gave up)\n";
}
// Tiny regex engine: literals, ., *, +, ?, |, ( ), \ escapes. Thompson NFA + simulation.
const NONE = "", ANY = "ANY"; // label kinds besides single characters
type Frag = [number, number]; // [start, accept]
class TinyRegex {
label: string[] = []; // NONE, ANY or one character
target: number[] = []; // destination of the labelled edge
eps: number[][] = []; // epsilon edges
start = 0;
accept = 0;
private p: string;
private i = 0;
constructor(pattern: string) {
this.p = pattern;
const f = this.alt();
if (this.i !== this.p.length) throw new Error(`unexpected '${this.p[this.i]}' at ${this.i}`);
[this.start, this.accept] = f;
}
private newState(): number {
this.label.push(NONE);
this.target.push(-1);
this.eps.push([]);
return this.label.length - 1;
}
private peek(): string | undefined { return this.p[this.i]; }
private concatEnds(): boolean {
const c = this.peek();
return c === undefined || c === "|" || c === ")";
}
private alt(): Frag { // alt := concat ('|' concat)*
let a = this.concat();
while (this.peek() === "|") {
this.i++;
const b = this.concat();
const s = this.newState(), f = this.newState();
this.eps[s].push(a[0], b[0]);
this.eps[a[1]].push(f);
this.eps[b[1]].push(f);
a = [s, f];
}
return a;
}
private concat(): Frag { // concat := repeat*
if (this.concatEnds()) { const s = this.newState(); return [s, s]; }
const f = this.repeat();
while (!this.concatEnds()) {
const g = this.repeat();
this.eps[f[1]].push(g[0]);
f[1] = g[1];
}
return f;
}
private repeat(): Frag { // repeat := atom ('*' | '+' | '?')*
let f = this.atom();
let op = this.peek();
while (op === "*" || op === "+" || op === "?") {
this.i++;
const s = this.newState(), a = this.newState();
this.eps[s].push(f[0]);
if (op !== "+") this.eps[s].push(a);
this.eps[f[1]].push(a);
if (op !== "?") this.eps[f[1]].push(f[0]);
f = [s, a];
op = this.peek();
}
return f;
}
private atom(): Frag { // atom := '(' alt ')' | '.' | '\' char | char
let c = this.peek();
if (c === undefined || "*+?".includes(c)) throw new Error(`expected an atom at ${this.i}`);
this.i++;
if (c === "(") {
const f = this.alt();
if (this.peek() !== ")") throw new Error("missing )");
this.i++;
return f;
}
let lab = c === "." ? ANY : c;
if (c === "\\") {
c = this.peek();
if (c === undefined) throw new Error("trailing backslash");
this.i++;
lab = c;
}
const s = this.newState(), a = this.newState();
this.label[s] = lab;
this.target[s] = a;
return [s, a];
}
private closure(inSet: Uint8Array, stack: number[]): void {
while (stack.length > 0) {
const s = stack.pop()!;
for (const t of this.eps[s]) {
if (!inSet[t]) { inSet[t] = 1; stack.push(t); }
}
}
}
fullMatch(text: string): boolean {
const n = this.label.length;
let cur = new Uint8Array(n);
const stack: number[] = [this.start];
cur[this.start] = 1;
this.closure(cur, stack);
for (const ch of text) {
const next = new Uint8Array(n);
for (let s = 0; s < n; s++) {
const lab = this.label[s];
if (cur[s] && lab !== NONE && (lab === ANY || lab === ch)) {
const t = this.target[s];
if (!next[t]) { next[t] = 1; stack.push(t); }
}
}
if (stack.length === 0) return false; // no thread survives
this.closure(next, stack);
cur = next;
}
return cur[this.accept] === 1;
}
}
const matches = (p: string, t: string): boolean => new TinyRegex(p).fullMatch(t);
function assert(cond: boolean, msg = "assertion failed"): void {
if (!cond) throw new Error(msg);
}
// Deterministic pseudo-random numbers (mulberry32) so runs are repeatable.
function rng(seed: number): () => number {
return () => {
seed = (seed + 0x6d2b79f5) | 0;
let t = Math.imul(seed ^ (seed >>> 15), 1 | seed);
t = (t + Math.imul(t ^ (t >>> 7), 61 | t)) ^ t;
return ((t ^ (t >>> 14)) >>> 0) / 4294967296;
};
}
function gen(r: () => number, depth: number): string {
const pick = (s: string) => s[Math.floor(r() * s.length)];
const x = r();
if (depth > 3 || x < 0.35) return pick("ab.");
if (x < 0.55) return gen(r, depth + 1) + gen(r, depth + 1);
if (x < 0.7) return "(" + gen(r, depth + 1) + "|" + gen(r, depth + 1) + ")";
if (x < 0.85) return "(" + gen(r, depth + 1) + ")" + pick("*+?");
return pick("ab.") + pick("*+?");
}
assert(matches("(a|b)*abb", "babb") && !matches("(a|b)*abb", "abab"));
assert(matches("a+b?c*", "aaacc") && !matches("a+b?c*", "bc"));
assert(matches("h.llo|bye", "hallo") && matches("(ab)+", "ababab"));
assert(matches("a\\*b", "a*b") && matches("", "") && matches("(a|)", ""));
assert(!matches("(a+)+", "a".repeat(30) + "b"));
assert(new TinyRegex("(a|b)*abb").label.length === 14);
const r = rng(1);
let checked = 0;
for (let t = 0; t < 3000; t++) {
const pat = gen(r, 0);
const mine = new TinyRegex(pat);
const theirs = new RegExp(`^(?:${pat})$`);
for (let k = 0; k < 20; k++) {
let s = "";
const len = Math.floor(r() * 9);
for (let j = 0; j < len; j++) s += "abc"[Math.floor(r() * 3)];
assert(mine.fullMatch(s) === theirs.test(s), `${pat} on ${s}`);
checked++;
}
}
console.log(`all tests passed; ${checked} random cases agree with RegExp`);
Reading the code. Parser.concat glues fragments with ε arrows; repeat handles all three quantifiers with one gadget (add "skip" unless +, add "again" unless ?). The simulation keeps a boolean array per step in Java, C++ and TypeScript, and a Python set; the "is this state already in the set?" check is what bounds the work at per character. The check if not current: return False is the early exit when every thread has died.
The backtracking matcher, for contrast (Python)
Same grammar, but parsed to a tree of tuples and matched depth-first with continuations. It counts steps and reproduces the table in Catastrophic backtracking. The j2 != j test inside loop stops a star from repeating a body that matched the empty string, which would otherwise recurse forever on (a*)*: a classic bug in hand-written backtrackers.
"""A backtracking matcher for the same syntax, for contrast.
It parses to a tree and tries one choice at a time, backing up on failure,
the way PCRE, Java, Python's re and JavaScript do. It counts its steps.
"""
def parse(p: str):
"""Same grammar as the Thompson engine, but returns a tree of tuples."""
i = 0
def peek():
return p[i] if i < len(p) else None
def alt():
nonlocal i
node = concat()
while peek() == "|":
i += 1
node = ("alt", node, concat())
return node
def concat():
parts = []
while peek() not in (None, "|", ")"):
parts.append(repeat())
return ("cat", parts)
def repeat():
nonlocal i
node = atom()
while peek() in ("*", "+", "?"):
node = ({"*": "star", "+": "plus", "?": "opt"}[p[i]], node)
i += 1
return node
def atom():
nonlocal i
c = peek()
if c is None or c in "*+?":
raise ValueError(f"expected an atom at {i}")
i += 1
if c == "(":
node = alt()
if peek() != ")":
raise ValueError("missing )")
i += 1
return node
if c == "\\":
c = p[i]
i += 1
return ("char", c)
return ("any",) if c == "." else ("char", c)
tree = alt()
if i != len(p):
raise ValueError(f"unexpected {p[i]!r} at {i}")
return tree
def backtrack_match(pattern: str, text: str) -> tuple[bool, int]:
"""Full match by backtracking. Returns (matched, steps)."""
tree, n, steps = parse(pattern), len(text), 0
def m(node, i, k):
"""Try to match `node` at text[i:], then call continuation k(j)."""
nonlocal steps
steps += 1
kind = node[0]
if kind == "char":
return i < n and text[i] == node[1] and k(i + 1)
if kind == "any":
return i < n and k(i + 1)
if kind == "cat":
def run(idx, j):
if idx == len(node[1]):
return k(j)
return m(node[1][idx], j, lambda j2: run(idx + 1, j2))
return run(0, i)
if kind == "alt": # left branch first, then right
return m(node[1], i, k) or m(node[2], i, k)
if kind == "opt": # greedy: try the body first
return m(node[1], i, k) or k(i)
body = node[1]
def loop(j): # greedy: one more, else stop
again = m(body, j, lambda j2: j2 != j and loop(j2))
return again or k(j)
if kind == "star":
return loop(i)
return m(body, i, loop) # plus: one body, then a star
return bool(m(tree, 0, lambda j: j == n)), steps
if __name__ == "__main__":
import random, re
assert backtrack_match("(a|b)*abb", "babb")[0]
assert not backtrack_match("(a|b)*abb", "abab")[0]
rng = random.Random(7)
for _ in range(20000): # agrees with re.fullmatch
p = "".join(rng.choice(["a", "b", ".", "a*", "(a|b)", "(ab)+", "b?", "(a|.)*"])
for _ in range(rng.randint(1, 4)))
s = "".join(rng.choice("ab") for _ in range(rng.randint(0, 7)))
assert backtrack_match(p, s)[0] == bool(re.fullmatch(p, s)), (p, s)
print(" n steps for (a+)+ on a^n b ratio")
prev = None
for n in range(10, 21, 2):
ok, steps = backtrack_match("(a+)+", "a" * n + "b")
assert not ok
print(f"{n:2d} {steps:>12,} {'' if prev is None else f'{steps / prev:.2f}'}")
prev = steps
Lab: subset construction, minimisation and a lazy DFA (Python)
Save the engine above as tiny_regex.py next to this file. This produces the blowup table and the lazy-DFA timing quoted earlier.
"""Subset construction, minimisation and a lazy DFA, on top of tiny_regex.py."""
import random
import time
from tiny_regex import closure, compile_regex, full_match, step
def subset_construction(nfa, alphabet):
"""Eager NFA -> DFA. Each DFA state is a frozenset of NFA states."""
start = frozenset(closure(nfa, [nfa.start]))
index, delta, todo = {start: 0}, {}, [start]
while todo:
S = todo.pop()
for c in alphabet:
T = frozenset(step(nfa, S, c))
if T not in index:
index[T] = len(index)
todo.append(T)
delta[index[S], c] = index[T]
accepting = {i for S, i in index.items() if nfa.accept in S}
return len(index), delta, accepting
def minimize(n, delta, accepting, alphabet):
"""Moore's partition refinement: split blocks until no letter separates
two states of the same block. Returns the number of blocks."""
block = [int(s in accepting) for s in range(n)]
while True:
signature = [(block[s],) + tuple(block[delta[s, c]] for c in alphabet)
for s in range(n)]
ids = {}
new_block = [ids.setdefault(sig, len(ids)) for sig in signature]
if len(ids) == len(set(block)):
return len(ids)
block = new_block
class LazyDFA:
"""Builds DFA states only when the text reaches them, and caches them."""
def __init__(self, nfa):
self.nfa = nfa
self.start = frozenset(closure(nfa, [nfa.start]))
self.cache = {} # (state set, char) -> state set
def full_match(self, text):
S = self.start
for ch in text:
key = (S, ch)
T = self.cache.get(key)
if T is None: # first visit: one NFA step
T = self.cache[key] = frozenset(step(self.nfa, S, ch))
S = T
return self.nfa.accept in S
if __name__ == "__main__":
print(" k NFA states subset DFA minimal DFA 2^(k+1)")
for k in range(0, 11):
nfa = compile_regex("(a|b)*a" + "(a|b)" * k)
n, delta, acc = subset_construction(nfa, "ab")
m = minimize(n, delta, acc, "ab")
assert m == 2 ** (k + 1)
print(f"{k:2d} {len(nfa.label):10d} {n:10d} {m:11d} {2 ** (k + 1):7d}")
nfa = compile_regex("(a|b)*abb")
n, delta, acc = subset_construction(nfa, "ab")
assert (n, minimize(n, delta, acc, "ab")) == (5, 4)
rng = random.Random(42)
text = "".join(rng.choice("ab") for _ in range(200_000))
nfa = compile_regex("(a|b)*a" + "(a|b)" * 10)
lazy = LazyDFA(nfa)
t0 = time.perf_counter()
r1 = full_match(nfa, text)
t1 = time.perf_counter()
r2 = lazy.full_match(text)
t2 = time.perf_counter()
assert r1 == r2 == (text[-11] == "a")
print(f"NFA simulation: {t1 - t0:.2f} s; lazy DFA: {t2 - t1:.2f} s; "
f"DFA states built: {len(set(lazy.cache.values()))} of 2048 possible")
Real-world uses
grepand its descendants. Thompson put regex search into the QED andededitors, andgrepgrew out ofed'sg/re/pcommand. GNU grep compiles patterns to a DFA (itsdfa.cbuilds states lazily) and falls back to the slower general matcher only when a pattern uses backreferences. ripgrep uses Rust'sregexcrate (lazy DFA, plus SIMD literal search when the pattern contains a required literal).- RE2 at Google. Built by Russ Cox for Google Code Search, where users typed arbitrary regexes to search a huge code corpus: a backtracking engine would have been a denial-of-service waiting to happen. RE2 is now used across Google and has bindings or ports for Python (
google-re2), Java (RE2/J) and many other languages; Go'sregexppackage follows the same design. Cloudflare's 2019 postmortem names RE2 and Rustregexas the replacements for their backtracking engine. - Lexers.
lex(1975) andflextake a list of token regexes, build one NFA for their union, convert it to a DFA, minimise it and emit the transition table as C code. Every compiler front end that uses them runs a DFA over the source file. - Search engines. Lucene's
RegexpQueryand fuzzy queries compile the pattern to an automaton and intersect it with the automaton of the term dictionary, so they never look at terms that cannot match. - Network security. Intrusion-detection systems such as Snort and Suricata match thousands of signatures against every packet. Intel's Hyperscan compiles large sets of regexes into combined automata (NFA and DFA parts, with SIMD acceleration) to do this at line rate, and Suricata can use it as its pattern matcher.
- Input validation and routing. Web frameworks match URLs and validate form fields with regexes on every request, which is exactly where ReDoS bites. The OWASP guidance on injection and input validation and secure-coding checklists (Secure Coding) treat untrusted regex input as an attack surface.
Pitfalls & edge cases
- Full match vs search.
re.matchanchors only at the start,re.fullmatchat both ends,re.searchat neither. Java'smatches()is full;find()is search. JavaScript'stestis search unless you add^…$. Most "my regex is wrong" bugs are really "I used the wrong one of these". - Empty loops.
(a*)*can loop forever without consuming input. The Thompson simulation is immune (a set cannot grow forever), but a backtracker must refuse to repeat a body that matched empty. - Precedence.
ab|cdis(ab)|(cd), nota(b|c)d.ab*isa(b*). When a generated pattern looks wrong, print the parse tree. - Escaping. In most languages the pattern goes through two parsers: the string literal, then the regex.
"\\*"in Java/C++/TS source is the two characters\*, which the regex reads as a literal star. Raw strings (r"\*"in Python,R"(\*)"in C++) avoid one layer. - Characters vs bytes. Our engines iterate over UTF-16 code units (Java), bytes (C++) or code points (Python, TypeScript's
for…of)..against an emoji matches one character in Python and two in Java. Real engines (RE2, Rust) compile UTF-8 into the automaton itself, so.becomes a small byte-level sub-automaton. - Set duplicates. Forgetting the "already in the set?" check makes the simulation exponential again, because the same state is added once per path that reaches it.
- Deep recursion. A recursive ε-closure or a recursive backtracker can overflow the stack on long patterns or texts. Use an explicit stack, as the engines above do for closure.
- Bounded repetition multiplies size.
x{1000}expands to 1,000 copies ofx's NFA, and(x{100}){100}to 10,000. Real engines cap the compiled size (RE2's default program size limit, Rust'ssize_limit) and return an error rather than run out of memory. - "Regex" features that are not regular (backreferences, lookaround, recursion) silently force your engine into backtracking mode, or are rejected by linear engines. If you need both features and safety, check the input length first.
Variations
- Leftmost-longest (POSIX) semantics. POSIX
regcomp/regexecmust report the longest match at the leftmost position, and specific submatch rules on top. Getting submatches right under POSIX rules is notoriously subtle; Laurikari's tagged NFAs/DFAs (TRE library, 2000) are one principled approach. - Glushkov (position) automaton. An ε-free NFA with exactly one state per symbol occurrence plus one start state ( states). Its regular structure is perfect for bit-parallel simulation (Shift-And/Shift-Or, Baeza-Yates and Gonnet 1992; Navarro and Raffinot's nrgrep), where the whole state set lives in one machine word and a step is a shift and an AND.
- Brzozowski derivatives (1964). The derivative of a regex by symbol is a regex for . Repeatedly differentiating builds a DFA directly from the regex, with no NFA. .NET's
NonBacktrackingengine is built on (symbolic) derivatives. - One-pass regexes. If at every point at most one thread can survive, a single-thread DFA can also track captures. RE2 and Go detect this and use a faster "one-pass" matcher.
- Aho–Corasick as a regex special case. A big alternation of literal strings,
w1|w2|…|wk, has a DFA that is exactly the Aho–Corasick automaton. Engines detect literal alternations and hand them to Aho–Corasick or SIMD algorithms (Rust's "Teddy"). - Approximate regex matching. Allow up to edits: Wu and Manber's
agrepcombined bit-parallel NFAs with edit-distance layers, one per allowed error (String DP explains the edit-distance part). - Counting matches. "How many strings of length does this regex match?" Build the DFA, then count paths of length from the start to accepting states, by DP over lengths or matrix exponentiation for huge . You must use a DFA here: counting NFA paths would count one string several times.
Practice ladder
Each problem is described in my own words; follow the link for the full statement.
1. String to Integer (atoi) (LeetCode 8) — Parse an optional sign and digits after leading spaces, clamping to 32 bits. Teaches thinking in states.
Hint
Draw four states: leading spaces, sign seen, in digits, done. Each character class (space, sign, digit, other) moves you along one arrow or stops. That is a DFA with an output.
2. Valid Number (LeetCode 65) — Decide whether a string is a decimal or integer, optionally with an exponent. Teaches building a DFA by hand.
Solution
Classify each character as digit, sign, e/E, . or other, and walk an 8-state table. States 2 (digits), 4 (digits after a dot, or a dot after digits) and 7 (exponent digits) accept.
def is_number(s):
def cls(c):
if c.isdigit(): return "d"
if c in "+-": return "s"
if c in "eE": return "e"
if c == ".": return "."
return "x"
T = {0: {"d": 2, "s": 1, ".": 3}, 1: {"d": 2, ".": 3},
2: {"d": 2, ".": 4, "e": 5}, 3: {"d": 4},
4: {"d": 4, "e": 5}, 5: {"d": 7, "s": 6},
6: {"d": 7}, 7: {"d": 7}}
state = 0
for c in s:
state = T[state].get(cls(c))
if state is None:
return False
return state in (2, 4, 7)
Tested on 2, 0089, -0.1, 4., -.9, 2e10, 3e+7, -123.456e789 (all valid) and abc, 1e, e3, 99e2.5, --6, ., .e1 (all invalid). It is the hand-minimised DFA for the regex [+-]?(\d+\.?\d*|\.\d+)([eE][+-]?\d+)?.
3. Design Add and Search Words Data Structure (LeetCode 211) — Store words; search patterns where . matches any letter. Teaches "the set of states" over a trie.
Hint
Keep a set of trie nodes. For a letter, move each node to its child; for ., to all children. The answer is whether any final node ends a word. That is NFA simulation where the automaton is a trie.
4. Wildcard Matching (LeetCode 44) — ? is any one character, * any run. Teaches translating one pattern language into another.
Solution
Translate to our syntax and reuse the engine: ? becomes ., * becomes .*. Linear-size NFA, time.
from tiny_regex import matches
def is_match(s: str, p: str) -> bool:
return matches("".join(".*" if c == "*" else "." if c == "?" else c for c in p), s)
Checked: adceb vs *a*b true, acdcb vs a*c?b false, empty vs *** true. The DP version and the greedy two-pointer are in String DP.
5. Regular Expression Matching (LeetCode 10) — . and * with full-match semantics. Teaches that the classic DP is NFA simulation.
Solution
LeetCode's dialect is a subset of ours (letters, ., x*), so matches(p, s) from the engine solves it as is, in . In an interview, also be ready to write the DP from String DP and to explain that its rows are the NFA's state sets. Checked: aab vs c*a*b true, mississippi vs mis*is*p*. false, aa vs a false.
6. Parsing A Boolean Expression (LeetCode 1106) — Evaluate nested &(…), |(…), !(…). Teaches the recursive-descent skeleton our regex parser uses.
Solution
def parse_bool_expr(expression: str) -> bool:
pos = 0
def expr():
nonlocal pos
c = expression[pos]; pos += 1
if c in "tf":
return c == "t"
pos += 1 # skip '('
vals = [expr()]
while expression[pos] == ",":
pos += 1
vals.append(expr())
pos += 1 # skip ')'
return (not vals[0]) if c == "!" else all(vals) if c == "&" else any(vals)
return expr()
&(|(f)) → false, |(f,f,f,t) → true, !(&(f,t)) → true. Same pattern as Parser.atom: a shared position, one function per grammar rule.
7. Brace Expansion II (LeetCode 1096) — Expand a grammar of union ({a,b}) and concatenation into the sorted set of words. Teaches the union/concat precedence of regular expressions on a finite language.
Hint
Same three-level grammar as regexes, minus the star: alt := concat (',' concat)*, concat := atom*, atom := letter | '{' alt '}'. Return sets of strings; concatenation is the Cartesian product.
8. Stream of Characters (LeetCode 1032) — After each streamed letter, report whether some word ends here. Teaches a DFA over a stream.
Hint
The pattern is .*(w1|w2|…|wk) searched over a stream. Build the Aho–Corasick automaton (the DFA of that regex) and advance one state per letter; or, simpler, a trie of reversed words walked backwards over the last maxLen letters.
9. Count Strings (HackerRank) — Given a fully parenthesised regex over a, b and a length up to , count matching strings of length modulo . Teaches the whole pipeline: regex → NFA → DFA → counting.
Solution
Build the Thompson NFA, run the subset construction over , make the DFA's transition-count matrix , and compute by fast exponentiation. The answer is the sum of row "start" over accepting columns. A DFA is essential: in an NFA, one string can follow several paths and would be counted several times.
from tiny_regex import compile_regex, closure, step
MOD = 10**9 + 7
def count_strings(regex: str, length: int) -> int:
nfa = compile_regex(regex)
start = frozenset(closure(nfa, [nfa.start]))
index, todo, edges = {start: 0}, [start], []
while todo:
S = todo.pop()
for c in "ab":
T = frozenset(step(nfa, S, c))
if T not in index:
index[T] = len(index)
todo.append(T)
edges.append((index[S], index[T]))
n = len(index)
M = [[0] * n for _ in range(n)]
for u, v in edges:
M[u][v] += 1
def mul(A, B):
return [[sum(A[i][k] * B[k][j] for k in range(n)) % MOD for j in range(n)]
for i in range(n)]
R = [[int(i == j) for j in range(n)] for i in range(n)]
while length:
if length & 1:
R = mul(R, M)
M = mul(M, M)
length >>= 1
return sum(R[0][index[S]] for S in index if nfa.accept in S) % MOD
The samples ((ab)|(ba)), 2 → 2; ((a|b)*), 5 → 32; ((a*)(b(a*))), 100 → 100 pass, and the function agrees with brute-force enumeration for five patterns and every . The DFA is small for these inputs; the matrix power is for DFA states.
10. Build-it challenge (no judge): add character classes and anchors. Extend the engine with [abc], [a-z], [^…] and the search-mode ^/$. Character classes become one labelled arrow with a set label (test membership in step). Anchors are conditions on the position, checked when computing the closure. Test against your language's regex library the same way the main functions do.
Common mistakes & interview follow-ups
"How does a regex engine work?" Parse, compile to an automaton (Thompson's construction: states), then either backtrack through it (most standard libraries) or simulate all paths at once (, RE2/Go/Rust), optionally caching the sets as DFA states.
"Why is (a+)+$ slow in Python but not in Go?" Python's re backtracks and tries all ways to split the as before failing. Go's regexp simulates the NFA with a set of states, so each character costs at most the number of states.
"Then why don't Python and Java switch?" Backreferences and lookaround, which their users rely on, cannot be done by automata (backreferences make matching NP-hard: Aho 1990), and changing match semantics would break existing code. They add atomic groups, possessive quantifiers and limits instead; .NET added an opt-in automaton engine.
"NFA to DFA: how big can the DFA get?" Up to states, and really needs . Hence lazy DFAs.
"Can a regex match balanced parentheses / check that a string is a palindrome?" Not a true regular expression (pumping lemma). PCRE's recursion (?R) can, because PCRE patterns are not regular expressions in the formal sense.
"Implement . and * matching." Write the DP or the NFA simulation, not plain recursion without memoization, and say why: plain recursion explores every way of sharing the as among the stars of a*a*a*a*a*a*b against thirty as (about ways for stars), and nested quantifiers make it exponential.
Mistakes interviewers watch for: confusing "NFA engine" (marketing for backtracking) with NFA simulation; forgetting the ε-closure of the start state; adding a state twice to the set; claiming DFA construction is always cheap; saying "regexes can't be slow if they're short"; using match when fullmatch was needed.
Quick quiz
1. How many states does our Thompson construction create for a|b? For a*?
Answer
a|b: 2 + 2 for the symbols plus 2 for the alternation = 6. a*: 2 + 2 = 4. (The program's state dump confirms both.)
2. After reading ba from the start of (a|b)*abb, which DFA state are you in, and what does it mean?
Answer
D0 →b→ D2 →a→ D1: "the text currently ends in a", that is, one letter of abb seen.
3. Why does the minimal DFA for need 16 states, not 4?
Answer
It must remember the last 4 letters ( possibilities), because any two different 4-letter memories can be told apart by appending the right number of letters. The 4th letter from the end is not known to be "the" one until the input ends.
4. The toy backtracker takes 4,097 steps on (a+)+ against . Roughly how many on ?
Answer
: the count is , doubling with each extra a.
5. Stack Overflow's regex was not exponential. What was its complexity on a line of spaces followed by other text, and why?
Answer
Quadratic, about steps: an unanchored search tries each of the start positions, and from each one the [\s]+ part consumes all the remaining spaces before $ fails.
6. True or false: Go's regexp package builds a DFA.
Answer
False. It uses a Pike VM (NFA simulation), a one-pass matcher and a bounded backtracker, all linear-time; RE2 (C++) and Rust's regex add a lazy DFA.
Further reading / sources
- Ken Thompson, "Programming Techniques: Regular expression search algorithm", Communications of the ACM 11(6), 1968, pp. 419–422. The construction and the simulation.
- Stephen C. Kleene, "Representation of events in nerve nets and finite automata", in Automata Studies, Princeton, 1956. Regular expressions = finite automata.
- Michael O. Rabin, Dana Scott, "Finite automata and their decision problems", IBM Journal of Research and Development 3(2), 1959. NFAs and the subset construction.
- John Hopcroft, "An n log n algorithm for minimizing states in a finite automaton", in Theory of Machines and Computations, Academic Press, 1971.
- Alfred V. Aho, "Algorithms for finding patterns in strings", in J. van Leeuwen (ed.), Handbook of Theoretical Computer Science, vol. A, ch. 5, Elsevier/MIT Press, 1990. Includes the NP-completeness of matching with backreferences.
- Russ Cox, "Regular Expression Matching Can Be Simple And Fast" (2007), "Regular Expression Matching: the Virtual Machine Approach" (2009) and "Regular Expression Matching in the Wild" (2010), at swtch.com/~rsc/regexp/. The clearest modern account, including RE2's design.
- Alfred V. Aho, Monica S. Lam, Ravi Sethi, Jeffrey D. Ullman, Compilers: Principles, Techniques, and Tools, 2nd ed., 2006, §3.6–3.9 (Thompson's construction, subset construction, minimisation, lexer generators).
- Michael Sipser, Introduction to the Theory of Computation, 3rd ed., ch. 1 (regular languages, the pumping lemma).
- Jeffrey E. F. Friedl, Mastering Regular Expressions, 3rd ed., O'Reilly, 2006. The backtracking engine's view, including the "NFA vs DFA" terminology discussed above.
- Stack Exchange, "Outage Postmortem – July 20, 2016", stackstatus.net (post 147710624694).
- John Graham-Cumming, "Details of the Cloudflare outage on July 2, 2019", blog.cloudflare.com, 12 July 2019.
- James C. Davis, Christy A. Coghlan, Francisco Servant, Dongyoon Lee, "The impact of regular expression denial of service (ReDoS) in practice: an empirical study at the ecosystem scale", ESEC/FSE 2018.
- Stephen Toub, "Regular Expression Improvements in .NET 7", .NET Blog, 2022 (the
NonBacktrackingengine). V8 team, "An additional non-backtracking RegExp engine", v8.dev, 2021. - Ville Laurikari, "NFAs with tagged transitions, their conversion to deterministic automata and application to regular expressions", SPIRE 2000.
Previous lesson: Minimal Rotation, Lyndon Words & Booth's Algorithm · Next: Module 7 Capstone
Related: String Algorithms overview · Regex Mastery · String DP · Aho–Corasick · KMP · Backtracking & Recursion · BFS · Course home