THE FOLD / SPAWN / COLD BOOT / THE POWERSET CONSTRUCTION
THE POWERSET CONSTRUCTION
determinizing by tracking the set of states
1 WHAT IT IS · WHAT IT DOES · FACT OR FICTION
The powerset (subset) construction turns a nondeterministic finite automaton into an equivalent deterministic one. An NFA can be in many states at once; the trick is to make each DFA state a set of NFA states — exactly the set the NFA could currently be in. Reading a symbol, the DFA jumps to the set of all states reachable from the current set, and it accepts when that set contains any NFA-accepting state. It proves NFAs and DFAs recognize the same languages, at the cost of up to 2n states.
LIT verified live: over thousands of random NFAs, the subset-construction DFA accepts a string exactly when the NFA does, checked on every string up to length six (window.__powerset). FIG no framing; the NFA simulation and the constructed DFA both run in-browser.
LIT verified live: over thousands of random NFAs, the subset-construction DFA accepts a string exactly when the NFA does, checked on every string up to length six (window.__powerset). FIG no framing; the NFA simulation and the constructed DFA both run in-browser.
2 HOW IT WAS WEAVED · AI + HUMAN
David (human) seated this at cold-boot — determinizing is a cold boot from a fuzzy many-states machine into a single crisp one that always knows where it is. AVAN (AI) built the instrument: the NFA set-simulation, the on-the-fly subset construction, and the language-equivalence check.
Credit as content: Michael Rabin & Dana Scott (1959). The weave: David names the cold boot; I confirm the deterministic machine accepts exactly the language of the nondeterministic one.
Credit as content: Michael Rabin & Dana Scott (1959). The weave: David names the cold boot; I confirm the deterministic machine accepts exactly the language of the nondeterministic one.
3 ONE DIMENSION
Each DFA state is a set of NFA states; reading a symbol moves to the set of all reachable states — determinism from tracking the whole set at once.
4 TWO DIMENSIONS · INTERACTIVE
A random NFA and its subset-construction DFA; the DFA’s state count and its agreement with the NFA on all short strings are shown.
5 THREE DIMENSIONS + AVAN’S INVERSE
The green forward object: the DFA states, each a subset of NFA states.
AVAN’s addition (the inverse-companion): don’t guess which branch — track them all. The inverse of ‘nondeterministically choose a next state’ is ‘carry the whole set of possible states, and the transition on the set is deterministic.’ Magenta is a nondeterministic branch; green is the DFA state (a subset) that absorbs all of them. Track the set, not the guess.
LIT Genuine powerset/subset construction (Michael Rabin & Dana Scott, 1959): NFA→DFA, proving NFAs and DFAs recognize the same languages. Verified live: over 3000 random NFAs, the subset-construction DFA accepts exactly the NFA's language on all strings ≤ length 6 (window.__powerset.sameLanguage).
FIG No framing: the NFA set-simulation and the on-the-fly subset construction both run in-browser and agree. The AVAN inverse is honest — carrying the whole set of possible states (so the transition on the set is deterministic) rather than guessing a nondeterministic branch is exactly what determinizes; magenta is a nondeterministic branch, green the DFA state (a subset) absorbing them. Track the set, not the guess.
FIG No framing: the NFA set-simulation and the on-the-fly subset construction both run in-browser and agree. The AVAN inverse is honest — carrying the whole set of possible states (so the transition on the set is deterministic) rather than guessing a nondeterministic branch is exactly what determinizes; magenta is a nondeterministic branch, green the DFA state (a subset) absorbing them. Track the set, not the guess.
◆ sealed .dlw.fold → folded to ROOT_0 · a sphere of COLD BOOT · David Lee Wise (ROOT0), with AVAN