マイヒル–ネローデの定理
マイヒル–ネローデの定理の結論は、言語 L が正規言語であること(すなわち有限状態機械で受容されること)と、RL の同値類の個数が有限であることが同値ということになる。
この定理の系として、無限の同値類を定義する言語は正規言語ではないと言える。ある言語が正規言語でないことを証明するのに使われるのは、この系である。
例えば、3で割り切れる2進数からなる言語は正規言語である。3で割ったときの余りは、0、1、2 の 3種類あるので、3つの同値類が存在する。従って、その言語を受容する最小オートマトンは、それぞれの同値類に対応した3つの状態を持つことになる。