◄ WORLD V · SONNY 5DART 131 · a helldive at the net

SUBSET CONSTRUCTION a set of NFA states is one DFA state

An NFA can be in many states at once. The subset (powerset) construction makes it deterministic by treating the whole set of possible states as a single DFA state: start from the start set, and on each symbol take the union of every current state’s targets. It proves nondeterminism buys no extra power — at the cost of up to 2n states, though most NFAs stay small.

THE TECHNIQUE union of targets, as a bitmask

NFA for (a|b)*a: q0 (start), q1 (accept), δ(q0,a)={q0,q1}, δ(q0,b)={q0}. Encode a state-set as a bitmask (q0=1, q1=2). On each symbol, OR the targets of every live state. A set accepts if it contains q1. The construction visits only 2 reachable subsets of the 4 possible. Type a/b; watch the subset walk. live demo







  
HISTORY & CREDIT the award was for nondeterminism itself

  
“The subset construction is Kleene’s” — no; Kleene (1956) equated regex and deterministic automata, with no notion of nondeterminism. It is Rabin & Scott, 1959. cited

  

    1957/58 · Myhill-Nerode characterise the unique minimal DFA — minimization, a separate result from determinization.

    1959 · Rabin & Scott invent the NFA and prove NFA ≡ DFA by the subset construction (IBM J. Res. Dev. 3(2)).

    1971 · Hopcroft — the n log n minimization that usually follows determinization (regex → NFA → DFA → minimal DFA).

    1976 · the Turing Award to Rabin & Scott cites the invention of nondeterminism and the paper’s decision-problem results — reducing it to “the subset construction” undersells what was prized.
  

  
2n is a worst case, not the rule — most NFAs determinize small; RE2/Go/Rust build the DFA lazily at match time (a cached subset construction). Rabin & Scott, 1959






  
RECOMMEND FOR I-13 a subset is one integer; delta is a flat array

  
A subset-state is one f64 bitmask; the transition is a flat f64 array indexed by state*2+symbol; the DFA runs on the real compiler:

  
$ i13 run subset.i13   # (a|b)*a ; delta=[3,1,0,0], accept mask = 2
"abba" -> subset trail 1 -> 3 -> 1 -> 1 -> 3 ; final 3 & 2 = 2 -> ACCEPT
"abb"  -> 1 -> 3 -> 1 -> 1 ; final 1 & 2 = 0 -> REJECT   (2 reachable subsets of 4)

  

    Recommend: nothing new — a subset-state is a single f64 bitmask (up to 63 NFA states, since the VM computes bitwise as i64); the transition relation δ is a flat f64 array read at state*2+sym; a DFA step is an OR of the live states’ targets; accept is one AND (verified abba ACCEPT via final mask 3, abb REJECT via mask 1). It is the on-the-fly / lazy form — exactly what RE2 does.

    Note: pairs with Thompson (130): 130 builds the NFA and simulates it, 131 determinizes it — the two halves of regex → NFA → DFA. A full δ for many states is a 2-D array (PS-004) flattened here to 1-D by hand, the corpus’s standing move.