マイヒル–ネローデの定理
ある言語 L について、その文字列についての関係 RL を次のように定義する。すなわち x RL y という関係は、文字列 xz と yz のいずれか一方しか L に含まれないというような文字列 z が存在しない。RL が文字列の同値関係であることは容易に示され、従って全ての有限文字列は1つ以上の同値類に分類される。
マイヒル–ネローデの定理は、L を受容する最小オートマトンの状態数が RL の同値類の数と等しいとする。直観的には、そのような最小オートマトンで同じ状態に到達する文字列 x と y は、同じ同値類に属することを意味する。そして、文字列群を同値類に分類していけば、同値類毎に状態を設定することで容易にオートマトンを構築できる。