為何需要一件更鋒利的工具
到現在，你已經能揮舞幫浦引理去證明一個語言不是正規的，也見識過那個惱人的陷阱：它必要、卻不充分。通過了幫浦測試什麼也證明不了——存在一些幫浦引理抓不到的非正規語言，所以一句乾淨的「它能被幫浦」只會把你丟回原地。我們手上這件工具有時會說「不」，卻從不會誠實地說「是」。這種不對稱讓人不舒服。我們真正想要的，是一條能正反兩面都判定正規性的單一準則。
Myhill-Nerode 定理正是這條準則。它不去戳弄某一台機器、某一段被幫浦的子字串，而是退一步、對語言本身發問：一位讀者在吞下輸入的某個前綴之後，能處於多少種「真正不同」的處境？若答案是個有限的數，這語言就是正規的；若答案是無窮，它就不是。發問時不需要任何機器，而答案是一條若且唯若（iff）。
關鍵想法：兩個前綴何時共享同一個未來？
想像一道旋轉閘門，已經讀了某個前綴，正等著剩下的輸入。關於它的過去，唯一要緊的事是：哪些「續接」最終會導向接受？相對於一個語言 L，若兩個前綴 x 與 y 滿足「對每一個可能的續接字串 z，判決都一致」——也就是說，對所有 z，『xz 屬於 L』與『yz 屬於 L』總是同進同退——我們就說它們不可區分。這就是字串不可區分關係。只要有任何一個續接 z 把它們分開（xz 被接受卻 yz 被拒，或反之），x 與 y 就是可區分的，而 z 就是把它們認出來的見證。
不可區分是 Sigma-star（字母表上所有字串的集合）上的一個等價關係，所以它把每個字串切成一個個等價類：每一類都是一束「共享同一個未來」的前綴。它還有一個俐落的性質，叫做右不變（就是右不變關係的想法）：若 x 與 y 不可區分，那麼在兩者末端各黏上同一個符號——xa 與 ya——它們依然不可區分。正是這一點，讓一台有限機器能一次一個符號地往後接，卻永遠不必記得自己究竟讀過哪個確切的前綴，只需記得自己落在哪一類裡。
數一數未來：語言的指數
現在來數這些等價類。不可區分類的個數，稱為這個語言的指數（語言的指數）。Myhill-Nerode 定理把它陳述成一條乾淨的等價：一個語言 L 是正規語言，若且唯若它的指數是有限的。有限多個不同的未來，意味著一台機器頂多需要有限多個狀態；無窮多個不同的未來，則意味著任何有限的記憶都無法把它們分得開。更妙的是，這條定理是定量的——指數恰好等於 L 的最小可能 DFA 的狀態數。
讓我們在一個小例子上看它如何兩面開鋒：L = 在 {a, b} 上、含偶數個 a 的字串，這正是你早在 DFA 那一階為它設計過 DFA 的語言。有幾個未來呢？讀完任一前綴後，唯一能改變判決的事，就是你迄今看過的 a 的個數是偶是奇。兩個同奇偶的前綴不可區分（任何續接都把兩者朝同方向翻）；兩個不同奇偶的前綴，則被——比方說——z = epsilon（若語言要的是偶）或末端再接一個 'a' 給區分開。所以恰好有兩類——偶與奇——指數是 2，而最小 DFA 也確實有 2 個狀態。
現在拿那個經典反派 L = a^n b^n（先若干個 a 再等量的 b）來跑跑看——它正是本階稍早證明非正規性裡的那個語言。看看前綴 a、aa、aaa、…、a^i、…。它們之中有任何兩個不可區分嗎？取 a^i 與 a^j，其中 i 不等於 j。接上續接 z = b^i。那麼 a^i b^i 屬於 L，但 a^j b^i 不屬於（個數對不上）。所以每一個不同次方的 a 都自成一類——無窮多類、指數無窮、不是正規的。請注意：這是一句誠實的「是／否」判決，而幫浦引理頂多只能交出其中一半。
為何有限多類就能換來一台機器
「只有當」這個方向（正規推出有限指數）很快：一台有 k 個狀態的 DFA，會依每個前綴最終停在哪裡，把它分進 k 個桶之一，而停在同一狀態的前綴必定不可區分，因為從那一刻起機器的行為一模一樣。所以指數至多是 k——有限。「若」這個方向才是魔法所在：從一個有限的類集合，你能在沒有任何現成 DFA 的情況下「造」出一台機器。這個建構是定理的核心，讓我們走一遍。
- 為每一個不可區分類各設一個狀態。因為指數有限，這是個有限的狀態集——把前綴 x 所屬的類叫做盒子 [x]。
- 起始狀態是空字串的類 [epsilon]——也就是還沒讀任何符號前的處境。
- 用「末端接一個符號」來定義轉移：delta([x], a) = [xa]。右不變性正是讓這個定義「良好」（well-defined）的關鍵——若你從同一類裡改挑了另一個代表 y，[ya] 也會是同一個盒子，所以這個移動不取決於你恰好點名的是哪個前綴。
- 當一個類裡的字串屬於 L 時，就把該類標為接受。由前面 z = epsilon 的提醒，同一類裡的每個字串對「屬不屬於 L」都一致，所以「這一類是接受的嗎？」是個前後一致、答得出來的問題。
- 把任何輸入餵進這台機器，它就在一個個類之間行走；它停在接受類，恰恰當整個輸入屬於 L。所以這台機器辨識 L——而且它恰好有「指數那麼多」個狀態。
這裡有一股令人滿足的鴿籠味，正是當初驅動幫浦引理的同一條鴿籠原理。有限的狀態意味著有限多個鴿籠；若一個語言真的需要分辨無窮多種處境，必有某兩個確實不同的前綴被迫共用一個籠子，於是一個本該把它們分開的續接卻辦不到——矛盾。Myhill-Nerode 不過是把鴿籠講精確了：它們「就是」那些等價類，不多也不少。
最小機器是免費附贈的
上一節造出的機器，不只是 L 的「某一台」DFA——它是「最小」的那台。任何辨識 L 的 DFA 至少需要每類一個狀態（它的狀態數不可能少於它必須分辨開的未來數），而 Myhill-Nerode 機器恰好每類用一個狀態，所以無物能勝過它。更棒的是，這台最小機器在「重新命名狀態」的意義下是唯一的——每一台達到最小的 DFA，本質上都是同一張圖換了不同標籤。正是這份唯一性，讓「那台最小 DFA」成為一句有意義的話，而不只是「某台最小 DFA」。
這就是通往本階下一篇、也是最後一篇導覽的大門。實務上你很少從抽象的類出發；你通常手上早有某台 DFA——也許是子集合建構法吐出來的一台臃腫貨——而你想把它縮小。DFA 最小化靠的正是 Myhill-Nerode 的鏡像：它反覆把「結果證明彼此不可區分」的狀態併在一起，直到只剩下真正不同的狀態。存活下來的，恰恰是定理所描述的那個類結構——Myhill-Nerode 定理證明了終點存在且唯一，最小化則是把你領到那裡的演算法。