Lesson 1.2 — Running automata: backtracking, NFA simulation, subset construction, lazy DFAs¶

Techniques: backtracking search (the baseline), Thompson's NFA simulation and the Pike VM, the subset (powerset) construction, the lazy (on-the-fly) DFA of RE2 and GNU grep · Pebble implements: all four in the regex lab (PikeVM, DFA, ★ LazyDFA back ends; backtracking only as the comparison baseline std::regex) · Prerequisites: Lesson 1.1 · Time: 5–7 hours

Lesson 1.1 turned \(r_0 = (a \mid b)^{*}abb\) into an 11-state ε-NFA. An NFA is not a program: at state 0 on input a it may go several ways. This lesson covers the four ways to run one. Backtracking tries one path and retreats on failure: simple, but exponential. Simulation follows all paths at once as a set of states: linear in the input. The subset construction precomputes every set the simulation can reach: one table lookup per byte, at the cost of possibly exponentially many states. The lazy DFA computes only the sets the input actually visits and caches them. Pebble's hand-written lexer is a DFA written by hand; the lab builds all of these mechanically and races them.

1. Problem and motivation¶

Given an ε-NFA \(N\) (or a regex \(r\)) and an input \(w\), decide whether \(w \in L(N)\), or find the longest prefix of \(w\) in \(L(N)\), which is what a lexer needs (Lesson 1.6). The engine runs on every byte of every source file, so it must be linear in \(\lvert w \rvert\) with a small constant.

Backtracking¶

The most direct implementation walks the regex (or the NFA) depth-first: at a choice (an alternative or a star) take the first option and, if the rest fails, come back and try the next. Henry Spencer's regex library, Perl, PCRE, Python's re, Java's java.util.regex and libstdc++'s std::regex work this way, because backtracking handles backreferences and reports the "leftmost-first" submatches programmers expect. Its worst case is exponential, which Cox's articles made widely known [Cox07]; we cover it as the baseline every automaton method beats.

Thompson NFA simulation (Pike VM)¶

Thompson's 1968 paper [Tho68] already avoided backtracking: keep the set of NFA states that some path could be in after reading each prefix, and advance all of them together. Pike extended the simulation to track submatch positions per thread in the sam editor [Pik87]; Cox's description of this "Pike VM" [Cox09] is the model for RE2, Go and Rust's regex. Linear time in the input, for any regular expression.

Subset construction¶

Rabin and Scott [RS59] showed that nondeterminism adds no power: the sets of NFA states reachable by the simulation are themselves the states of a DFA. Precomputing them gives one table lookup per input byte, the fastest possible inner loop. flex, re2c, and every table-driven lexer run a subset construction at build time [Dragon2 §3.7.1].

Lazy DFA (RE2)¶

The subset construction can blow up exponentially (Proposition 1.2.11), and a search engine compiles a new pattern for every query, so building the whole DFA is often wasteful. A lazy DFA builds a state the first time the input reaches it and caches it; when the cache is full it is flushed. The technique goes back to Unix egrep [Aho90 §3] and is the core of GNU grep (lib/dfa.c) and RE2 [RE2-DFA, Cox10].

2. Definitions and algorithms¶

Definition 1.2.1 (Membership and longest-prefix problems)

For a language \(L \subseteq \Sigma^{*}\) and an input \(w = a_1 \cdots a_n\): the membership problem asks whether \(w \in L\); the longest-prefix problem asks for \(\max \{\, i \mid a_1 \cdots a_i \in L \,\}\), or "none" if no prefix (not even ε) is in \(L\). The lab's Matcher::matches and Matcher::longestPrefix are these two problems (labs/ch01-regex/include/regexlab/Regex.h).

Definition 1.2.2 (Run, configuration)

A configuration of an ε-NFA \(N\) on \(w\) is a pair \((q, i)\): state \(q\) after consuming \(a_1 \cdots a_i\). \((p, i) \vdash (q, i)\) if \((p, \varepsilon, q) \in \Delta\), and \((p, i) \vdash (q, i + 1)\) if \((p, a_{i+1}, q) \in \Delta\). \(w \in L(N)\) iff \((q_0, 0) \vdash^{*} (f, n)\) for some \(f \in F\).

Backtracking¶

Algorithm 1.2.3 (Backtracking search over configurations)

