邁希爾-尼羅德定理(邁希爾-尼羅德定理)

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

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

基本介紹

• 中文名：邁希爾-尼羅德定理
• 外文名：Myhill–Nerode 定理
• 用途：證明一個給定語言不是正則的
• 提出者： John Myhill 和 Anil Nerode
• 時間：1958年
• 提出地點：芝加哥大學

定理陳述

給定一個語言L，定義在字元串上一個關係R_L，通過規則x R_Ly如果沒有有區別擴展z，它帶有字元串xz和yz之中嚴格的有一個在L中的性質。容易證明R_L是字元串上的等價關係，因此它把所有有限字元串的集合劃分成一個或多個等價類。

Myhill–Nerode 定理聲稱在接受L的最小自動機中狀態的數目等於在R_L中等價類的數目。直覺是如果以這樣一個極小自動機作為開始，則驅使它到相同狀態的任何字元串x和y將在同一個等價類中；而且如果以等價類劃分作為開始，可以輕易的構造出一個自動機使用它的狀態來跟蹤包含字元串迄今已經看到部分的等價類。

用途和結論

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

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

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

參考

• 形式語言
  

套用

求證：語言L = 0^n 1^n不是正則語言。

證明：考察001，0001，00001，……

注意到第i個字元串加上i個1後屬於L，而第i個字元串加上j個1後不屬於L（i與j不相等）。

因此，在等價關係下，這一列字元串屬於不同的等價類。由Myhill–Nerode 定理，語言L不是正則表達式。證畢。