Myhill-Nerode定理
维基百科，自由的百科全书
在形式语言理论中，Myhill–Nerode 定理提供了一个语言是正则语言的必要和充分条件。它近乎专门的被用来证明一个给定语言不是正则的。
这个定理得名于 John Myhill 和 Anil Nerode，他们于1958年在芝加哥大学证明了这个定理[1]。
[编辑] 定理陈述
给定一个语言 L，定义在字符串上一个关系 RL，通过规则 x RL y 如果没有有区别扩展 z，它带有字符串xz 和 yz 之中严格的有一个在 L 中的性质。容易证明 RL 是字符串上的等价关系，因此它把所有有限字符串的集合划分成一个或多个等价类。
Myhill–Nerode 定理声称在接受 L 的最小自动机中状态的数目等于在 RL 中等价类的数目。直觉是如果以这样一个极小自动机作为开始，则驱使它到相同状态的任何字符串 x 和 y 将在同一个等价类中；而且如果以等价类划分作为开始，可以轻易的构造出一个自动机使用它的状态来跟踪包含字符串迄今已经看到部分的等价类。
[编辑] 用途和结论
Myhill–Nerode 定理的一个结论是语言 L 是正则的(就是说可被有限状态机接受)，当且仅当 RL 的等价类的数目是有限的。
直接推论是如果一个语言定义等价类的无限集合，它就不是正则的。这个推论经常被用来证明一个语言不是正则的。
例如，由可以被 3 整除的二进制数组成的语言是正则的。有三个等价类 3 - 被 3 除的时候余数是 0, 1 和 2 的数。接受这个语言的极小自动机有对应于等价类的三个状态。
[编辑] 引用
- ^ A. Nerode, "Linear automaton transformations", Proceedings of the AMS, 9 (1958) pp 541-544.
- John E. Hopcroft and Jeffrey D. Ullman, Introduction to Automata Theory, Languages and Computation, Addison-Wesley Publishing, Reading Massachusetts, 1979. ISBN 0-201-029880-X. (See chapter 3.)
- Tom Henzinger, Lecture 7: Myhill–Nerode Theorem (2003)
