Myhill-Nerode 定理（Myhill-Nerode theorem）
/ Myhill: MY-hill; Nerode: neh-ROH-dee /
Myhill-Nerode 定理是對「哪些語言是正規的？」的精確「雙向」回答，而幫浦引理只是單向的。其想法是：對一個固定的語言 L，問「讀完某個前綴後，一位讀者可能處於多少種『真正不同』的處境」。若有限多種處境就夠用，你便能建一台「每種處境一個狀態」的 DFA；若需要無窮多種，沒有任何有限自動機追蹤得了，於是 L 不是正規的。
把「處境」說精確。對 L 而言，兩個字串 x 與 y 是「不可區分的」，若對「每一個」續接 z，xz 屬於 L 正好當 yz 屬於 L——無論接下來是什麼，它們的「未來」都相同。這是一個等價關係，把 Σ*（所有字串）分成若干類；類的數目稱為 L 的指數（index）。定理斷言：L 是正規的「若且唯若」這個關係有「有限多」個類（有限指數）。此外，當 L 是正規的，類的數目「等於」最小 DFA 的狀態數——因此這條定理同時刻畫了正規性、並釘住了確切的最小機器。
這給了兩件強大而精確的工具。要證明 L 非正規，拿出一個「兩兩可區分」的無窮字串族（每一對都有某個見證 z 把它們分開）——無窮多個類就代表非正規，而且與幫浦引理不同，當語言確實非正規時這「永不」失手。要找最小的 DFA，數出或建出這些等價類；每一類成為一個狀態。本定理以 John Myhill 與 Anil Nerode 命名。
對 a^n b^n，字串 a^0、a^1、a^2、… 兩兩可區分：a^i 與 a^j（i ≠ j）用 z ＝ b^i 分開，因為 a^i b^i 屬於 L、但 a^j b^i 不屬於。無窮多個類 ⇒ 非正規。對「偶數個 a」，只有「兩」個類（目前偶數、目前奇數）⇒ 正規，最小 DFA 有 2 個狀態。
有限指數 ⇔ 正規；類的數目正好是最小 DFA 的狀態數。
Myhill-Nerode 既必要又充分——它精確地刻畫正規性，因此不像幫浦引理那樣會給出假結果。這個等價關係是定義在「字串」上的（語言的右同餘），而非任何特定機器的狀態上。