[人工智能]【编译原理】泵引理

浅浅冒泡一下我这个科研废物。

泵引理：若$A$是一个正则语言，则存在一个数$p$（泵长度）使得，如果$s$是$A$中任一长度不小于$p$的字符串，那么$s$可以被分成$3$段，$s=xyz$，满足下述条件：

1. 对每一个$i\ge 0,x{y}^{i}z\in A$
2. $|y|>0$
3. $|xy|\le p$

这定理乍一看给我整不会了，然后以下借助例题说一下我的理解。（如有错误可以告诉我呜呜呜）

泵引理就是：在一个正则语言$A$中有任意一个字符串$s$，这个字符串由$3$个子串$x、y、z$构成（即$s=xyz$），且$s$中的一个子串（也就是$y$）在自我重复$i$次后，组成的新字符串$x{y}^{i}z$仍在语言$A$中。

注意：泵引理只能证明一个语言不是正则语言，而不能证明一个语言是正则语言。

例1：用泵引理证明语言 B = { 0 n 1 n ∣ n ≥ 0 } B=\{0^n1^n|n\geq0\} B={0n1n∣n≥0}不是正则的。

1. 先假设语言正则：假设相反，$B$是正则的。
2. 找合适的字符串$s$，一般与语言本身形式长得一样：设$p$是泵引理给出的泵长度。选择字符串$s=0^p{1}^p$。
3. 利用泵引理证明语言非正则，一般考察$xyyz$？：

书上说，满足条件的子串$y$有以下三种情况——
（1）$y$中只有$0$：比如对于$000111$，$x=00,y=0,z=111$，那么$xyyz=0000111$，$0$比$1$多，矛盾。
（2）$y$中只有$1$：比如对于$000111$，$x=000,y=11,z=1$，那么$xyyz=0001111$，$1$比$0$多，矛盾。
（3）$y$中有$0$有$1$：比如对于$000111$，$x=00,y=01,z=11$，那么$xyyz=00010111$，顺序乱了，不是所有$0$都在$1$前面，矛盾。

但是考虑$|xy|\le p$，又因为$s$前$p$个字符都为$0$，说明$xy$肯定由全$0$组成。
而且$|y|>0$，所以$y$必然由$0$组成。那就是上面的第（1）种情况。

例2：用泵引理证明语言 C = { w ∣ w 中 0 和 1 的 个 数 相 同 } C=\{w|w中0和1的个数相同\} C={w∣w中0和1的个数相同}不是正则的。

1. 先假设语言正则：假设相反，$C$是正则的。
2. 找合适的字符串$s$，一般与语言本身形式长得一样：设$p$是泵引理给出的泵长度。选择字符串$s=0^p{1}^p$。
3. 利用泵引理证明语言非正则，一般考察$xyyz$？：同上。

例3：用泵引理证明语言 D = { w w ∣ w ∈ { 0 , 1 } ? } D=\{ww|w\in\{0,1\}^*\} D={ww∣w∈{0,1}?}不是正则的。

1. 先假设语言正则：假设相反，$D$是正则的。
2. 找合适的字符串$s$，一般与语言本身形式长得一样：设$p$是泵引理给出的泵长度。选择字符串$s=0^{p}10^{p}1$。
3. 利用泵引理证明语言非正则，一般考察$xyyz$？：
   同样地，$s$前$p$个字符串都是$0$，所以根据泵引理，$y$必然由$0$组成。
   那么考察$001001$，选择$x=0,y=0,z=1001$，
   $xyyz=0001001$，前面一串$0$和后面一串$0$的个数不相等，不满足$s$的形式，矛盾。

参考：《计算理论导引（第3版）》