迈希尔－尼罗德定理

在形式语言理论中，Myhill–Nerode 定理提供了一个语言是正则语言的必要和充分条件。它近乎专门的被用来证明一个给定语言不是正则的。

这个定理得名于 John Myhill 和 Anil Nerode，他们于1958年在芝加哥大学证明了这个定理。

给定一个字母集 (alphabet) ${\displaystyle \mathrm{\Sigma <!--\; \Sigma \; -->}}$ 是正则的(就是说可被有限状态机接受)，当且仅当 的等价类的数目是有限的。

直接推论是如果一个语言定义等价类的无限集合，它就不是正则的。这个推论经常被用来证明一个语言不是正则的。

例如，由可以被 3 整除的二进制数组成的语言是正则的。有三个等价类 3 - 被 3 除的时候余数是 0, 1 和 2 的数。接受这个语言的极小自动机有对应于等价类的三个状态。

再给一例，我们想说明 ${\displaystyle A=\{0^n{1}^n:n\ge <!--\; \ge \; -->0\}}$ 不是正规的。原因是，给定任意两个不同长度的 ${\displaystyle 0}$ 字串，我们都能接上一个后接字串将这两个字串分辨开来，举例来说，给定 ${\displaystyle 000}$ 和 ${\displaystyle 00000}$，我们就能接上 ${\displaystyle 111}$ 让 ${\displaystyle 000111}$ 合法而 ${\displaystyle 00000111}$ 不合法。所以有无限多个字串 ${\displaystyle 0}$、${\displaystyle 00}$、${\displaystyle 000}$、${\displaystyle 0000}$、... 等彼此之间都是可分辨的，这意味着需要无限多个状态的自动机才能辨识这个语言，和正规语言定义矛盾，因此 ${\displaystyle A}$ 不是正规语言。