THE FOLD / CO-OP / THE MERGE / THE MYHILL-NERODE
THE MYHILL-NERODE
the fewest states a language needs
1 WHAT IT IS · WHAT IT DOES · FACT OR FICTION
The Myhill–Nerode theorem pins down the fewest states a language needs. Call two strings equivalent if no continuation ever tells them apart — for every suffix z, xz and yz are both in the language or both out. The theorem says the number of such equivalence classes equals the number of states in the minimal DFA, and a language is regular exactly when that number is finite. So minimizing an automaton is just merging states no string can distinguish.
LIT verified live: over thousands of random DFAs, the minimized machine accepts the same language as the original on all short strings, and it is truly minimal — every pair of its states is separated by some string (window.__myhill). FIG no framing; the minimization and the distinguishability checks run in-browser.
LIT verified live: over thousands of random DFAs, the minimized machine accepts the same language as the original on all short strings, and it is truly minimal — every pair of its states is separated by some string (window.__myhill). FIG no framing; the minimization and the distinguishability checks run in-browser.
2 HOW IT WAS WEAVED · AI + HUMAN
David (human) seated this at the-merge — minimization is a merge: fold together every pair of states that behave the same on all futures, until only distinguishable ones remain. AVAN (AI) built the instrument: partition-refinement minimization, a language-equivalence check, and a pairwise distinguishability test.
Credit as content: John Myhill & Anil Nerode (1958). The weave: David names the merge; I confirm the merged machine accepts the same language and that no two of its states can still be told apart.
Credit as content: John Myhill & Anil Nerode (1958). The weave: David names the merge; I confirm the merged machine accepts the same language and that no two of its states can still be told apart.
3 ONE DIMENSION
Two states that no string can distinguish are the same class — merge them; repeat until every remaining pair is separable.
4 TWO DIMENSIONS · INTERACTIVE
A random DFA coloured by equivalence class; the minimized machine keeps one state per class and accepts the identical language.
5 THREE DIMENSIONS + AVAN’S INVERSE
The green forward object: the minimal machine, one state per equivalence class.
AVAN’s addition (the inverse-companion): don’t track states — track what strings can tell apart. The inverse of ‘how many states?’ is ‘how many futures behave differently — that count is the minimal state count.’ Magenta is a distinguishable pair; green is a merged class. States are just distinguishable futures.
LIT Genuine Myhill–Nerode theorem (John Myhill & Anil Nerode, 1958): #equivalence-classes of the indistinguishability relation = #states of the minimal DFA; finite ⟺ regular. Verified live: over 2000 random DFAs, the minimized machine accepts the same language on all strings up to length 6 (window.__myhill.sameLanguage) and every pair of its states is distinguishable (.minimal).
FIG No framing: partition-refinement minimization, a language-equivalence check, and a pairwise distinguishability test all run in-browser. The AVAN inverse is honest — counting distinguishable futures (rather than states) gives the minimal state count directly, which is the theorem's content; magenta is a distinguishable pair kept apart, green a merged class. States are just distinguishable futures.
FIG No framing: partition-refinement minimization, a language-equivalence check, and a pairwise distinguishability test all run in-browser. The AVAN inverse is honest — counting distinguishable futures (rather than states) gives the minimal state count directly, which is the theorem's content; magenta is a distinguishable pair kept apart, green a merged class. States are just distinguishable futures.
◆ sealed .dlw.fold → folded to ROOT_0 · a sphere of THE MERGE · David Lee Wise (ROOT0), with AVAN