泵引理#

用于证明一个语言不是正则语言

泵引理指出：对于任何正则语言$L$，存在一个整数$p$（称为泵长度），使得对于任何长度大于或等于$p$的字符串$s \in L$，都可以将$s$分解为三个部分$s = xyz$，满足以下条件：

• $|xy| \leq p$，即前两个部分的长度之和不超过$p$
• $|y| > 0$，即中间部分$y$的长度大于0
• 对于所有的非负整数$i$，字符串$xy^iz \in L$，即重复中间部分$y$任意次数后，仍然属于语言$L$
• $|s| \ge p$，即字符串$s$的长度大于或等于泵长度$p$

所以利用上述规则，当重复中间部分任意次数后，只要有一个结果不属于语言$L$，就可以证明该语言不是正则语言

例子#

证明$L = \{0^n1^n | n \geq 0\}$不是正则语言

1. 假设$L$是正则语言，则存在泵长度$p$
2. 设输入字符串$s$, $|s| \geq p$，设$s = 0^p1^p$，$|s| = 2p$ 确实大于等于$p$
3. 根据泵引理，$s$可以分解为$s = xyz$，满足$|xy| \leq p$且$|y| > 0$。由于$|xy| \leq p$，所以$x$和$y$只能包含0，因此可以设$x = 0^k, y = 0^m$，则$|xy| = k + m \leq p, |y| = m > 0$，所以$z = 0^{p-k-m}1^p$
4. 根据泵引理，$xy^iz \in L$对于所有的非负整数$i$都应成立。当$i = 0$时，$xy^0z = xz = 0^{p-m}1^p$，其中$m > 0$，所以$p-m < p$，因此$xy^0z \notin L$
5. 不满足泵引理的条件，故$L$不是正则语言