迈希尔－尼罗德定理

在形式语言理论中，Myhill–Nerode 定理提供了一个语言是正则语言的必要和充分条件。它近乎专门的被用来证明一个给定语言不是正则的。这个定理得名于 John Myhill 和 Anil Nerode，他们于1958年在芝加哥大学证明了这个定理。给定一个语言L，定义在字符串上一个关系RL，通过规则x RLy如果没有有区别扩展z，它带有字符串xz和yz之中严格的有一个在L中的性质。容易证明RL是字符串上的等价关系，因此它把所有有限字符串的集合划分成一个或多个等价类。