THE FOLD / SPAWN / HELLO WORLD / THE HOPCROFT
THE HOPCROFT
the minimal DFA by merging indistinguishable states
1 WHAT IT IS · WHAT IT DOES · FACT OR FICTION
Hopcroft’s algorithm minimises a deterministic finite automaton — it finds the smallest DFA recognising the same language. It works by partition refinement: begin by splitting accepting from non-accepting states, then repeatedly split any group whose members transition into different groups, until stable. The final classes are the Myhill–Nerode equivalence classes — states no string can tell apart, merged into one. Hopcroft’s trick of always splitting by the smaller half gives O(n log n).
LIT verified live: over 200 random DFAs the minimised automaton accepts the same language (all strings up to length 6) and is truly minimal — every pair of its states is distinguishable (window.__hopcroft). FIG no framing; exact.
LIT verified live: over 200 random DFAs the minimised automaton accepts the same language (all strings up to length 6) and is truly minimal — every pair of its states is distinguishable (window.__hopcroft). FIG no framing; exact.
2 HOW IT WAS WEAVED · AI + HUMAN
David (human) seated this at hello-world — the first thing a language needs is to recognise its own words, and Hopcroft shrinks that recogniser to the smallest possible machine, beside the CYK parser. AVAN (AI) built the instrument: the partition-refinement worklist, the merged minimal DFA, the language-equivalence and distinguishability checks.
Credit as content: John Hopcroft (1971). The weave: David names hello-world; I merge every pair of states no string separates and confirm the result is minimal and language-equivalent.
Credit as content: John Hopcroft (1971). The weave: David names hello-world; I merge every pair of states no string separates and confirm the result is minimal and language-equivalent.
3 ONE DIMENSION
Start with two blocks (accepting / non-accepting). Split any block whose states, on some symbol, jump to different blocks. Repeat until no split is possible — the blocks are the minimal states.
4 TWO DIMENSIONS · INTERACTIVE
A DFA and its minimised form; equivalent states are merged, the language preserved, and every remaining state is distinguishable.
5 THREE DIMENSIONS + AVAN’S INVERSE
The green forward object: the minimal state set — the Myhill–Nerode classes.
AVAN’s addition (the inverse-companion): merge states that are indistinguishable — start by splitting accepting from non-accepting, then split any group whose members transition into different groups, until stable; the resulting classes are the minimal DFA. The inverse of ‘build a DFA state per situation’ is ‘merge all states no string can tell apart.’ Magenta is the redundant equivalent states collapsed; green is the minimal state set. Splitting by the smaller half gives O(n log n) — indistinguishability is the equivalence.
LIT Genuine Hopcroft DFA minimization (Hopcroft 1971). Verified live: the partition-refinement minimization yields a DFA that accepts the same language as the original on all strings up to length 6, and every pair of states in the minimized DFA is distinguishable (truly minimal), across 200 random DFAs (window.__hopcroft.sameLanguage && .minimal).
FIG No framing: the partition-refinement worklist, the merged minimal DFA, and the language-equivalence + distinguishability checks run in-browser and hold. The AVAN inverse is honest — merging states no string can tell apart (refine until stable) yields the minimal DFA, the Myhill-Nerode classes; magenta is the redundant equivalent states collapsed, green the minimal state set. Splitting by the smaller half gives O(n log n).
FIG No framing: the partition-refinement worklist, the merged minimal DFA, and the language-equivalence + distinguishability checks run in-browser and hold. The AVAN inverse is honest — merging states no string can tell apart (refine until stable) yields the minimal DFA, the Myhill-Nerode classes; magenta is the redundant equivalent states collapsed, green the minimal state set. Splitting by the smaller half gives O(n log n).
◆ sealed .dlw.fold → folded to ROOT_0 · a sphere of HELLO WORLD · David Lee Wise (ROOT0), with AVAN