【理论学习】Myhill–Nerode Theorem

如果你上一门本科阶段的计算理论课，你通常会学到“泵引理”这个证明一个语言非正则的手段。

但是，泵引理条件并非语言是正则语言的充要条件。你自然要好奇，有没有什么条件，既是充要的，又易于使用（来证明非正则性）？

其实充要（或者说等价）条件有很多很多，包括但不限于下面列出的这些：

Myhill–Nerode Theorem说的就是。

---

预备工作

首先，我们定义两个“不可区分性”。

令为上的任意语言，若串满足

，

则称在上不可区分，记作。

类似的，我们可以定义上的不可区分性。

令，若串满足

，即在上到达同一个状态，

则称在上不可区分，记作。

注意到上面两个“不可区分”都是等价关系。

(接下来的证明全部使用大白话)

---

引理

为，，对于任意，若，则

证明：

因为在的同一个状态上，所以往后面接上任何相同的串，到达的状态也一样，因此要么同时在上，要么同时不在上。因此

由上可见

---

推论

若为正则语言，则有有限个等价类。

证明：

设

任何字符串显然都会落在的某个状态上，因此全体字符串关于只有个等价类，因此至多有个等价类。

---

结论

不是正则语言。

证明：

我们曾经用泵引理证明过这一经典命题，现在我们利用刚才的推论来给出一个简洁的证明。

考虑字符串集，显然该集合中的任意两个字符串都不在意义上等价，因为时，，。

因此有无穷个等价类，因此不是正则语言。

---

Myhill–Nerode 定理

是正则语言 当且仅当 有有限个等价类。

证明：

方向已经在推论中证明。

方向可以构造性地证明：

构造，其中

等于的等价类个数，每个状态对应一个等价类。

状态代表所在的等价类。

注意到，若，则。

，其中为对应的等价类的对应状态。

由数学归纳法可知，上述构造使任何字符串在输入后都会落在其所在等价类对应的状态。

注意到，对于任意一个等价类，要么，要么。也因此我们可以知道，是由有限个等价类组成的。

把这些构成的等价类对应的状态作为。

这样一来，当且仅当。

也即，。

因此，是一个正则语言。

可以看到，该证明过程为我们给出了一个正则语言的最简有限自动机的构造方法。