正则语言的泵引理

理解

**应用场景：**判断语言是否不是正则语言（能确定特定语言不是正则语言，但是其只是正则语言成立的必要条件不是充分条件，不能证明一个语言就是正则语言）

**使用原理：**鸽巢原理在有限状态、无限字符串的情况下的运用

定义

如果语言$L$是正则的，那么存在正整数$N$，对$w\in L$，只要$|w|\ge N$，就可以将$w$分为三部分$w=xyz$满足：

1. $y\ne \varepsilon$（或者$|y|>0$）
2. $|xy|\le N$
3. $\forall k \ge 0, xy^kz \in L$

**解释：**任何从开始状态到接受状态的路径，如果长度超过$N$，经过大于$N$个状态，必定有一个重复状态，因此会形成一个循环（loop）；那么，这个循环可以被多次重复后，沿着原路径还会到达接收状态。

泵引理可以用来判定某语言不是正则语言，但是不能确定某语言就是正则语言。

**例子1：**证明$L_{01}=\{0^n1^n|n\ge 0\}$不是正则语言

假设$L_{01}$是正则的，

1. 那么一定存在正整数$N$，对$w\in L_{01}(|w|\ge N)$满足泵引理
2. 从$L_{01}$中取$w=0^N1^N$，则$w\in L_{01}$，且$|w|=2N>N$
3. 那么可令$w=xyz$，且$|xy|\le N,y\ne \varepsilon$
4. $\because |xy|\le N$，令$x=0^m,y=0^n,z=0^{N-m-1}1^N,n>0$
5. 那么$xy^0z=0^{N-n}1^N\notin L_{01}$，与泵引理结论$xy^0z\in L_{01}$矛盾 // $y^0$即为$\{\varepsilon\}$