前言
我们已经知道对于任意字母表$\Sigma$存在语言$A\subseteq \Sigma^{*}$是非正则的。这是因为基于$\Sigma$的语言数量是不可数的，但是基于$\Sigma$的正则语言是可数的。然而这个观察结果不足以让我们推导出某个非正则语言是非正则的。本节课我们会讨论一种方法，它可以证明相当广泛的语言是非正则的。
知识点
正则语言的泵引理
首先我们来证明一个简单的事实 — 称之为泵引理 — 它确立了正则语言所拥有的一种必然属性。稍后在接下来的小节中，我们将会用这个引理来推导某个语言是非正则的。
引理5.1（正则语言的泵引理）. 已知$\Sigma$是一个字母表，$A\subseteq\Sigma^{*}$是一个正则语言。存在一个正整数$n$（叫做$A$的泵长度）具有以下属性。对于每个字符串$w\in A$并且$|A|\geq n$，可以写成$w=xyz$，其中所选择的$x,y,z\in\Sigma^{*}$满足
- $y\neq \varepsilon$,
- $|xy|\leq n$,并且
- 对于所有$i\in\mathbb{N}$有$xy^iz\in A$.
泵引理基本上是一个精确的技术性方法，用来表示以下事实的简单结果：
如果一个有$n$个或者更少状态的DFA从一个输入字符串中读取了$n$个或者更多符号，那么至少一个状态会被访问超过一次。
这表示如果一个有$n$个状态的DFA读取了某个长度至少是$n$的字符串，那么输入字符串中一定存在一个子串造成了一个循环，也就是说DFA从一个状态出发又回到了这个状态。如果这个DFA接受原来的字符串，那么重复添加造成循环的子串或者移除子串，我们得到不同的字符串也能被这个DFA接受。尝试将这种直觉和随后的证明搭配也许会有帮助。
引理5.1的证明：已知$M=(Q,\Sigma,\delta,q_0,F)$是一个识别A的DFA，$n=|Q|$是$M$的状态数量。我们将会证明这个$n$满足泵引理中的属性。
注意如果$A$中没有长度超过$n$的字符串，那么就没我们什么事了：引理中声明的属性在这种情况下是满足的。因此我们将转到$A$包含至少一个长度超过$n$的字符串的情况上来。特别地假设$w\in A$是一个字符串并且$|w|>n$。我们写出
其中$m=|w|$并且$a_1,…,a_m\in\Sigma$。由$w\in A$可知$M$接受$w$，并且存在状态
使得$r_0=q_0,r_m\in F$并且对于每个$k\in\{0,…,m-1\}$
现在，序列$r_0,r_1,…,r_n$有$n+1$个成员，但是$Q$中只有$n$个不同的元素，所以在这个序列中至少$Q$中至少有一个状态出现超过一次。这样，一定存在索引$s,t\in\{0,…,n\}$满足$s<t$使得$r_s=r_t$。
接下来，定义字符串$x,y,z\in\Sigma^{*}$如下：
选择这些字符串让$w=xyz$，接着为了完成证明，我们只需要说明这些字符串满足引理所列的三种条件就行。前两个条件很明显：因为$s<t$我们知道$y$的长度$t-s$至少为1，因此$y\neq \varepsilon$；然后因为$t$选自集合$\{0,…,n\}$我们知道$xy$的长度$t$最大是$n$。现在只需要验证$xy^iz\in A$即可，他等价于对于每个$i\in\mathbb{N}$都有$M$接受$xy^iz$。$xy^iz$被$M$接受这个事实通过核实状态序列
能被DFA $M$接受来推断。
泵引理的样例DFA
如果泵引理的证明或者背后的思路不太明确，也许看看一个实际的DFA运作和一个足长的字符串被它接受会有所帮助。比如，让我们将$M$当做是状态图5.1中的DFA。
现在考虑任意长度至少为6而且可以被$M$接受的字符串$w$。比如，我们让$w=0110111$。它造成了$M$通过了状态序列：
（箭头表示转移，箭头上的符号表示造成转移的输入符号）很明显，这个序列中至少有一个状态会出现多次，而且实际上这个特殊例子中有三个这样的状态：$q_1、q_2、q_5$，每个都出现了两次。让我们集中在状态$q_1$上，因为这个状态首次重复出现。子串$1101$造成了$M$在状态$q_1$上循环。换成泵引理的表达方式对应采用
因为子串$y$造成了$M$从状态$q_1$回到状态$q_1$，看起来当$M$处于状态$q_1$时读取$y$没有任何作用。所以$x$导致$M$从初始状态$q_0$到达状态$q_1$，$z$导致$M$从状态$q_1$到达一个接受状态，我们可以看出$M$不止接受$w=xyz$，而且还接受$xy、xyyz、xyyyz$等等。
刚才所描述的例子没什么特殊的地方；一些类似的情况总会发生。随便选取任意DFA，以及任意超过DFA状态数量并且能被接受的字符串，然后你就能找到一个我们上面发现的循环。通过多次或者零次重复循环部分的输入字符你就能得到不同的能被DFA接受的字符串。这就是泵引理本质上想要表达的。
使用泵引理证明非正则性
记住泵引理是一种关于正则语言的陈述会很有帮助：它建立了一种每个已知正则语言都拥有的属性。
尽管泵引理一种关于正则语言的陈述，通过反证法，我们可以用它来证明某个语言是非正则的。特别是，我们采用以下步骤：
- 对于我们想要证明非正则性的语言$A$，我们假设$A$是正则的。基于这个假设我们采用泵引理证明它。
- 使用泵引理为$A$建立的属性，我们得出矛盾。这个矛盾就是我们得出某个字符串本来应该包含于$A$但实际上却没有。
- 已经得出矛盾，我们推断假设$A$是正则导致了这个矛盾，所以我们得出$A$是非正则的。
通过泵引理证明非正则性的例子
让我们用一些例子来说明这个方法。这些例子将会被声明为命题，随后的证明会告诉你如何论证。
命题5.2. 已知$\Sigma=\{0,1\}$是一个二进制字母表，定义一个基于$\Sigma$的语言如下：
语言$SAME$是非正则的。
注意5.3. 当我们像这样赋予一个语言特殊名称时，这个语言在后续课程中出现时也是这样定义的。所以看到有特殊名称的语言就记住它是个不错的注意 — 作为样例他们很有帮助。另外两个特殊名称语言也会出现在本节课中。
证明：反向假设$SAME$是正则的。由正则语言的泵引理可知，对于$SAME$一定存在一个泵长度$n\geq 1$满足引理中的属性。接下来的证明中我们会假设这样一个泵长度$n$。
定义$w=0^n1^n$，$w\in SAME$并且$|w|=2n\geq n$，所以泵引理告诉我们存在字符串$x、y、z\in\Sigma^{*}$使得$w=xyz$满足以下条件：
- $y\neq \varepsilon,$
- $|xy|\leq n,$
- 对于所有$i\in\mathbb{N}$有$xy^iz\in SAME.$
现在因为$xyz=0^n1^n$并且$|xy|\leq n$，子串$y$中没有1，因为$xy$的长度够不着$xyz$中的1。也就是说对于某个$k\in\mathbb{N}$有$y=0^k$，并且因为$y\neq \varepsilon$，我们得知$k\geq 1$。我还能得出
这是因为$xyyz$是在$xyz$中插入$y=0^k$，而且是在没有1出现之前插入，普遍来说还可以得出对于每个$i\in\mathbb{N}$有
然而，因为$k\geq 1$，我们知道字符串$xy^2z=0^{n+k}1^n$不包含于$SAME$。这与泵引理的第三个条件矛盾，它要求对于所有$i\in\mathbb{N}$有$xy^iz\in SAME$。
得到这个矛盾后，我们推断假设$SAME$是正则的是错误的。因此语言$SAME$是非正则的，证毕。
命题5.4. 已知$\Sigma=\{0,1\}$是一个二进制字母表，定义一个基于$\Sigma$的语言如下：
语言$A$是非正则的。
证明：反向假设$A$是正则的。由正则语言的泵引理可知，对于$A$一定存在一个泵长度$n\geq 1$满足引理中的属性。接下来的证明中我们会假设这样一个泵长度$n$。
定义$w=0^{n+1}1^n$。我们知道$w\in A$并且$|w|=2n+1\geq n$，所以泵引理告诉我们存在字符串$x、y、z\in\Sigma^{*}$使得$w=xyz$，以及以下条件得到满足：
- $y\neq \varepsilon,$
- $|xy|\leq n,$
- 对于所有$i\in\mathbb{N}$有$xy^iz\in A.$
现在，因为$xyz=0^{n+1}1^n$并且$|xy|\leq n$，对于某个$k\geq 1$一定有$y=0^k$。（这里的原因和上个命题类似）这次我们获得对于每个$i\in\mathbb{N}$有
特别是，如果我们选择$i=0$，那么我们获得
然而$k\geq 1$，因此$n+1-k\leq n$，我们发现$xy^0z$不包含于$n$。这泵引理的第三个条件矛盾，他要求对于所有$i\in\mathbb{N}$都有$xy^iz\in A$
得到了这个矛盾，我们推断假设$A$是正则的是错误的。因此$A$是非正则的，证毕。
注意5.5. 在上面的证明中，很重要的一点是，选择$i=0$才能得出矛盾，其他的选择都不行。
命题5.6 已知$\Sigma=\{0\}$，定义一个基于$\Sigma$的语言如下：
语言$SQUARE$是非正则的。
证明：反向假设$SQUARE $是正则的。由正则语言的泵引理可知，对于$SQUARE $一定存在一个泵长度$n\geq 1$满足引理中的属性。接下来的证明中我们会假设这样一个泵长度$n$。
定义$w=0^{n^2}$。我们知道$w\in SQUARE$并且$|w|=n^2\geq n$，所以泵引理告诉我们存在字符串$x、y、z\in\Sigma^{*}$使得$w=xyz$，以及以下条件得到满足：
- $y\neq \varepsilon,$
- $|xy|\leq n,$
- 对于所有$i\in\mathbb{N}$有$xy^iz\in SQUARE.$
字母表$\Sigma$中只有一个符号，所以马上可以看出对于任意$k\in\mathbb{N}$有$y=0^k$。因为$y\neq\varepsilon$并且$|y|\leq|xy|\leq n$，可知$1\leq k\leq n$，因此对于每个$i\in\mathbb{N}$都有
特别是，如果我们选择$i=2$，那么我们获得
然而因为$1\leq k\leq n$，$n^2+k$不可能是一个完全平方；$n^2+k$大于$n^2$，$n^2$的下一个完全平方是
明显大于$n^2+k$，因为$k\leq n$。因此字符串$xy^2z$不包含于$SQUARE$，这与泵引理的第三个条件矛盾，它要求对于所有$i\in\mathbb{N}$有$xy^iz\in SQUARE$。
得到了这个矛盾，我们推断假设$SQUARE$是正则的是错误的，因此语言$SQUARE$是非正则的，证毕。
在进入下一个例子前，让我们介绍一个本课程中很有用的概念。对于一个已知字符串$w$,字符串$w^R$表示$w$的反转。一般来说，假设$w$是一个基于字母表$\Sigma$的字符串，反转操作的递归定义如下：
- $\varepsilon^R=\varepsilon,$
- 对于每个$w\in\Sigma^{*}$和$a\in\Sigma$都有$(aw)^R=w^Ra.$
让我们定义一个基于二进制字母表$\Sigma=\{0,1\}$的语言
这个语言的名字叫做$PAL$，因为他是回文（palindrome）的缩写，这种字符串你从前往后读或者从后往前读是一样的。
命题5.7. 语言$PAL$是非正则的。
证明：反向假设$PAL $是正则的。由正则语言的泵引理可知，对于$PAL $一定存在一个泵长度$n\geq 1$满足引理中的属性。接下来的证明中我们会假设这样一个泵长度$n$。
定义$w=0^n10^n$。我们知道$w\in PAL $并且$|w|=2n+1\geq n$，所以泵引理告诉我们存在字符串$x、y、z\in\Sigma^{*}$使得$w=xyz$，以及以下条件得到满足：
- $y\neq \varepsilon,$
- $|xy|\leq n,$
- 对于所有$i\in\mathbb{N}$有$xy^iz\in PAL.$
我们再次发现对于$k\geq 1$有$y=0^k$。这次我们获得对于每个$i\in\mathbb{N}$有
特别是，如果我们选择$i=2$，那么我们获得
因为$k\geq 1$，这个字符串和它的反转并不相等，因此$xy^2z$不包含于$PAL$。这与泵引理的第三个条件矛盾，他要求对于所有$i\in\mathbb{N}$有$xy^iz\in PAL.$。
得到了这个矛盾，我们推断假设$PAL$是正则的是错误的。因此$PAL$是非正则的，证毕。
上面这个四个命题应该能给你提供泵引理证明语言非正则性的思路。开头总是一样的：我们反向假设某个语言是正则的，观察泵引理提供的泵长度$n$。此时选择一个字符串$w$，试图通过一些推论，得出一个矛盾。有时候如何选择字符串或者怎样得出矛盾并不太明确；这些步骤取决于你所选择的语言，也许$w$有很多不错的选择，也许还需要一些创造性的取舍才能成功。
如果你选择什么样的字符串$w$，针对矛盾做一点猜想。如果不行，你会发现你获得了一些更好选择的直接。当然，你应该彻底信服自己的论证，并且积极地检查一些可能出错的地方；如果你不能被自己的证明说服，那么别人也不会相信它。
得自闭包属性的费正则性
有时候通过关联正则语言的闭包属性我们可以证明某个语言是非正则的。这里有两个例子，同样地先声明命题。
命题5.8. 已知$\Sigma=\{0,1\}$，定义一个基于$\Sigma$的语言如下：
语言$B$是非正则的。
证明：反向假设$B$是正则的。正则语言的取余操作是闭合的，因此$\overline{B}$是正则的。然而$\overline{B}=PAL$，我们已经证明$PAL$是非正则的。这是一个矛盾，因此我们假设$B$是正则的是错误的。我们得出$B$是非正则的，证毕。
命题5.9. 已知$\Sigma=\{0,1\}$，定义一个基于$\Sigma$的语言如下：
$C=\{w\in\Sigma^{*}:w中的0比1多\}.$
语言$C$是非正则的。
证明：反向假设$C$是正则的。我们知道语言$L(0^{*}1^{*})$是正则的，因为这个语言能匹配上一个正则表达式。正则语言的交集操作是闭合的，所以$C\cap L(0^{*}1^{*})$是正则的。然而我们获得了
这个语言的定义在命题5.4中，我们已经证明过它是非正则的了。这是一个矛盾，因此我们假设$C$是正则的是错误的。我们得出$C$是非正则的。
一定要记住当我们使用这个方法时，是正则语言在交集、并集等等操作下是闭合的，而不是非正则语言。比如，两个非正则语言的交集并不总是非正则的 — 所以基于这个声明的证明将不是有效的。