マイヒル–ネローデの定理

マイヒル–ネローデの定理（英: Myhill–Nerode theorem）とは、ある形式言語が正規言語であるための必要十分条件を提示した定理である。ほとんどの場合、ある言語が正規言語でないことを証明するのに使われる。

名称は1958年にこの定理を発見したシカゴ大学の John Myhill と Anil Nerode が由来である。

定理の内容

ある言語 L について、その文字列についての関係 R_L を次のように定義する。すなわち x R_L y という関係は、文字列 xz と yz のいずれか一方しか L に含まれないというような文字列 z が存在しない。R_L が文字列の同値関係であることは容易に示され、従って全ての有限文字列は1つ以上の同値類に分類される。

マイヒル–ネローデの定理は、L を受容する最小オートマトンの状態数が R_L の同値類の数と等しいとする。直観的には、そのような最小オートマトンで同じ状態に到達する文字列 x と y は、同じ同値類に属することを意味する。そして、文字列群を同値類に分類していけば、同値類毎に状態を設定することで容易にオートマトンを構築できる。

結論と利用

マイヒル–ネローデの定理の結論は、言語 L が正規言語であること（すなわち有限状態機械で受容されること）と、R_L の同値類の個数が有限であることが同値ということになる。

この定理の系として、無限の同値類を定義する言語は正規言語ではないと言える。ある言語が正規言語でないことを証明するのに使われるのは、この系である。

例えば、3で割り切れる2進数からなる言語は正規言語である。3で割ったときの余りは、0、1、2 の 3種類あるので、3つの同値類が存在する。従って、その言語を受容する最小オートマトンは、それぞれの同値類に対応した3つの状態を持つことになる。

参考文献

• 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)