Simulating an NFA Without Determinizing It: State Sets, Epsilon Closure, and Bitsets

A nondeterministic finite automaton has a transition relation rather than a function: from one state and one symbol there may be zero, one, or several targets, and there may also be transitions that consume nothing at all. The definition says the machine accepts a string if some path through the relation reaches an accepting state. Read literally, that is a search over exponentially many paths.

The simulation that avoids the search rests on one observation: the paths do not need to be tracked individually, only the set of states they currently occupy. That set is a subset of Q, and the number of distinct subsets is finite, so the set-valued simulation is itself a deterministic machine. The implementation question is how to represent and update the set fast enough that the simulation does not pay the subset construction’s price up front.

The state set is the whole machine

Write S for the current set of live states. The initial value is not {q₀} but the epsilon closure of {q₀}: every state reachable from q₀ by zero or more epsilon transitions. The closure is necessary because an epsilon move can happen before the first symbol is read, and the definition allows any number of them in sequence.

For each input symbol a, the update is two steps:

1. M = { t | s ∈ S, (s, a, t) ∈ δ }, the set of targets reached by consuming a.
2. S' = ε-closure(M).

After the last symbol, the string is accepted if S ∩ F ≠ ∅. The empty string is accepted if the initial closure already meets F, which is why the initial closure is computed before the loop rather than inside it.

Both steps are unions of per-state contributions, so both are distributable over the elements of S. That is what makes a bitset representation natural: if state i is live, bit i of a machine word is set, and a union of contributions is a bitwise OR.

/* Bitset simulation. nstates <= 64 for this single-word version.
 * eclose[i] is the epsilon closure of state i as a bitmask. */
uint64_t closure_of(uint64_t m, const uint64_t *eclose)
{
    uint64_t r = 0, frontier = m;
    while (frontier) {
        uint64_t next = 0;
        for (uint64_t x = frontier; x; x &= x - 1)
            next |= eclose[__builtin_ctzll(x)];   /* lowest live state */
        next &= ~r;                               /* only states not yet in the closure */
        r |= next;
        frontier = next;
    }
    return r;
}

The inner loop iterates over set bits, not over all states, which matters when the live set is sparse. The set r is the part of the closure already known, and frontier holds states whose epsilon moves have not been applied yet. Each round either adds at least one state to r or leaves frontier empty, so the loop runs at most once per state in the closure. The iteration is necessary because the members of eclose[i] are themselves states whose own epsilon moves may still need applying; a single pass over the initial set would stop at the first level of the epsilon graph.

Why the closure step dominates

The per-symbol transition is a handful of ORs when the transition function is precomputed per state as a bitset. The closure is the expensive part, and its cost depends on how the epsilon moves are shaped.

For an NFA produced by the Thompson construction, epsilon edges form a graph whose structure mirrors the syntax tree, and closures are small: often a couple of states. For an NFA produced by a tool that chains many epsilon transitions, a closure can sweep most of the machine. The worst case is a single closure visiting every state, which is O(|Q|) work, repeated for every input symbol.

Precomputing the full closure of every state is the standard fix: an array of |Q| bitsets, each of |Q| bits, built once by transitive closure over the epsilon relation. The memory cost is |Q|² / 8 bytes, which is 125 KB for a 1,000-state machine and 12.5 MB for 10,000 states. The time saving is that the closure of a set becomes OR of the precomputed closures of its members, with no fixed-point iteration.

For large machines the precomputed matrix is too big, and the fixed-point loop is used with a per-symbol cache of closures already computed. Caching is sound because the closure is a pure function of the input set, and the number of distinct sets actually encountered during a scan is usually far smaller than 2^|Q|.

The subset construction, run lazily

The set-valued simulation is exactly the subset construction with the states materialized on demand. Each distinct S encountered becomes a state of an implicit DFA, and transitions between them are recorded as they are first taken. Nothing is enumerated in advance, so an NFA with n states costs O(n) memory to hold and the simulation costs O(n) per symbol in the worst case, rather than the 2^n table that the full construction would build.

This is the mechanism behind the classic regular-expression matcher: the pattern is compiled to an NFA with epsilon transitions, and matching runs the set simulation over the input, one set per character position. The construction from syntax tree to machine is covered in compiling a regular expression into an NFA; the simulation described here is what makes that construction usable without a determinization pass.

/* One step of the simulation: move on symbol a, then close. */
static uint64_t step(uint64_t s, uint8_t a,
                     const uint64_t *move,   /* [nstates][nsym] as bitsets */
                     const uint64_t *eclose)
{
    uint64_t m = 0;
    for (uint64_t x = s; x; x &= x - 1)
        m |= move[__builtin_ctzll(x) * NSYM + a];
    return closure_of(m, eclose);
}

The loop is over live states and each iteration does one indexed load and one OR. Its cost is proportional to the population count of the set, which is why a sparse live set is cheap even when the machine is large. The closure call is the part that can be hoisted into a table.

Where the representation breaks down

Sixty-four states fit one word. Beyond that, the set is an array of words and every operation becomes a loop over the array, so a machine with 4,096 states spends 64 word operations per union of two sets. The per-symbol move-and-close step stays proportional to the number of live words it touches, so a sparse live set in a large machine is still cheap, but the precomputed closure table and any full-set pass grow with the state count.

Sparse sets are the alternative when the live set is small relative to |Q|. A sorted array of live state indices makes iteration proportional to the set size, but union requires a merge, and membership tests require a search. A hash set gives constant-time membership but poor locality. The choice depends on whether the dominant operation is union across many states (favour bitset) or iteration over a small set (favour array).

There is a subtler problem with the lazy approach: the number of distinct sets encountered is bounded by 2^|Q| but is not bounded by anything smaller in general. An adversary can construct an NFA whose run visits an exponential number of distinct subsets, and then the lazy simulation’s cache grows without bound. In practice the cache is either dropped (recomputing closures each time, accepting the constant) or capped, at which point the simulation is no longer guaranteed to be faster than building the determinized table.

Epsilon cycles are the last hazard. A closure over a cycle of epsilon transitions still terminates because the fixed point is reached after finitely many additions, but a naive implementation that recurses on each epsilon edge will not terminate. The iterative union above is safe by construction; a recursive one needs an explicit visited set.

What the set representation costs and buys

The trade is memory against determinism. A DFA table costs |Q| · |Σ| entries and gives one dependent load per symbol. The NFA simulation costs O(|Q|) bits plus whatever closure data is cached, and gives one loop over live states plus a closure per symbol. For small machines the DFA wins outright. For large machines, especially ones built from many alternatives where the determinized version would explode, the simulation is the only option that fits in memory.

The simulation also preserves information the DFA discards: which alternatives are still viable. That is what allows a matcher to report the longest match, or all matches, or the position where each alternative began, without rerunning the machine. Keeping per-state capture positions is a matter of storing one extra field per live state and merging on union, and the merge rule is where the semantics of a particular matching dialect are decided.