迈希尔-尼罗德定理

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

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

定理陈述给定一个语言L，定义在字符串上一个关系RL，通过规则x RLy如果没有有区别扩展z，它带有字符串xz和yz之中严格的有一个在L中的性质。容易证明RL是字符串上的等价关系，因此它把所有有限字符串的集合划分成一个或多个等价类。

Myhill–Nerode 定理声称在接受L的最小自动机中状态的数目等于在RL中等价类的数目。直觉是如果以这样一个极小自动机作为开始，则驱使它到相同状态的任何字符串x和y将在同一个等价类中；而且如果以等价类划分作为开始，可以轻易的构造出一个自动机使用它的状态来跟踪包含字符串迄今已经看到部分的等价类。

用途和结论Myhill–Nerode 定理的一个结论是语言L是正则的(就是说可被有限状态机接受)，当且仅当RL的等价类的数目是有限的。

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

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

参考形式语言

本词条内容贡献者为:

张尉 - 副教授 - 西南大学