Input: ε-NFA \(N\), word \(w\) of length \(n\).
Output: whether \(w \in L(N)\).
Precondition: out-edges of every state are in a fixed order (the regex's "preferred" order).
Postcondition: returns true iff some run reaches \((f, n)\) with \(f \in F\) (Proposition 1.2.7).
Invariant: OnPath holds the configurations of the current recursion stack that were reached through ε-edges only since the last symbol; a configuration is never on the stack twice (so ε-cycles cannot loop).

function Backtrack(q, i, OnPath):
    if i = n and q ∈ F: return true
    if (q, i) ∈ OnPath: return false           # an ε-cycle: this branch adds nothing
    for (label, t) in edges(q) in order:
        if label = ε:
            if Backtrack(t, i, OnPath ∪ {(q, i)}): return true
        else if i < n and a_{i+1} ∈ label:
            if Backtrack(t, i + 1, {}): return true
    return false

function Matches(N, w): return Backtrack(q0, 0, {})

Production engines backtrack over the regex syntax tree or a bytecode instead of the NFA, and add a memo of failed configurations only in special cases (Go's "bit-state" backtracker does memoize, which makes it linear; Perl, PCRE, Python and std::regex do not).

Backtracking vs automata in GNU grep

Reproduce (GNU grep 3.11 with PCRE2 10.42; Linux):

python3 -c "print('a' * 30)" > a30.txt
grep -cP '^(a?){30}a{30}$' a30.txt; echo "exit=$?"
grep -cE '^(a?){30}a{30}$' a30.txt; echo "exit=$?"

Output (complete):

grep: a30.txt: exceeded PCRE's backtracking limit
exit=2
1
exit=0

What to notice: the same pattern, the same 30-byte line. -P uses PCRE2, a backtracking engine: \((a?)^{30}\) offers \(2^{30}\) ways to split the input and PCRE2 gives up at its step limit (Proposition 1.2.13). -E uses gnulib's DFA matcher (positions + lazy DFA, Lesson 1.1 §7) and answers at once. PCRE's defense is a limit, not an algorithm.

Thompson NFA simulation (Pike VM)¶

Algorithm 1.2.4 (Thompson's simulation)

Input: ε-NFA \(N\) with states numbered \(0..s-1\); word \(w = a_1 \cdots a_n\).
Output: whether \(w \in L(N)\), and the longest accepted prefix length.
Precondition: none.
Postcondition: accept \(\iff w \in L(N)\); last = the longest-prefix answer of Definition 1.2.1 (Theorem 1.2.9).
Invariant: before step \(i\) (\(0 \le i \le n\)), \(S = \hat\Delta(a_1 \cdots a_i)\) (Lemma 1.2.8).

function Closure(T):                      # ε-closure; T is a list of states
    S ← empty set;  stack ← T (reversed, so T[0] is explored first)
    while stack not empty:
        q ← pop(stack)
        if q ∉ S:
            add q to S
            for (ε, t) in edges(q), in reverse order: push(stack, t)
    return S

function Simulate(N, w):
    S ← Closure([q0]);  last ← (0 if S ∩ F ≠ ∅ else none)
    for i from 1 to n:
        T ← [ t | q in S, (label, t) in edges(q), label ≠ ε, a_i ∈ label ]
        S ← Closure(T)
        if S = ∅: break                   # no path survives: stop early
        if S ∩ F ≠ ∅: last ← i
    return (last = n, last)

Set \(S\) is a sparse set (a dense array of members plus an index array) so membership, insertion and clearing are \(O(1)\); the lab's solution uses a mark array with the same effect. In the Pike VM, each member of \(S\) is a thread that also carries submatch positions; the order in which threads are added encodes regex priority, so the first thread to reach Match is the leftmost-first match.

An NFA simulation inside LLVM: llvm::Regex

Reproduce (clang 23.1.2, LLVM 23.1.2 with its llvm-config first on PATH, e.g. /opt/llvm-23/bin; on macOS drop --gcc-install-dir):

cat > llregex.cpp <<'EOF'
#include "llvm/Support/Regex.h"
#include "llvm/Support/raw_ostream.h"
#include <string>

int main() {
  for (unsigned N : {10u, 20u, 30u}) {
    std::string Pat = "^(a?){" + std::to_string(N) + "}a{" + std::to_string(N) + "}$";
    llvm::Regex R(Pat);
    std::string Text(N, 'a');
    llvm::outs() << Pat << " on a^" << N << ": " << (R.match(Text) ? "match" : "no match") << "\n";
  }
  llvm::Regex Back("^(a+)b\\1$");
  llvm::outs() << "^(a+)b\\1$ on aabaa: " << (Back.match("aabaa") ? "match" : "no match") << "\n";
}
EOF
clang++-23 --gcc-install-dir=/usr/lib/gcc/x86_64-linux-gnu/14 $(llvm-config --cxxflags) llregex.cpp \
  $(llvm-config --ldflags --libs support) -Wl,-rpath,$(llvm-config --libdir) -o llregex
./llregex

Output (complete; the program finishes in about 10 ms):

^(a?){10}a{10}$ on a^10: match
^(a?){20}a{20}$ on a^20: match
^(a?){30}a{30}$ on a^30: match
^(a+)b\1$ on aabaa: match

What to notice: llvm::Regex (the regex FileCheck uses) is Henry Spencer's POSIX library. Its matchers smatcher/lmatcher (llvm/lib/Support/regengine.inc, function step) advance a set of states per input character: Algorithm 1.2.4, with the set stored as the bits of a long when the program has at most 64 states. Only a pattern with a backreference (the last line) makes it call backref, its backtracking fallback.

Subset construction¶

Algorithm 1.2.5 (Subset construction, Rabin–Scott)

Input: ε-NFA \(N = (Q, \Sigma, \Delta, q_0, F)\).
Output: DFA \(D = (Q_D, \Sigma, \delta_D, A, F_D)\) with \(Q_D \subseteq \mathcal{P}(Q)\).
Precondition: \(\Sigma\) is given as a list of symbol classes such that every edge label is a union of classes (then one representative per class suffices).
Postcondition: \(L(D) = L(N)\) (Theorem 1.2.10); \(Q_D\) contains exactly the nonempty sets \(\hat\Delta(w)\) for \(w \in \Sigma^{*}\).
Invariant: every set in \(Q_D\) is \(\hat\Delta(w)\) for some \(w\); every set in \(Q_D\) not on the worklist has all its transitions in \(\delta_D\).

function SubsetConstruction(N, classes):
    A ← Closure([q0]);  Q_D ← [A];  work ← queue [A]
    while work not empty:
        T ← dequeue(work)
        for c in classes (in order):
            U ← Closure(move(T, representative(c)))
            if U = ∅: δ_D(T, c) ← undefined        # the implicit dead state
            else:
                if U ∉ Q_D: append U to Q_D; enqueue(work, U)   # new DFA state
                δ_D(T, c) ← U
    F_D ← { T ∈ Q_D | T ∩ F ≠ ∅ }
    return (Q_D, classes, δ_D, A, F_D)

function move(T, a): return [ t | q in T, (label, t) in edges(q), label ≠ ε, a ∈ label ]
function SymbolClasses(labels):        # coarsest partition of Σ refining every label
    P ← [Σ]
    for L in labels: P ← [ B ∩ L, B ∖ L for B in P, dropping empty sets ]
    return P

Sets are compared as sorted vectors (or hashed bit sets); Q_D is a hash map from set to DFA state number. Naming convention (drills and lessons): DFA states are named A, B, C, … in the order they are appended to Q_D.

flex shows its NFA, its subset-constructed DFA and its byte classes

Reproduce (flex 2.6.4; any OS):

cat > abb.l <<'EOF'
%option noyywrap nodefault
%%
(a|b)*abb   { return 1; }
.|\n        { return 2; }
%%
EOF
flex -T -o abb.c abb.l 2>&1 | sed -n '/DFA Dump/,/state # 10 accepts/p'

Output (complete for the DFA part; the NFA dump and the 256-entry class table that precede and follow it are cut):

DFA Dump:

state # 1:
    1   4
    2   4
    3   5
    4   6
state # 2:
    1   4
    2   4
    3   5
    4   6
state # 3:
state # 4:
state # 5:
    3   7
    4   8
state # 6:
    3   7
    4   9
state # 7:
    3   7
    4   8
state # 8:
    3   7
    4   10
state # 9:
    3   7
    4   9
state # 10:
    3   7
    4   9
state # 3 accepts: [4]
state # 4 accepts: [2]
state # 5 accepts: [2]
state # 6 accepts: [2]
state # 10 accepts: [1]

What to notice: each line c t is "on class \(c\) go to state \(t\)". flex computed four equivalence classes (its table, cut here, maps a to 3, b to 4, \n to 2 and every other byte to 1): the SymbolClasses step. States 7, 8, 9 and 10 are the subset construction of \((a|b)^{*}abb\) after at least two characters: 7, 8, 9, 10 play the roles of B, D, C, E in §3, and only 10 accepts rule 1. States 1 and 2 are identical: flex makes two start states per start condition (one for the beginning of a line) and never merges them, because it has no minimization pass (ntod in src/dfa.c is the subset construction, and that is all) [FLEX-DFA].

Lazy DFA (RE2)¶

Algorithm 1.2.6 (Lazy DFA with a bounded cache)

Input: ε-NFA \(N\), symbol classes, input \(w\), cache capacity \(C \ge 2\) states.
Output: the same as Algorithm 1.2.4.
Precondition: as for Algorithm 1.2.5.
Postcondition: as for Algorithm 1.2.4 (Proposition 1.2.12).
Invariant: every cached state is a pair (set \(\hat\Delta(u)\) for some \(u\), partial transition row); a filled entry row[c] = U means \(U = \mathrm{Closure}(\mathrm{move}(T, c))\). The current state is always in the cache.

function Intern(set):                      # find or add a cache state
    if set ∈ index: return index[set]
    s ← new state {set, row ← all "unknown", accepting ← set ∩ F ≠ ∅}
    index[set] ← s;  return s

function Step(s, c):
    if s.row[c] ≠ unknown: return s.row[c]           # hit: O(1)
    U ← Closure(move(s.set, representative(c)))       # miss: one NFA step
    if |cache| ≥ C:
        clear index and every state; return Intern(U)  # flush, keep going
    t ← Intern(U);  s.row[c] ← t;  return t

function LazyMatch(N, w):
    s ← Intern(Closure([q0]));  last ← (0 if s.accepting else none)
    for i from 1 to n:
        s ← Step(s, class(a_i))
        if s.set = ∅: break
        if s.accepting: last ← i
    return (last = n, last)

RE2 falls back to the NFA simulation if it has to flush too often (it counts bytes per state); the lab's ★ back end only flushes (solutions/labs/ch01-regex/src/Engines.cpp, LazyDfaMatcher).

RE2's lazy DFA: a memory budget and a cache reset

Reproduce (RE2 tag 2024-07-02; curl 8.5.0 and grep 3.11, any OS):

curl -sSfL https://raw.githubusercontent.com/google/re2/2024-07-02/re2/dfa.cc -o re2-dfa.cc
grep -n 'mem_budget_;\|state_budget_;\|^void DFA::RunWorkqOnByte\|^DFA::State\* DFA::RunStateOnByte(\|^void DFA::ResetCache\|DFA out of memory' re2-dfa.cc

Output (complete):

340:  int64_t mem_budget_;     // Total memory budget for all States.
341:  int64_t state_budget_;   // Amount of memory remaining for new States.
952:void DFA::RunWorkqOnByte(Workq* oldq, Workq* newq,
1024:DFA::State* DFA::RunStateOnByte(State* state, int c) {
1188:void DFA::ResetCache(RWLocker* cache_lock) {
2062:    if (ns == NULL)  // DFA out of memory
2071:      if (ns == NULL)  // DFA out of memory

What to notice: RunWorkqOnByte is move + Closure on a work queue of NFA instructions; RunStateOnByte is Step (it fills a transition the first time it is needed); ResetCache is the flush; mem_budget_ is \(C\) measured in bytes. When a state cannot be allocated even after a reset, RE2's search returns "DFA out of memory" and the caller falls back to the NFA.

3. Worked example¶

All traces run on the Thompson NFA of \(r_0\) from Lesson 1.1 §3 (states 0–10, accept 10) and were produced with the course oracle (tools/course/lib/regex.py).

Backtracking¶

On \(r = a?a?aa\) (the \(n = 2\) member of the pathological family) and \(w = aa\), trying "take the \(a\)" before "skip":

step	choice made	position after	outcome
1	1^st \(a?\) takes \(a\)	1	continue
2	2^nd \(a?\) takes \(a\)	2	continue
3	3^rd item \(a\) needs a symbol at 2	–	fail → back to step 2
4	2^nd \(a?\) skips	1	continue
5	\(a\) reads position 1	2	continue
6	last \(a\) needs a symbol at 2	–	fail → back to step 1
7	1^st \(a?\) skips	0	continue
8	2^nd \(a?\) takes \(a\)	1	continue
9	\(a\) reads position 1	2	continue
10	last \(a\) needs a symbol at 2	–	fail → back to step 8
11	2^nd \(a?\) skips	0	continue
12	\(a\), \(a\) read positions 0, 1	2	success

Three of the four choice combinations fail before the only good one (skip, skip) is tried: \(2^{n}\) combinations in general.

Thompson NFA simulation (Pike VM)¶

Simulation of \(r_0\) on \(w = aabb\):

step	read	move(S, symbol)	S = closure (after)	accepting?	last
init	–	–	{0, 1, 2, 4, 7}	no	none
1	a	{3, 8}	{1, 2, 3, 4, 6, 7, 8}	no	none
2	a	{3, 8}	{1, 2, 3, 4, 6, 7, 8}	no	none
3	b	{5, 9}	{1, 2, 4, 5, 6, 7, 9}	no	none
4	b	{5, 10}	{1, 2, 4, 5, 6, 7, 10}	yes	4

\(w \in L(r_0)\) and the longest accepted prefix is the whole word. Step 2 produced the same set as step 1: the simulation keeps rediscovering the same sets, which is what the subset construction exploits.

Subset construction¶

Worklist trace for \(r_0\) over classes \(a\), \(b\) (FIFO; symbols in order):

step	take	symbol	move then ε-closure	target	worklist after
0	–	–	\(E(\{0\})\) =	A (new)	A
1	A	a	{1, 2, 3, 4, 6, 7, 8}	B (new)	B
2	A	b	{1, 2, 4, 5, 6, 7}	C (new)	B C
3	B	a	{1, 2, 3, 4, 6, 7, 8}	B	C
4	B	b	{1, 2, 4, 5, 6, 7, 9}	D (new)	C D
5	C	a	{1, 2, 3, 4, 6, 7, 8}	B	D
6	C	b	{1, 2, 4, 5, 6, 7}	C	D
7	D	a	{1, 2, 3, 4, 6, 7, 8}	B	E
8	D	b	{1, 2, 4, 5, 6, 7, 10}	E (new)	E
9	E	a	{1, 2, 3, 4, 6, 7, 8}	B	(empty)
10	E	b	{1, 2, 4, 5, 6, 7}	C	(empty)

Result (Dragon Fig. 3.35): only E contains the NFA's accept state 10.

state	a	b	accepting
→ A	B	C
B	B	D
C	B	C
D	B	E
E	B	C	yes

flowchart LR
  A([A]) -->|a| B
  A -->|b| C
  B -->|a| B
  B -->|b| D
  C -->|a| B
  C -->|b| C
  D -->|a| B
  D -->|b| E(((E)))
  E -->|a| B
  E -->|b| C

Five DFA states for an 11-state NFA; the worst case would be \(2^{11}\). A and C have the same row and the same acceptance: they are equivalent, and Lesson 1.4 merges them.

Try it

./course drill subset-construction --seed 4 --difficulty medium, then --solution for the full worklist trace.

Lazy DFA (RE2)¶

Two searches with the same cache (capacity large enough), on inputs babb then abab. "State miss" means the set had to be computed and interned; "row miss" means the state existed but this transition had not been filled yet.

input	step	from	read	result	cache effect	states cached
`babb`	0	–	–	A	intern A	1
	1	A	b	C	row miss, state miss	2
	2	C	a	B	row miss, state miss	3
	3	B	b	D	row miss, state miss	4
	4	D	b	E (accept)	row miss, state miss	5
`abab`	1	A	a	B	row miss, state hit	5
	2	B	b	D	hit	5
	3	D	a	B	row miss, state hit	5
	4	B	b	D	hit	5

After two short inputs the cache holds the whole five-state DFA; a longer text would run entirely on hits. On the exponential family of Proposition 1.2.11 only the states the text actually visits are ever built: at most \(\lvert w \rvert + 1\) per search.

4. Invariants and correctness¶

Backtracking¶

Proposition 1.2.7 (Backtracking is correct and terminates)

Matches(N, w) returns true iff \(w \in L(N)\), and every call terminates.

Proof

Termination: along any branch of the recursion, the position \(i\) never decreases; between two increases the configurations on the ε-path are pairwise distinct because of the OnPath check, and there are at most \(\lvert Q \rvert\) of them. So every branch has length at most \((n + 1)\lvert Q \rvert\), and the recursion tree is finite. Soundness: a true result is produced only at \((f, n)\) with \(f \in F\), and the recursion stack is a run \((q_0, 0) \vdash^{*} (f, n)\). Completeness: suppose an accepting run exists; take one with no repeated configuration between consecutive symbol steps (cut out ε-cycles, which do not change the configuration sequence's endpoints). The search explores every out-edge of every configuration in order until one succeeds, and the OnPath check never blocks a configuration of this cycle-free run (it blocks only repetitions within one ε-segment), so by induction on the run's length the search reaches an accepting configuration or returns true earlier. \(\square\)

Thompson NFA simulation (Pike VM)¶

Lemma 1.2.8 (Simulation invariant)

In Algorithm 1.2.4, after the \(i\)-th iteration (and before the first, for \(i = 0\)), \(S = \hat\Delta(a_1 \cdots a_i)\) unless the loop has stopped early, in which case \(\hat\Delta(a_1 \cdots a_j) = \emptyset\) for all \(j \ge i\).

Proof

Initialization: Closure([q0]) returns the least set containing \(q_0\) closed under ε-edges: each popped state is added and its ε-successors pushed, and a state is added only if reachable by ε-edges from \(q_0\). That is \(E(\{q_0\}) = \hat\Delta(\varepsilon)\). Maintenance: \(T\) is \(\mathrm{move}(S, a_{i+1})\) by construction, so the new \(S\) is \(E(\mathrm{move}(\hat\Delta(a_1 \cdots a_i), a_{i+1})) = \hat\Delta(a_1 \cdots a_{i+1})\) (Definition 1.1.4). Early stop: if \(S = \emptyset\) then \(\mathrm{move}(\emptyset, a) = \emptyset\) for every \(a\), so every later set is empty too. \(\square\)

Theorem 1.2.9 (Correctness and cost of the simulation)

Simulate returns last = the longest-prefix answer and accept \(\iff w \in L(N)\), in \(O(\lvert Q \rvert + \lvert \Delta \rvert)\) time per input symbol.

Proof

By Lemma 1.2.8, \(S \cap F \neq \emptyset\) after step \(i\) iff \(a_1 \cdots a_i \in L(N)\); last records the largest such \(i\) (and is not updated after an early stop, correctly, since all later sets are empty). accept compares last with \(n\). Cost: each iteration adds each state to \(S\) at most once (the membership test), and scans each state's edges once, in move and in Closure: \(O(\lvert Q \rvert + \lvert \Delta \rvert)\). For a Thompson NFA \(\lvert \Delta \rvert \le 2 \lvert Q \rvert \le 4 \lvert r \rvert\), so the cost is \(O(\lvert r \rvert)\) per symbol. \(\square\)

Subset construction¶

Theorem 1.2.10 (Rabin–Scott: the subset construction is correct)

Algorithm 1.2.5 terminates, and \(L(D) = L(N)\). Every state of \(D\) is reachable, and \(\hat\delta_D(A, w) = \hat\Delta(w)\) whenever \(\hat\Delta(w) \neq \emptyset\) (otherwise \(D\) falls into the implicit dead state).

Proof

Termination: each state enters Q_D (and the worklist) at most once, and Q_D \(\subseteq \mathcal{P}(Q)\) is finite; each dequeue does a bounded amount of work. Invariant (first half): \(A = \hat\Delta(\varepsilon)\), and each new \(U = E(\mathrm{move}(T, c))\) with \(T = \hat\Delta(u)\) equals \(\hat\Delta(uc)\) for any symbol of class \(c\): all symbols of a class belong to the same labels (precondition), so move is the same for each of them. Claim \(\hat\delta_D(A, w) = \hat\Delta(w)\): induction on \(\lvert w \rvert\) using the invariant for the step; when \(\hat\Delta(w) = \emptyset\) the transition was left undefined and every extension also has \(\hat\Delta = \emptyset\). Language: \(w \in L(D)\) iff \(\hat\delta_D(A, w) \in F_D\) iff \(\hat\Delta(w) \cap F \neq \emptyset\) iff \(w \in L(N)\). Reachability: every appended set was produced as a transition target. \(\square\)

Proposition 1.2.11 (The exponential blow-up is unavoidable)

For \(k \ge 1\), \(L_k = L((a \mid b)^{*} a (a \mid b)^{k-1})\) (the \(k\)-th symbol from the end is \(a\)) has a Thompson NFA with \(O(k)\) states, but every DFA for \(L_k\) has at least \(2^{k}\) states.

Proof

The NFA bound is Proposition 1.1.18. Suppose a DFA with fewer than \(2^{k}\) states recognizes \(L_k\). There are \(2^{k}\) words of length \(k\) over \(\{a, b\}\), so by pigeonhole two different ones, \(u \neq v\), reach the same state. Let position \(j\) (\(1 \le j \le k\)) be where they differ, say \(u_j = a\), \(v_j = b\). Append \(z = a^{j-1}\): in \(uz\) the \(k\)-th symbol from the end is \(u_j = a\), so \(uz \in L_k\); in \(vz\) it is \(v_j = b\), so \(vz \notin L_k\). But \(uz\) and \(vz\) end in the same state: contradiction. \(\square\)

The lab's benchmark prints the minimal DFA sizes of this family: \(2^{k+1} + 1\) over bytes for \((a|b)^{*}a(a|b)^{k}\), including the dead state (ch01-regexbench, section 3, and Inputs/min-dfa.golden).

Lazy DFA (RE2)¶

Proposition 1.2.12 (The lazy DFA agrees with the simulation)

LazyMatch returns the same answers as Simulate. With a cache that is never flushed, it builds at most \(\min(\lvert w \rvert + 1, \lvert Q_D \rvert)\) states per search and does one Closure per miss.

Proof

By the invariant of Algorithm 1.2.6, Step(s, c) returns a state whose set is \(E(\mathrm{move}(s.\mathit{set}, c))\) both on a hit (the row entry was filled with exactly that) and on a miss (computed now). A flush discards cached states but interns the correct next set, so the invariant survives. Hence the sequence of sets is exactly the sequence of Lemma 1.2.8, and the answers coincide by Theorem 1.2.9. Each input symbol visits one state, so at most \(\lvert w \rvert + 1\) states are interned; all of them are subset-construction states (Theorem 1.2.10). \(\square\)

5. Complexity¶

Variables: \(n = \lvert w \rvert\) input length; \(m = \lvert r \rvert\) regex size; \(s = \lvert Q \rvert \le 2m\) NFA states; \(k\) = number of symbol classes; \(d = \lvert Q_D \rvert \le 2^{s}\) DFA states.

Technique	Time per match (worst)	Time (typical)	Space	Build cost
Backtracking	\(\Omega(2^{n})\) on \((a?)^{n}a^{n}\)	fast when the first choice is right	\(O(n + s)\) stack	none
Thompson simulation / Pike VM	\(O(n \cdot m)\)	\(O(n \cdot\) live states\()\)	\(O(s)\)	\(O(m)\)
Subset construction + DFA run	\(O(n)\) lookups	\(O(n)\)	\(O(d \cdot k)\) table	\(O(d \cdot k \cdot s)\), \(d \le 2^{s}\)
Lazy DFA	\(O(n \cdot m)\) (every step a miss)	\(O(n)\) once warm	\(O(C \cdot k)\)	amortized into the search

Proposition 1.2.13 (Backtracking is exponential on \((a?)^{n}a^{n}\))

On \(r_n = (a?)^{n} a^{n}\) and \(w = a^{n}\), a backtracking matcher that tries "take" before "skip" at each \(a?\) explores \(2^{n}\) assignments of take/skip to the \(n\) optional items before it succeeds.

Proof

A successful match must skip all \(n\) optional \(a\)'s (the \(n\) mandatory \(a\)'s need all \(n\) symbols). The search enumerates take/skip vectors in lexicographic order with "take" first, and every vector other than all-"skip" fails: it consumes \(t \ge 1\) symbols in the optional part and then the mandatory part runs out of input. All-"skip" is the last of the \(2^{n}\) vectors. Each failing vector costs at least one step, so the running time is \(\Omega(2^{n})\). \(\square\)

Pathological inputs, per technique. Backtracking: \((a?)^{n}a^{n}\) above, and nested stars such as (a*)*b on \(a^{n}\) (no b to find). Simulation: none; the \(O(nm)\) bound is uniform. Subset construction: \((a \mid b)^{*}a(a \mid b)^{k-1}\) (Proposition 1.2.11). Lazy DFA: the same family with a text that keeps visiting new subsets forces a miss on every byte (the lab's RegexLazyDFA.CorrectWhenTheCacheOverflows test drives it through cache flushes).

At scale (build/<preset>/bin/ch01-regexbench, course container, RelWithDebInfo): matches() on 200 000 short lines (1.8 MB) takes 36–106 ms for the Pike VM, 2–4 ms for the minimized DFA, 5–8 ms for the lazy DFA and 26–38 ms for libstdc++'s backtracking std::regex; on \((a?)^{20}a^{20}\) std::regex needs 122 ms while every automaton takes under 1 ms.

Backtracking¶

Memoization (Go's bit-state backtracker, bounded by program × input size): remember failed \((\text{instruction}, \text{position})\) pairs; linear time, at the cost of a bit per pair. Go uses it only for small programs and inputs.
Atomic groups and possessive quantifiers (PCRE, Java): let the programmer forbid backtracking into a group; fixes some blow-ups, changes the language matched.
Step limits (PCRE's match_limit, .NET timeouts): a safety net, not an algorithm (the grep box in §2).

Thompson NFA simulation (Pike VM)¶

Bit-parallel simulation (Shift-And, Baeza-Yates–Gonnet; used by agrep): for NFAs of at most 64 states, \(S\) is one machine word and a step is a few shifts and masks. The ε-free position automaton (Lesson 1.1) is the natural input.
Submatch tracking (Pike [Pik87], Laurikari's tagged NFAs): threads carry capture positions; priority order implements leftmost-first or leftmost-longest.
One-pass NFAs (RE2, Go): if at every point at most one thread can make progress, the simulation needs no thread list at all.

Subset construction¶

Direct construction from positions (Dragon §3.9.5, GNU grep): build DFA states as sets of positions, never materializing the NFA.
Minimization afterwards (Lesson 1.4) or during construction (re2c minimizes; flex does not).
Table compression (flex's default -Cem: equivalence classes, meta-classes and a comb-vector "base/next/check" layout) trades a few instructions per byte for tables tens of times smaller [FLEX-Manual].

Lazy DFA (RE2)¶

Cache policy: RE2 flushes everything; GNU grep also bounds the number of states. Smarter policies (LRU) have not paid off in practice because a flush is cheap relative to rebuilding hot states.
Fallback: RE2 abandons the DFA for the Pike VM when the cache hit rate drops below a threshold; Rust's regex-automata "hybrid" engine does the same.
Reverse DFA for match starts (RE2, Rust): run a DFA forward to find where a match ends, then a reversed DFA backwards to find where it starts, avoiding the Pike VM entirely for unanchored searches.

7. In real compilers¶

Backtracking¶

libstdc++ std::regex (ECMAScript mode) backtracks by default; the lab uses it as the oracle for correctness and as the slow baseline for speed (tests/ch01/unit/RegexTest.cpp).
LLVM llvm/lib/Support/regengine.inc — backref is the only backtracking routine, used only when the pattern has backreferences [LLVM-Regex].
PCRE2 / Perl / Python re: backtracking engines; the grep box in §2 shows PCRE2's step limit.

Thompson NFA simulation (Pike VM)¶

LLVM

llvm/lib/Support/regexec.c — llvm_regexec picks smatcher (state set = one long) when the compiled program has at most CHAR_BIT * sizeof(long) states, otherwise lmatcher (state set = a byte array); regengine.inc — step maps the set of states before a character to the set after it (LLVM 23.1.2) [LLVM-Regex]. This is the engine behind FileCheck's {{regex}} patterns.

Go src/regexp/exec.go — machine.step is a Pike VM over the program from syntax.Compile [GO-Regexp].
RE2 re2/nfa.cc — NFA::Step, used when the DFA gives up or submatches are needed [RE2-DFA].

Find where LLVM does it. Open llvm/lib/Support/regexec.c at llvmorg-23.1.2. Question: which two #defines make the same regengine.inc text compile into two different matchers, and what type is a "set of states" in each? (Quiz llvm-regex-state-sets.)

Subset construction¶

flex src/nfa.c builds the NFA and src/dfa.c's ntod ("NFA to DFA") runs the subset construction over equivalence classes (flex 2.6.4) [FLEX-DFA]; box in §2.
re2c determinizes (with tags for submatch extraction) and then minimizes, src/dfa/determinization.cc and src/dfa/minimization.cc (re2c 3.1) [RE2C-Min].
Rust regex-automata src/dfa/determinize/mod.rs builds dense DFAs ahead of time for its dfa module.
LLVM llvm/utils/TableGen/DFAEmitter.cpp — DfaEmitter::constructDfa and visitDfaState determinize an NFA of VLIW packetization choices: a DFA state is a SmallVector of NFA states, interned in a UniqueVector (the index map of Algorithm 1.2.5), processed in order of first appearance (LLVM 23.1.2) [LLVM-DFAEmitter].

Lazy DFA (RE2)¶

RE2 re2/dfa.cc — DFA::RunStateOnByte, DFA::ResetCache, mem_budget_ (tag 2024-07-02) [RE2-DFA]; box in §2.
GNU grep — gnulib lib/dfa.c, build_state is called from dfaexec when a transition is missing [GNULIB-DFA].
Rust regex-automata src/hybrid/ ("lazy DFA") with a configurable cache capacity.

8. Comparison¶

Technique	Power / precision	Speed	Output / error quality	Implementation effort	Typical use
Backtracking	regular + backreferences, lookaround	\(O(n)\) typical, \(\Omega(2^{n})\) worst	leftmost-first submatches; no "how far did it get"	small	Perl, PCRE, Python `re`, `std::regex`
Thompson simulation / Pike VM	any regex; submatches with threads	\(O(nm)\) always	submatches, leftmost-first or -longest	small–moderate	RE2/Go/Rust fallback, LLVM `Regex`, submatch extraction
Subset construction (+ DFA run)	any regex; no submatches without tags	\(O(n)\), one lookup per byte	accept/reject and longest match only	moderate (+ minimization, tables)	lexer generators (flex, re2c), ahead-of-time DFAs
Lazy DFA	any regex; no submatches	\(O(n)\) when warm, \(O(nm)\) worst	as DFA	moderate (+ cache management)	grep, RE2, Rust `regex` for search

Choose backtracking when you need backreferences or you control the patterns and they are small. Choose the Pike VM when you need submatches with a linear-time guarantee. Choose an ahead-of-time DFA when the pattern set is fixed at build time, like a lexer: the table is built once and every byte costs one lookup. Choose a lazy DFA when patterns arrive at run time (search tools, user queries) and some patterns would blow up if fully determinized.

Lab numbers (ch01-regexbench, see §5): per 1.8 MB of short lines, DFA 2–4 ms, lazy DFA 5–8 ms, Pike VM 36–106 ms, std::regex 26–38 ms; on \((a?)^{20}a^{20}\), std::regex 122 ms vs under 1 ms for every automaton.

9. Assessment¶

Technique	Quiz ids	Drill	Flashcard tag	Exercises
Backtracking	`backtracking-blowup`, `engine-choice`	justification below	`backtracking`	— (baseline `std::regex`)
Thompson NFA simulation (Pike VM)	`thompson-closure`, `llvm-regex-state-sets`	`./course drill epsilon-closure --difficulty medium`	`pike-vm`	Lab L2
Subset construction	`subset-states`, `subset-blowup`	`./course drill subset-construction`	`subset-construction`	Lab L3
Lazy DFA (RE2)	`lazy-dfa-states`, `engine-choice`	`./course drill subset-construction` (the lazy DFA builds a subset of these states)	`lazy-dfa`	Lab ★ L6

Backtracking has no drill of its own: tracing an exponential search is not good practice material; the quiz asks you to count the search (backtracking-blowup) and the §3 table shows the trace.

Pitfall

"The DFA is exponential, so avoid DFAs" is wrong for lexers: the blow-up needs patterns like "the \(k\)-th symbol from the end", which token classes never contain. Pebble's whole regular token set (labs/ch01-regex/inputs/pebble.lexspec) determinizes to 147 live states, 135 (dead state included) after Hopcroft's minimization.

References¶

See the chapter references.

Lesson 1.2 — Running automata: backtracking, NFA simulation, subset construction, lazy DFAs¶

1. Problem and motivation¶

Backtracking¶

Thompson NFA simulation (Pike VM)¶

Subset construction¶

Lazy DFA (RE2)¶

2. Definitions and algorithms¶

Backtracking¶

Thompson NFA simulation (Pike VM)¶

Subset construction¶

Lazy DFA (RE2)¶

3. Worked example¶

Backtracking¶

Thompson NFA simulation (Pike VM)¶

Subset construction¶

Lazy DFA (RE2)¶

4. Invariants and correctness¶

Backtracking¶

Thompson NFA simulation (Pike VM)¶

Subset construction¶

Lazy DFA (RE2)¶

5. Complexity¶

6. Variants and refinements¶

Backtracking¶

Thompson NFA simulation (Pike VM)¶

Subset construction¶

Lazy DFA (RE2)¶

7. In real compilers¶

Backtracking¶

Thompson NFA simulation (Pike VM)¶

Subset construction¶

Lazy DFA (RE2)¶

8. Comparison¶

9. Assessment¶

References¶