マイヒル・ネロードの定理

形式言語 の理論において、マイヒル・ネロードの定理は、言語が正規言語であるための必要十分条件を提供する。この定理は、 1957年にシカゴ大学でそれを証明したジョン・マイヒルとアニル・ネロードにちなんで名付けられた。^{[ 1 ]}

言語が与えられた場合${\displaystyle L}$そして一対の弦${\displaystyle x}$そして${\displaystyle y}$文字列として識別拡張を定義する ${\displaystyle z}$2つの文字列のうちちょうど1つだけ${\displaystyle xz}$そして${\displaystyle yz}$に属する${\displaystyle L}$関係を定義する$\displaystyle \sim _{L}}$文字列として${\displaystyle x\;\sim _{L}\ y}$区別する拡張がない場合${\displaystyle x}$そして${\displaystyle y}$簡単に示すことができるのは、$\displaystyle \sim _{L}}$は文字列上の同値関係であり、したがってすべての文字列の集合を 同値類に分割します。

マイヒル・ネロードの定理によれば、言語は${\displaystyle L}$正規であるのは、$\displaystyle \sim _{L}}$同値類の数が有限であり、さらに、この数は受理する最小決定性有限オートマトン（DFA）の状態数に等しい。${\displaystyle L}$さらに、その言語のすべての最小DFAは、標準的なDFAと同型である。^{[ 2 ]}

一般的に、どの言語においても、構築されたオートマトンが状態オートマトン受理器となる。しかし、必ずしも有限個の状態を持つとは限らない。マイヒル・ネロードの定理は、言語の規則性にとって有限性が必要十分条件であることを示している。

一部の著者は、${\displaystyle \sim _{L}}$アニル・ネロデに敬意を表して、ネロデの合同としての関係^{[ 3 ] [ 4 ]}。

マイヒル・ネロードの定理は、言語が${\displaystyle L}$同値類の数を証明することによって正則である。${\displaystyle \sim _{L}}$は有限です。これは、空文字列から始めて、識別拡張を使用して追加の同値類を見つけ、それ以上見つからなくなるまで、網羅的な場合分け分析によって行うことができます。

例えば、3で割り切れる数の二進数表現からなる言語は正規言語である。2つの二進数文字列が与えられた場合、${\displaystyle x,y}$1桁増やすと${\displaystyle 2x+b,2y+b}$、 それで${\displaystyle 2x+b\equiv 2y+b\mod 3}$もし${\displaystyle x\equiv y\mod 3}$。 したがって、${\displaystyle 00}$（または${\displaystyle 11}$)${\displaystyle 01}$、 そして${\displaystyle 10}$これらが唯一の区別となる拡張であり、結果として3つのクラスが導き出される。我々の言語を受理する最小オートマトンには、これら3つの同値クラスに対応する3つの状態が存在する。

この定理のもう一つの直接的な帰結は、言語に対して${\displaystyle L}$関係${\displaystyle \sim _{L}}$同値類が無限に存在する場合、それは正規言語ではない。この系は、言語が正規言語ではないことを証明するためによく用いられる。

マイヒル・ネロードの定理は木オートマトンに一般化できる。^{[ 5 ]}

• 正規言語に対するポンピング補題：言語が正規言語ではないことを証明する代替手法。ただし、ポンピング補題は必ずしも言語が正規言語ではないことを証明できるとは限らない。
• 構文モノイド