states * 256 array;Learn Zig Series):Last episode we built a real regular expression engine: we parsed a pattern into a syntax tree, ran Thompson's construction to turn that tree into an NFA, and then simulated the NFA in guaranteed linear time by tracking the whole set of states the machine could be in at once. No backtracking, no ReDoS, no exponential blowups. Correct and safe. But if you look closely at that simulation, it is doing a surprising amount of busywork: at every character we walk the active set, follow out-edges, recompute an epsilon-closure, dedupe with a seen array, and swap two lists. For a single character. Over and over. The machine is fast in the big-O sense, but it is re-deriving the same answers millions of times on a long input.
Today we fix that, and the fix is one of the most satisfying results in all of computer science: any NFA can be converted into a DFA, a deterministic machine that is in exactly one state at a time and needs just a single array lookup per input byte. No sets, no closures, no bookkeeping at match time. The technique is the subset construction, and the punchline of last episode's third exercise was pointing straight at it. Here we go!
Three exercises last time -- character classes, unanchored search, and caching the state sets. Full code for each, and the third one is the whole reason today's episode exists.
Exercise 1 -- Character classes. Extend the parser and NFA to support [abc] and ranges like [a-z], plus negation with [^...]. I add a class node to the AST that carries a 256-bit set (a plain [32]u8 bitset -- one bit per possible byte), a matching class NFA state, and the consume logic in matches. The parser grows a parseClass function that reads until the closing ], expanding any a-z range as it goes. Here is the whole engine with classes wired in:
const std = @import("std");
const Node = union(enum) {
literal: u8,
any,
class: [32]u8, // 256-bit set: bit c set means "c matches"
concat: struct { left: *Node, right: *Node },
alternate: struct { left: *Node, right: *Node },
star: *Node,
plus: *Node,
optional: *Node,
};
fn setBit(bits: *[32]u8, c: u8) void {
bits[c >> 3] |= @as(u8, 1) << @intCast(c & 7);
}
fn testBit(bits: [32]u8, c: u8) bool {
return (bits[c >> 3] >> @intCast(c & 7)) & 1 != 0;
}
const Parser = struct {
src: []const u8,
pos: usize = 0,
arena: std.mem.Allocator,
fn peek(self: *Parser) ?u8 {
if (self.pos >= self.src.len) return null;
return self.src[self.pos];
}
fn advance(self: *Parser) u8 {
const c = self.src[self.pos];
self.pos += 1;
return c;
}
fn create(self: *Parser, node: Node) !*Node {
const p = try self.arena.create(Node);
p.* = node;
return p;
}
const ParseError = error{ UnexpectedEnd, UnbalancedParen, UnexpectedToken, BadClass, OutOfMemory };
fn parseAlt(self: *Parser) ParseError!*Node {
var left = try self.parseConcat();
while (self.peek() == '|') {
_ = self.advance();
const right = try self.parseConcat();
left = try self.create(.{ .alternate = .{ .left = left, .right = right } });
}
return left;
}
fn parseConcat(self: *Parser) ParseError!*Node {
var left = try self.parseRepeat();
while (self.peek()) |c| {
if (c == '|' or c == ')') break;
const right = try self.parseRepeat();
left = try self.create(.{ .concat = .{ .left = left, .right = right } });
}
return left;
}
fn parseRepeat(self: *Parser) ParseError!*Node {
var node = try self.parseAtom();
while (self.peek()) |c| switch (c) {
'*' => {
_ = self.advance();
node = try self.create(.{ .star = node });
},
'+' => {
_ = self.advance();
node = try self.create(.{ .plus = node });
},
'?' => {
_ = self.advance();
node = try self.create(.{ .optional = node });
},
else => break,
};
return node;
}
fn parseClass(self: *Parser) ParseError!*Node {
_ = self.advance(); // consume '['
var bits = [_]u8{0} ** 32;
var negate = false;
if (self.peek() == '^') {
_ = self.advance();
negate = true;
}
while (self.peek()) |c| {
if (c == ']') break;
_ = self.advance();
// a range like a-z: current char, a '-', then an end char
if (self.peek() == '-' and self.pos + 1 < self.src.len and self.src[self.pos + 1] != ']') {
_ = self.advance(); // '-'
const end = self.advance();
var x: usize = c;
while (x <= end) : (x += 1) setBit(&bits, @intCast(x));
} else {
setBit(&bits, c);
}
}
if (self.peek() != ']') return error.BadClass;
_ = self.advance(); // consume ']'
if (negate) for (&bits) |*b| {
b.* = ~b.*;
};
return self.create(.{ .class = bits });
}
fn parseAtom(self: *Parser) ParseError!*Node {
const c = self.peek() orelse return error.UnexpectedEnd;
switch (c) {
'(' => {
_ = self.advance();
const inner = try self.parseAlt();
if (self.peek() != ')') return error.UnbalancedParen;
_ = self.advance();
return inner;
},
'[' => return self.parseClass(),
'.' => {
_ = self.advance();
return self.create(.any);
},
')', '|', '*', '+', '?' => return error.UnexpectedToken,
else => {
_ = self.advance();
return self.create(.{ .literal = c });
},
}
}
};
const NfaKind = enum { char, any, class, split, match };
const NfaState = struct {
kind: NfaKind,
ch: u8 = 0,
set: [32]u8 = [_]u8{0} ** 32,
out: u32 = 0,
out1: u32 = 0,
};
const Hole = struct { state: u32, slot: u1 };
const Fragment = struct { start: u32, holes: []Hole };
const Builder = struct {
states: std.ArrayList(NfaState),
gpa: std.mem.Allocator,
fn addState(self: *Builder, s: NfaState) !u32 {
const idx: u32 = @intCast(self.states.items.len);
try self.states.append(self.gpa, s);
return idx;
}
fn patch(self: *Builder, holes: []const Hole, target: u32) void {
for (holes) |h| {
if (h.slot == 0) {
self.states.items[h.state].out = target;
} else {
self.states.items[h.state].out1 = target;
}
}
}
fn build(self: *Builder, node: *const Node, arena: std.mem.Allocator) !Fragment {
switch (node.*) {
.literal => |c| {
const s = try self.addState(.{ .kind = .char, .ch = c });
const holes = try arena.alloc(Hole, 1);
holes[0] = .{ .state = s, .slot = 0 };
return .{ .start = s, .holes = holes };
},
.any => {
const s = try self.addState(.{ .kind = .any });
const holes = try arena.alloc(Hole, 1);
holes[0] = .{ .state = s, .slot = 0 };
return .{ .start = s, .holes = holes };
},
.class => |bits| {
const s = try self.addState(.{ .kind = .class, .set = bits });
const holes = try arena.alloc(Hole, 1);
holes[0] = .{ .state = s, .slot = 0 };
return .{ .start = s, .holes = holes };
},
.concat => |pair| {
const f1 = try self.build(pair.left, arena);
const f2 = try self.build(pair.right, arena);
self.patch(f1.holes, f2.start);
return .{ .start = f1.start, .holes = f2.holes };
},
.alternate => |pair| {
const f1 = try self.build(pair.left, arena);
const f2 = try self.build(pair.right, arena);
const s = try self.addState(.{ .kind = .split, .out = f1.start, .out1 = f2.start });
const holes = try arena.alloc(Hole, f1.holes.len + f2.holes.len);
@memcpy(holes[0..f1.holes.len], f1.holes);
@memcpy(holes[f1.holes.len..], f2.holes);
return .{ .start = s, .holes = holes };
},
.star => |inner| {
const f = try self.build(inner, arena);
const s = try self.addState(.{ .kind = .split, .out = f.start });
self.patch(f.holes, s);
const holes = try arena.alloc(Hole, 1);
holes[0] = .{ .state = s, .slot = 1 };
return .{ .start = s, .holes = holes };
},
.plus => |inner| {
const f = try self.build(inner, arena);
const s = try self.addState(.{ .kind = .split, .out = f.start });
self.patch(f.holes, s);
const holes = try arena.alloc(Hole, 1);
holes[0] = .{ .state = s, .slot = 1 };
return .{ .start = f.start, .holes = holes };
},
.optional => |inner| {
const f = try self.build(inner, arena);
const s = try self.addState(.{ .kind = .split, .out = f.start });
const holes = try arena.alloc(Hole, f.holes.len + 1);
@memcpy(holes[0..f.holes.len], f.holes);
holes[f.holes.len] = .{ .state = s, .slot = 1 };
return .{ .start = s, .holes = holes };
},
}
}
};
const Regex = struct {
states: []NfaState,
start: u32,
gpa: std.mem.Allocator,
fn deinit(self: *Regex) void {
self.gpa.free(self.states);
}
fn addToList(self: *const Regex, list: *std.ArrayList(u32), seen: []bool, s: u32) !void {
if (seen[s]) return;
seen[s] = true;
const st = self.states[s];
if (st.kind == .split) {
try self.addToList(list, seen, st.out);
try self.addToList(list, seen, st.out1);
} else {
try list.append(self.gpa, s);
}
}
fn matches(self: *const Regex, input: []const u8) !bool {
const seen = try self.gpa.alloc(bool, self.states.len);
defer self.gpa.free(seen);
var clist: std.ArrayList(u32) = .empty;
defer clist.deinit(self.gpa);
var nlist: std.ArrayList(u32) = .empty;
defer nlist.deinit(self.gpa);
@memset(seen, false);
try self.addToList(&clist, seen, self.start);
for (input) |c| {
@memset(seen, false);
nlist.clearRetainingCapacity();
for (clist.items) |s| {
const st = self.states[s];
const consume = switch (st.kind) {
.char => st.ch == c,
.any => true,
.class => testBit(st.set, c),
else => false,
};
if (consume) try self.addToList(&nlist, seen, st.out);
}
std.mem.swap(std.ArrayList(u32), &clist, &nlist);
}
for (clist.items) |s| {
if (self.states[s].kind == .match) return true;
}
return false;
}
};
fn compile(gpa: std.mem.Allocator, pattern: []const u8) !Regex {
var arena_state = std.heap.ArenaAllocator.init(gpa);
defer arena_state.deinit();
const arena = arena_state.allocator();
var parser = Parser{ .src = pattern, .arena = arena };
const ast = try parser.parseAlt();
if (parser.pos != pattern.len) return error.TrailingInput;
var builder = Builder{ .states = .empty, .gpa = gpa };
errdefer builder.states.deinit(gpa);
const frag = try builder.build(ast, arena);
const match_state = try builder.addState(.{ .kind = .match });
builder.patch(frag.holes, match_state);
const states = try builder.states.toOwnedSlice(gpa);
return .{ .states = states, .start = frag.start, .gpa = gpa };
}
test "character classes and ranges" {
var re = try compile(std.testing.allocator, "[a-f]+");
defer re.deinit();
try std.testing.expect(try re.matches("cafe"));
try std.testing.expect(!try re.matches("code")); // 'o' out of range
var neg = try compile(std.testing.allocator, "[^0-9]+");
defer neg.deinit();
try std.testing.expect(try neg.matches("hello"));
try std.testing.expect(!try neg.matches("h3llo"));
}
The only genuinely new idea is the bitset. Storing the class as a [32]u8 (256 bits) means membership is a single shift-and-mask -- testBit -- rather than a scan through a list of characters, and negation is just flipping every bit. Everything else is the exact machine from last episode with one more NfaKind variant threaded through. Note the range check uses a usize loop counter (x) so that x <= end cannot silently wrap when end is 255.
Exercise 2 -- Substring search. Last time matches was anchored at both ends: it required the pattern to consume the whole input. Real search matches anywhere. The classic trick is to inject a fresh copy of the start state's closure into the active set at every position, so a new match attempt can begin at each character, and to report success the moment the match state appears in the set. This slots straight into the Regex struct from last episode -- everything else is unchanged:
// Unanchored search: match the pattern anywhere in the input.
fn search(self: *const Regex, input: []const u8) !bool {
const seen = try self.gpa.alloc(bool, self.states.len);
defer self.gpa.free(seen);
var clist: std.ArrayList(u32) = .empty;
defer clist.deinit(self.gpa);
var nlist: std.ArrayList(u32) = .empty;
defer nlist.deinit(self.gpa);
@memset(seen, false);
try self.addToList(&clist, seen, self.start); // a match may begin at position 0
for (clist.items) |s| {
if (self.states[s].kind == .match) return true; // empty match
}
for (input) |c| {
@memset(seen, false);
nlist.clearRetainingCapacity();
// seed a fresh start here, so a new attempt can begin at every position
try self.addToList(&nlist, seen, self.start);
for (clist.items) |s| {
const st = self.states[s];
const consume = switch (st.kind) {
.char => st.ch == c,
.any => true,
else => false,
};
if (consume) try self.addToList(&nlist, seen, st.out);
}
std.mem.swap(std.ArrayList(u32), &clist, &nlist);
for (clist.items) |s| {
if (self.states[s].kind == .match) return true;
}
}
return false;
}
};
The two additions are the re-seed (addToList(&nlist, seen, self.start) at the top of every step) and the accept check inside the loop rather than only at the end. Seeding start at each position is exactly how grep finds a pattern in the middle of a line. Note that because seen is reset each step and the start closure is added first, the fresh seeds and the carried-over states dedupe against each other for free.
Exercise 3 -- Cache the state sets. This is the important one. Instrument the matcher to record, for each step, the sorted list of active NFA-state indices, and count how many distinct sets ever occur. I canonicalise each set into a byte key (sort the indices, reinterpret as bytes) and drop it into a StringHashMap:
fn setKey(gpa: std.mem.Allocator, items: []const u32) ![]u8 {
const sorted = try gpa.dupe(u32, items);
defer gpa.free(sorted);
std.mem.sort(u32, sorted, {}, std.sort.asc(u32));
return gpa.dupe(u8, std.mem.sliceAsBytes(sorted));
}
// Anchored match that also counts how many DISTINCT active sets ever occur.
fn matchesCounting(re: *const Regex, input: []const u8, distinct: *usize) !bool {
const gpa = re.gpa;
const seen = try gpa.alloc(bool, re.states.len);
defer gpa.free(seen);
var clist: std.ArrayList(u32) = .empty;
defer clist.deinit(gpa);
var nlist: std.ArrayList(u32) = .empty;
defer nlist.deinit(gpa);
var sets = std.StringHashMap(void).init(gpa);
defer {
var it = sets.keyIterator();
while (it.next()) |k| gpa.free(k.*);
sets.deinit();
}
const note = struct {
fn f(g: std.mem.Allocator, s: *std.StringHashMap(void), items: []const u32) !void {
const key = try setKey(g, items);
const gop = try s.getOrPut(key);
if (gop.found_existing) g.free(key);
}
}.f;
@memset(seen, false);
try re.addToList(&clist, seen, re.start);
try note(gpa, &sets, clist.items);
for (input) |c| {
@memset(seen, false);
nlist.clearRetainingCapacity();
for (clist.items) |s| {
const st = re.states[s];
const consume = switch (st.kind) {
.char => st.ch == c,
.any => true,
else => false,
};
if (consume) try re.addToList(&nlist, seen, st.out);
}
std.mem.swap(std.ArrayList(u32), &clist, &nlist);
try note(gpa, &sets, clist.items);
}
distinct.* = sets.count();
for (clist.items) |s| {
if (re.states[s].kind == .match) return true;
}
return false;
}
test "distinct active sets stay small and bounded" {
const gpa = std.testing.allocator;
var re = try compile(gpa, "a(b|c)*d");
defer re.deinit();
var buf: [4000]u8 = undefined;
buf[0] = 'a';
var i: usize = 1;
while (i < buf.len - 1) : (i += 1) buf[i] = if (i % 2 == 0) 'b' else 'c';
buf[buf.len - 1] = 'd';
var distinct: usize = 0;
try std.testing.expect(try matchesCounting(&re, &buf, &distinct));
// 4000 input characters, but only a handful of distinct active sets
try std.testing.expect(distinct <= 8);
}
Run that over four thousand characters and the count of distinct active sets is not four thousand, and it is not even close: it is 3. Three. The simulation spent the entire input bouncing between the same three sets of NFA states, recomputing each one from scratch every time it arrived. That is a screaming hint. If there are only a handful of distinct sets, we should give each one a number, work out ahead of time where each numbered set goes on each input byte, and then matching becomes: look up the number, follow the arrow, repeat. Those numbered sets are the states of a DFA, and that is today's whole story. ;-)
Here is the mental shift. The NFA simulation's "current state" is really the set of NFA states it currently occupies. Exercise 3 showed that, for a given pattern, only a small and bounded number of these sets can ever occur -- because a set is determined entirely by which NFA states are reachable, and there are only finitely many subsets that matter. So we do the obvious thing: treat each distinct reachable set as a single new state. That new machine is deterministic -- from one set, a given input byte leads to exactly one next set -- which is precisely the definition of a DFA.
The construction that does this has a name, the subset construction (or powerset construction), and it dates back to Rabin and Scott in 1959. The recipe is:
We keep a worklist of sets we have discovered but not yet expanded, and a map from "canonical set" to "DFA state id" so we never create the same state twice. When the worklist drains, the DFA is complete.
Before we build the table, look at how little work matching a DFA takes. I store the transitions as one flat array of states * 256 entries -- row s, column c is trans[s*256 + c] -- and a parallel accept array. A dead state is a reserved sentinel. That is the entire runtime:
const Nfa = struct {
states: []NfaState,
start: u32,
gpa: std.mem.Allocator,
fn deinit(self: *Nfa) void {
self.gpa.free(self.states);
}
// Epsilon-closure of a single state: follow free split edges, collect the
// input-consuming (and match) states into `list`.
fn addClosure(self: *const Nfa, list: *std.ArrayList(u32), seen: []bool, s: u32) !void {
if (seen[s]) return;
seen[s] = true;
const st = self.states[s];
if (st.kind == .split) {
try self.addClosure(list, seen, st.out);
try self.addClosure(list, seen, st.out1);
} else {
try list.append(self.gpa, s);
}
}
};
fn compileNfa(gpa: std.mem.Allocator, pattern: []const u8) !Nfa {
var arena_state = std.heap.ArenaAllocator.init(gpa);
defer arena_state.deinit();
const arena = arena_state.allocator();
var parser = Parser{ .src = pattern, .arena = arena };
const ast = try parser.parseAlt();
if (parser.pos != pattern.len) return error.TrailingInput;
var builder = Builder{ .states = .empty, .gpa = gpa };
errdefer builder.states.deinit(gpa);
const frag = try builder.build(ast, arena);
const match_state = try builder.addState(.{ .kind = .match });
builder.patch(frag.holes, match_state);
const states = try builder.states.toOwnedSlice(gpa);
return .{ .states = states, .start = frag.start, .gpa = gpa };
}
That is last episode's machine, unchanged, wrapped in a tiny Nfa holder with the addClosure helper (renamed from addToList) and a compileNfa that hands us the states and start index. The parser and Thompson builder are exactly as we left them. Now we compile it one step further.
const Dfa = struct {
trans: []u32, // n_states * 256, indexed [state*256 + byte]
accept: []bool, // n_states
n_states: usize,
gpa: std.mem.Allocator,
const DEAD = std.math.maxInt(u32); // the trap state: no path forward
fn deinit(self: *Dfa) void {
self.gpa.free(self.trans);
self.gpa.free(self.accept);
}
// Anchored full match: one state, one array lookup per character. No sets.
fn matches(self: *const Dfa, input: []const u8) bool {
var s: u32 = 0; // DFA state 0 is always the start
for (input) |c| {
s = self.trans[s * 256 + c];
if (s == DEAD) return false;
}
return self.accept[s];
}
};
Compare matches here to last episode's version. There is no allocator, no seen array, no two-list swap, no closure recursion -- just s = trans[s*256 + c] in a tight loop, which the CPU eats for breakfast. All the cleverness has been moved out of the hot path and into a one-time build step. A DFA match is, quite literally, one indexed load and a comparison per byte. This is why the fast engines convert.
Now the build. We need three helpers and a worklist loop. setKey turns a set of NFA-state indices into a canonical byte string (sort, then reinterpret) so identical sets hash to the same key -- allocating a real []u8 we own, not a view over the u32 allocation (that alignment mismatch would bite us at free time). isAccepting checks for the match state. And subsetConstruct runs the worklist:
fn setKey(gpa: std.mem.Allocator, items: []const u32) ![]u8 {
const sorted = try gpa.dupe(u32, items);
defer gpa.free(sorted);
std.mem.sort(u32, sorted, {}, std.sort.asc(u32));
return gpa.dupe(u8, std.mem.sliceAsBytes(sorted));
}
fn isAccepting(nfa: *const Nfa, set: []const u32) bool {
for (set) |s| if (nfa.states[s].kind == .match) return true;
return false;
}
fn subsetConstruct(gpa: std.mem.Allocator, nfa: *const Nfa) !Dfa {
const seen = try gpa.alloc(bool, nfa.states.len);
defer gpa.free(seen);
// Map from canonical set-key -> DFA state id. Keys are owned here.
var ids = std.StringHashMap(u32).init(gpa);
defer {
var it = ids.keyIterator();
while (it.next()) |k| gpa.free(k.*);
ids.deinit();
}
// worklist of DFA states still needing their row filled in; each entry
// owns the NFA set it stands for.
var work: std.ArrayList([]u32) = .empty;
defer {
for (work.items) |set| gpa.free(set);
work.deinit(gpa);
}
var trans: std.ArrayList(u32) = .empty;
defer trans.deinit(gpa);
var accept: std.ArrayList(bool) = .empty;
defer accept.deinit(gpa);
// Intern a set: return its DFA id, creating a new state if unseen.
const intern = struct {
fn f(
g: std.mem.Allocator,
m: *std.StringHashMap(u32),
wl: *std.ArrayList([]u32),
tr: *std.ArrayList(u32),
ac: *std.ArrayList(bool),
nn: *const Nfa,
set: []u32, // ownership moves in
) !u32 {
const key = try setKey(g, set);
const gop = try m.getOrPut(key);
if (gop.found_existing) {
g.free(key);
g.free(set);
return gop.value_ptr.*;
}
const id: u32 = @intCast(ac.items.len);
gop.value_ptr.* = id;
try ac.append(g, isAccepting(nn, set));
try tr.appendNTimes(g, Dfa.DEAD, 256);
try wl.append(g, set); // keep the set for row-filling
return id;
}
}.f;
// DFA start = closure of the NFA start.
{
var list: std.ArrayList(u32) = .empty;
@memset(seen, false);
try nfa.addClosure(&list, seen, nfa.start);
const set = try list.toOwnedSlice(gpa);
_ = try intern(gpa, &ids, &work, &trans, &accept, nfa, set);
}
var cursor: usize = 0;
while (cursor < work.items.len) : (cursor += 1) {
const set = work.items[cursor];
const from_id: u32 = @intCast(cursor);
var c: usize = 0;
while (c < 256) : (c += 1) {
const byte: u8 = @intCast(c);
var list: std.ArrayList(u32) = .empty;
defer list.deinit(gpa);
@memset(seen, false);
for (set) |s| {
const st = nfa.states[s];
const consume = switch (st.kind) {
.char => st.ch == byte,
.any => true,
else => false,
};
if (consume) try nfa.addClosure(&list, seen, st.out);
}
if (list.items.len == 0) continue; // stays DEAD
const next_set = try gpa.dupe(u32, list.items);
const to_id = try intern(gpa, &ids, &work, &trans, &accept, nfa, next_set);
trans.items[from_id * 256 + c] = to_id;
}
}
const n = accept.items.len;
return .{
.trans = try trans.toOwnedSlice(gpa),
.accept = try accept.toOwnedSlice(gpa),
.n_states = n,
.gpa = gpa,
};
}
fn compileDfa(gpa: std.mem.Allocator, pattern: []const u8) !Dfa {
var nfa = try compileNfa(gpa, pattern);
defer nfa.deinit();
return subsetConstruct(gpa, &nfa);
}
The intern inner function is the heart of it: hand it a set, and it either returns the id of an existing DFA state or mints a brand-new one -- appending a fresh all-dead row of 256 entries and queuing the set for expansion. Ownership is explicit throughout, the way Zig likes it: the map owns its keys, the worklist owns the NFA sets, and both are freed in defer blocks. One subtle bug I want to call out, because it caught me: intern appends to trans, which can reallocate the backing array, so I must recompute the row index after calling it rather than holding a pointer across the call. In a garbage-collected language you would never notice; in Zig the ownership is in your face, which is exactly what stops the dangling-pointer version from ever shipping.
Let us prove the DFA accepts the same language as the NFA -- both the hand-picked cases and a couple thousand random strings checked against an independent predicate:
test "the DFA matches the same language as the NFA" {
var dfa = try compileDfa(std.testing.allocator, "a(b|c)*d");
defer dfa.deinit();
try std.testing.expect(dfa.matches("ad"));
try std.testing.expect(dfa.matches("abd"));
try std.testing.expect(dfa.matches("abcbcbcd"));
try std.testing.expect(!dfa.matches("abce"));
try std.testing.expect(!dfa.matches("ab"));
}
test "DFA and NFA agree on thousands of random strings" {
const gpa = std.testing.allocator;
var dfa = try compileDfa(gpa, "a(a|b)*b");
defer dfa.deinit();
var prng = std.Random.DefaultPrng.init(0x5eed);
const rand = prng.random();
var buf: [200]u8 = undefined;
var trial: usize = 0;
while (trial < 2000) : (trial += 1) {
const len = rand.intRangeAtMost(usize, 0, buf.len);
for (buf[0..len]) |*ch| ch.* = if (rand.boolean()) 'a' else 'b';
const s = buf[0..len];
const expected = len >= 2 and s[0] == 'a' and s[len - 1] == 'b';
try std.testing.expectEqual(expected, dfa.matches(s));
}
}
Same answers as the NFA, every time. And here is the lovely closing of the loop: for a(b|c)*d, subsetConstruct produces exactly 3 DFA states -- the very same three distinct sets that exercise 3 counted. The counting experiment was not a curiosity; it was the DFA in disguise, waiting to be named.
So if the DFA is strictly faster to run, why did we not just build one last episode and skip the NFA entirely? Because the subset construction has a nasty worst case: a pattern of size m can produce a DFA with up to 2^m states. It is not merely theoretical -- a pattern like (a|b)*a(a|b)(a|b)(a|b)... that pins down "the k-th character from the end" genuinely needs 2^k states, because the machine has to remember the last k characters, and there are 2^k possible histories. An eager subset construction would sit there dutifully materialising every one of those states before matching a single byte, and would happily exhaust your memory on a pattern a user typed into a search box. Having said that, most real patterns produce small DFAs -- but "most" is not a guarantee you can build a robust engine on.
The fix is the trick that makes DFAs practical, and it is what RE2, Go's regexp, and Rust's regex crate all actually do. Do not build the whole table up front. Start with just the start state, and compute each transition the first time the input actually asks for it -- then cache the result so the second time is a plain lookup. This is a lazy DFA (sometimes "DFA construction on the fly"). On a pattern-and-input pair, you only ever materialise the states your specific input walks through, which is bounded by the input length no matter how monstrous the full DFA would be. You get the DFA's one-lookup-per-byte speed on the hot path, with the NFA's build cost amortised across the run and capped by what you actually touch:
// ---- Lazy DFA: build states on demand while matching, and cache them ----
const LazyDfa = struct {
nfa: *const Nfa,
gpa: std.mem.Allocator,
ids: std.StringHashMap(u32), // set-key -> state id (keys owned)
sets: std.ArrayList([]u32), // id -> NFA set (owned)
accept: std.ArrayList(bool),
trans: std.ArrayList(u32), // id*256 + byte, lazily filled
seen: []bool,
built: usize = 0, // how many DFA states we actually materialised
const DEAD = std.math.maxInt(u32);
const UNKNOWN = std.math.maxInt(u32) - 1; // "not computed yet"
fn init(gpa: std.mem.Allocator, nfa: *const Nfa) !LazyDfa {
return .{
.nfa = nfa,
.gpa = gpa,
.ids = std.StringHashMap(u32).init(gpa),
.sets = .empty,
.accept = .empty,
.trans = .empty,
.seen = try gpa.alloc(bool, nfa.states.len),
};
}
fn deinit(self: *LazyDfa) void {
var it = self.ids.keyIterator();
while (it.next()) |k| self.gpa.free(k.*);
self.ids.deinit();
for (self.sets.items) |set| self.gpa.free(set);
self.sets.deinit(self.gpa);
self.accept.deinit(self.gpa);
self.trans.deinit(self.gpa);
self.gpa.free(self.seen);
}
// Intern an NFA set into a DFA state id, creating a fresh (unexplored) row
// the first time we see it. Takes ownership of `set`.
fn intern(self: *LazyDfa, set: []u32) !u32 {
const key = try setKey(self.gpa, set);
const gop = try self.ids.getOrPut(key);
if (gop.found_existing) {
self.gpa.free(key);
self.gpa.free(set);
return gop.value_ptr.*;
}
const id: u32 = @intCast(self.sets.items.len);
gop.value_ptr.* = id;
try self.sets.append(self.gpa, set);
try self.accept.append(self.gpa, isAccepting(self.nfa, set));
try self.trans.appendNTimes(self.gpa, UNKNOWN, 256); // nothing explored yet
self.built += 1;
return id;
}
fn startState(self: *LazyDfa) !u32 {
var list: std.ArrayList(u32) = .empty;
@memset(self.seen, false);
try self.nfa.addClosure(&list, self.seen, self.nfa.start);
return self.intern(try list.toOwnedSlice(self.gpa));
}
// The heart of the lazy engine: compute (and cache) the transition only
// when the input actually asks for it.
fn step(self: *LazyDfa, state: u32, byte: u8) !u32 {
const slot = state * 256 + @as(usize, byte);
const cached = self.trans.items[slot];
if (cached != UNKNOWN) return cached; // already known (a real id or DEAD)
var list: std.ArrayList(u32) = .empty;
defer list.deinit(self.gpa);
@memset(self.seen, false);
for (self.sets.items[state]) |s| {
const st = self.nfa.states[s];
const consume = switch (st.kind) {
.char => st.ch == byte,
.any => true,
else => false,
};
if (consume) try self.nfa.addClosure(&list, self.seen, st.out);
}
var result: u32 = DEAD;
if (list.items.len != 0) {
result = try self.intern(try self.gpa.dupe(u32, list.items));
}
// NB: intern may have reallocated trans, so recompute the slot index.
self.trans.items[state * 256 + @as(usize, byte)] = result;
return result;
}
fn matches(self: *LazyDfa, input: []const u8) !bool {
var s = try self.startState();
for (input) |c| {
s = try self.step(s, c);
if (s == DEAD) return false;
}
return self.accept.items[s];
}
};
The structure is the eager builder turned inside out. intern is nearly identical, but the transition rows start life filled with UNKNOWN rather than computed. The step function is where the laziness lives: if the slot is still UNKNOWN, it does the closure-and-move work once, caches the resulting id (or DEAD) in the table, and returns it; every subsequent visit to that state-and-byte is a single array read. The built counter is just there so we can watch it work:
test "lazy DFA agrees, and only builds the states the input touches" {
const gpa = std.testing.allocator;
var nfa = try compileNfa(gpa, "a(b|c)*d");
defer nfa.deinit();
var lazy = try LazyDfa.init(gpa, &nfa);
defer lazy.deinit();
try std.testing.expect(try lazy.matches("abcbcd"));
try std.testing.expect(!try lazy.matches("abx"));
std.debug.print("lazy DFA built {d} states\n", .{lazy.built});
Match a(b|c)*d against a short string and the lazy DFA builds all of 3 states -- the same three -- because this tiny pattern's full DFA is small. Point it at the exponential pattern from the previous section, though, and a thousand-character input still only ever builds a thousand-ish states, not 2^k. The real engines put a hard cap on the cache: if it grows past some budget they flush it and keep going (rebuilding lazily from scratch), and if even that thrashes they fall back to the plain NFA set-simulation from last episode. Belt and suspenders. That fallback is why the industrial engines are both blisteringly fast on ordinary input and immune to pathological patterns -- they are never forced to choose.
This is not a scaled-down imitation -- it is the actual architecture. Google's RE2 (C++), written by Russ Cox, is built on exactly this lazy DFA over a Thompson NFA, precisely because it runs on untrusted, user-supplied patterns at Google scale and cannot afford either ReDoS or unbounded memory. Go's standard-library regexp uses the same lineage (Cox again). Rust's regex crate is a whole toolbox of these automata -- a lazy DFA for throughput, the NFA simulation ("PikeVM") when it needs submatch capture, plus specialised literal scanners -- and it picks the cheapest engine that can answer your specific query. Every one of them is standing on the two-episode construction you just built: parse to a tree, Thompson-construct an NFA, and (lazily) subset-construct a DFA. The backtracking camp (PCRE, Perl, Python's re, JavaScript's built-in RegExp) skips the DFA entirely to keep backreferences -- and pays for it with the catastrophic worst case we have been dodging all along.
Our version is deliberately the smallest honest thing: byte-at-a-time, no Unicode, no captures, a full 256-wide row per state, and an eager builder alongside the lazy one so you can see both. Every shortcut is a known, well-trodden extension rather than a redesign -- which is exactly what the exercises below start chipping at. ;-)
DFA minimization. The subset construction can produce a DFA with redundant states -- two states that lead to the same accept/reject outcome on every possible suffix are indistinguishable and can be merged. Implement a simple partition-refinement minimizer (the schoolbook version of Hopcroft's algorithm): start with two groups (accepting and non-accepting) and repeatedly split any group whose members disagree on where some byte sends them, until nothing splits. Report how many states a(b|c)*d and (a|b)*abb collapse to.
Bound the lazy cache. Give LazyDfa a max_states budget. When intern would exceed it, clear the cache (the map, the sets, the accept and trans arrays), keep only the current state's set, and carry on building lazily from there. Prove it still matches correctly on a long input while never holding more than max_states rows -- this is the exact safety valve RE2 uses so a hostile pattern cannot eat your RAM.
Byte-class compression. A 256-column row per state is wasteful: for a(b|c)*d, only four bytes (a, b, c, d) ever do anything different -- every other byte behaves identically. Compute the equivalence classes of bytes (two bytes are equivalent if no state ever distinguishes them), map all 256 bytes down to a handful of class ids, and shrink each transition row from 256 entries to one-per-class. Measure the memory saved. This one optimisation is worth an enormous amount in the real engines, and it is the natural bridge to tying the whole matcher together next time.
That is the deterministic half of the story: subset construction, the state-explosion trap, and the lazy DFA that the serious engines lean on -- all sitting on top of last episode's NFA, and all in a few hundred lines of honest Zig. Bedankt voor het lezen, en tot de volgende keer! ;-)
@scipio