邁希爾-尼羅德定理

在形式語言理論中，Myhill–Nerode 定理提供了一個語言是正則語言的必要和充分條件。它近乎專門的被用來證明一個給定語言不是正則的。

這個定理得名於 John Myhill 和 Anil Nerode，他們於1958年在芝加哥大學證明了這個定理。

定理陳述

給定一個字母集 (alphabet) $\Sigma$ 以及其生成的語言 (language) $L\subseteq \Sigma ^{*}$，我們先來定義兩個字串 $x,y\in \Sigma ^{*}$ 之間彼此的關係：如果對於所有的後接字串 $z\in \Sigma ^{*}$ (注意！$z$ 可以是空字串) 都會讓 $xz$ 和 $yz$ 同時屬於或不屬於 $L$，那麼我們說 $x$ 和 $y$ 不可區分 (indistinguishable)；相反地如果存在某個後接字串 $z\in \Sigma ^{*}$ 讓 $xz$ 和 $yz$ 其中一個屬於而另外一個不屬於 $L$，則我們說 $x$ 和 $y$ 是可區分的 (distinguishable)。如果 $x$ 和 $y$ 不可區分，我們說它們滿足關係 (relation) $R_{L}$，數學式子寫成 $x\ R_{L}\ y$。我們也很容易證明這種關係是種等價關係 (equivalence relation)，因此它可以把 $\Sigma ^{*}$ 劃分成一個或多個等價類 (equivalence class)。

Myhill–Nerode 定理聲稱一套語言 $L$ 是正規的「若且唯若」$\Sigma ^{*}$ 被 $R_{L}$ 所切分出的等價類數目是有限的，此外這個等價類數量又恰好是可辨識 $L$ 的最小 DFA 的狀態數量。在詳細的證明中「一個等價類會恰好對應到最小 DFA 裡的一個狀態」，如果先給定一個自動機，則任意兩個能驅使它走到同一個狀態的字串 $x$ 和 $y$ 必在同一個等價類中；如果先給定一個等價類劃分，那可以輕易地構造出一個自動機使其狀態恰好對應到等價類。

定理證明

• 方向一：如果 $\Sigma ^{*}$ 被 $R_{L}$ 所切分出的等價類數目是無限多的，那麼語言 $L$ 無法正規

這個方向比較簡單，我們只要證明一個引理 (lemma)：可辨識 $L$ 的 DFA 狀態數量必須不小於等價類數目即可，而這可以使用反證法 (鴿籠原理) 說明。如果 DFA 狀態數量少於等價類數量，那代表必定有兩個不屬於同一個等價類的字串 $x$ 和 $y$ 會引導 DFA 到同一個狀態，如果它們又繼續有後接字串 $z$，就會讓 $xz$ 和 $yz$ 也走到同一個狀態，如此一來根據定義，$x$ 和 $y$ 應該要屬於同一個等價類，造成矛盾，因此 DFA 狀態數量必須不小於等價類數目。由這個結論可以推得，當等價類數目無限多時，這個 DFA 的狀態數量也必須是無限多，和「有限」狀態機的定義矛盾，換句話說我們找不到一台 DFA 可辨識 $L$，因此 $L$ 不正規。

• 方向二：如果 $\Sigma ^{*}$ 被 $R_{L}$ 所切分出的等價類數目是有限的，那麼必存在一台同等數量狀態的 DFA 可辨識 $L$ 使其正規

我們先構造出一台 DFA，先假設它的每一個狀態都剛好代表一個等價類 (也就是一個狀態承裝一個等價類裡的所有字串，從起點開始輸入該字串務必到達該狀態)，而轉移函數的決定方式就是從一個狀態隨意抓取一個代表字串，看看它吃了一個字母之後的字串會落在哪個狀態裡面，就讓它走去那裏。這個走向會唯一，理由很簡單可以自己想。對於每個狀態和每個轉移字母都窮舉一遍，最後再觀察哪些狀態包含了被接受的字串，直接讓它們變成終點態 (final state)。一個等價類裡如果有一個字串被接受，那同一個類裡的所有其他字串也會通通被接受，因為根據定義，後接字串可以是空字串。到目前為止，我們有了一定數量的狀態 (圓圈圈)、所有的轉移函數、一個唯一的起點 (看空字串在哪裡即可)、所有的終點，是一台合法的 DFA。現在的問題是，要怎麼證明這台 DFA 能確實辨識 $L$，也就是說對於任意字串輸入都能驅使 DFA 走到我們當初賦予每個狀態必須各自代表一個等價類的任務？

這必須對字串輸入的長度作數學歸納法才能證明。如果字串輸入長度為 0，也就是空字串，那它必須留在起點，而我們起點的取法就剛好是看空字串的位置，所以輸入為空字串時的狀態落點正確；如果對於所有長度不超過 $\ell$ 的字串輸入，它們的狀態落點皆正確，那麼對於任何長度為 $\ell +1$ 的字串輸入 $w$，皆可分解為 $w=ua$，其中 $u$ 的長度為 $\ell$ 而 $a$ 的長度為 $1$ (字元)，走完 $u$ 之後的落點根據假設是正確的，剩下的一個字元 $a$ 根據我們上述決定轉移函數的方式，自然也會繼續走向我們當初所期望的落點；如此依序遞迴下去，就能說明對於任意字串輸入，這台 DFA 確實能妥善的把 $\Sigma ^{*}$ 裡的每個字串分到正確的類別，並決定接受與否。於是乎我們根據這個 $R_{L}$ 創造了一台能辨識 $L$ 的 DFA，而且這台 DFA 的狀態數量剛好就是 $\Sigma ^{*}$ 被 $R_{L}$ 所切分出的等價類數量。

用途和結論

Myhill–Nerode 定理的一個結論是語言 L 是正則的(就是說可被有限狀態機接受)，若且唯若 R_L 的等價類的數目是有限的。

直接推論是如果一個語言定義等價類的無限集合，它就不是正則的。這個推論經常被用來證明一個語言不是正則的。

例如，由可以被 3 整除的二進制數組成的語言是正則的。有三個等價類 3 - 被 3 除的時候餘數是 0, 1 和 2 的數。接受這個語言的極小自動機有對應於等價類的三個狀態。

再給一例，我們想說明 $A=\{0^{n}1^{n}:n\geq 0\}$ 不是正規的。原因是，給定任意兩個不同長度的 $0$ 字串，我們都能接上一個後接字串將這兩個字串分辨開來，舉例來說，給定 $000$ 和 $00000$，我們就能接上 $111$ 讓 $000111$ 合法而 $00000111$ 不合法。所以有無限多個字串 $0$、$00$、$000$、$0000$、... 等彼此之間都是可分辨的，這意味著需要無限多個狀態的自動機才能辨識這個語言，和正規語言定義矛盾，因此 $A$ 不是正規語言。

引用

一般參考

• John E. Hopcroft and Jeffrey D. Ullman, Introduction to Automata Theory, Languages and Computation, Addison-Wesley Publishing, Reading Massachusetts, 1979. ISBN 0-201-02988-X. (See chapter 3.)
• Tom Henzinger, Lecture 7: Myhill–Nerode Theorem (2003)