泵引理

在可计算性理论中的形式语言理论中，泵引理（Pumping lemma）声称给定类的任何语言可以被“抽吸”并仍属于这个类。一个语言可以被抽吸，如果在这个语言中任何足够长的字符串可以分解成片段，其中某些可以任意重复来生成语言中更长的字符串。这些引理的证明典型的需要计数论证比如鸽笼原理。

两个最重要例子是正则语言的泵引理和上下文无关语言的泵引理。鄂登引理是另一种更强的上下文无关语言的泵引理。

这些引理可以用来确定特定语言不在给定语言类中。但是它们不能被用来确定一个语言在给定类中，因为满足引理是类成员关系的必要条件，但不是充分条件。

泵引理是1961年由 Y. Bar-Hillel、M. Perles 和 E. Shamir首次发表的。

## 正则语言的泵引理

### 定义

假设$L \subseteq \Sigma^*$是正则语言，则存在整数$n \ge 1$，对任意字符串$w \in L$且$\left| w \right| \ge n$（n为泵长度，可理解为正则语言等效的极小化DFA的状态个数），可以将$w$写成$w = xyz$的形式，使得以下说法成立：

- $\left| xy \right| \le n$。
- $\left| y \right| \ge 1$。
- $\forall k \ge 0:xy^kz \in L$。

### 正确性的证明

- 因为L是正则语言，所以存在一个与之等价的确定有限状态自动机。
- 假设n是这个确定有限状态自动机中状态的数量。
- 假设$w \in L$和$\left| w \right| \ge n$
- 在这个自动机读入w的前n个字符后一定有一个状态达到过两次。
- 也就是说对于其中一种w的分解方式w=xyz有$\delta^* \left( s,x \right)=\delta^* \left( s,xy \right)$
- 因此对于所有的$k \ge 0$都有$\delta^*(s,xyz) \in L \leftrightarrow \delta^*(s,xy^kz) \in L$

### 应用

通过泵引理可以用反证法证明L不是正则语言。证明的时候需要注意以下几点：

- 假设要证明的语言为正则语言
- $n$是未知的
- $w$可以在满足$w \in L$和$\left| w \right| \ge n$的条件下自由选择
- $x,y,z$也是未知的
- 找到一个$k$，使得$xy^kz \notin L$，也就是说和泵引理的第三条矛盾

一个证明L不是正则语言的例子

- 证明$L_{01} = \{0^n1^n|n\geq1\}$不是正则语言
- 假设$L_{01}$是正则语言，令n为泵引理常数
- 选择$w = 0^n1^n \in L$，则$\left| w \right| \ge n$
- 于是存在$x,y,z$使得$w=xyz$满足条件$\left| xy \right| \le n$，$\left| y \right| \ge 1$，$\forall k \ge 0:xy^kz \in L_{01}$。
- 因为$\left| xy \right| \le n$且，$\left| y \right| \ge 1$所以$y$中不包含$1$但最少有一个$0$
- 当$k=0$的时候，$xy^kz = xy^0z = xz$，$xz$中$1$的数量比$0$多，所以$xz \notin L_{01}$
- 与泵引理的第三条矛盾，因此$L_{01}$不是正则语言

### 普遍化的泵引理

并不是所有满足泵引理的语言都是正则语言。$L = \{ a^mb^nc^n | m,n \ge 1 \} \cup \{b^mc^n|m,n \ge 0 \}$就是这样的一个例子，它虽然满足泵引理，但并不是正则语言。Jeffrey Jaffe发展出了一个普遍化的泵引理，使它可以证明一个语言是正则语言。它的描述如下：

- 一个语言$L \subseteq \Sigma^*$是正则语言，当且仅当存在一个自然数$n \in \mathbb{N}$，使得任意字符串$w\in \Sigma^*$可以通过至少一种方式被写成$w = xyz$的形式时，以下说法成立：
- $\left| xy \right| \le n$。
- $\left| y \right| \ge 1$。
- $\forall k \ge 0$，$\forall v \in \Sigma^* :xyzv \in L \leftrightarrow xy^kzv \in L$。

一个可行的用于判断一个语言是否为正则语言的方法，可以参见迈希尔－尼罗德定理。一般来说证明一个语言是正则的，可以通过对该语言构造一个有限状态机或正则表达式来实现。

## 上下文无关语言的泵引理

### 定义

若 L 是上下文无关语言，则存在一常数 n > 0 使得语言 L 中每个字串 w 的长度 |w| ≧ n，而当 w = uvxyz 时：

- 对所有的 k ≧ 0，字串 uvkxykz 属于 L。

### 应用

透过泵引理以反证法证明 L 不是上下文无关语言。

- $L = \{a^nb^nc^n|n \geq 1 \}$ 或 $L = \{a^ib^ic^i|i \geq 0\}$ 或 $L = \{a^ib^ic^i|i \geq 2\}$，换句话说，L 就是包含 $a^*b^*c^*$ 所有字串且 a、b、c 三者数目相同的语言。
- 令 n 为泵引理常数，$w = a^nb^nc^n$ 属于 L，w = uvxyz，而 |vxy| ≤ n，|vy| ≥ 1，则 vxy 不可能同时包含 a 与 c。
- 当 vxy 不包含 a 时，vy 只可能包含 b 或 c，则 uxz 包含 n 个 a 及不到 n 个的 b 或 c，使得 uxz 不属于 L。
- 当 vxy 不包含 c 时，uxz 会包含 n 个 c 及不到 n 个的 a 或 b，使得 uxz 不属于 L。
- 因此，无论是上述何种状况，L 都不会是上下文无关语言。
- $$L = \{a^ib^j|j = i^2\}$$
- 令 n 为泵引理常数，$w = a^nb^{n^2}$，w = uvxyz，而 |vxy| ≤ n，|vy| ≥ 1
- 若 vxy 只包含 a，则 uxz 会包含不到 n 个 a 及 $n^2$ 个 b，不属于 L。
- 若 vxy 只包含 b，则 uxz 会包含 n 个 a 及不到 $n^2$ 个 b，不属于 L。
- 若 vxy 里有 a 也有 b。
- 若 v 或 y 包含 a 与 b，$uv^2xy^2z$ 不在 $\{a^ib^j\}$ 里。
- 若 v 只包含 l 个 a，且 y 只包含 m 个 b，$uv^{1+k}xy^{1+k}z$ 会包含 n + lk 个 a 与 $n^2 + mk$ 个 b，由于两者都是线性成长，不可能永远满足 $\{a^ib^j|j = i^2\}$ 的条件，不属于 L。
- 因此，无论是上述何种状况，L 都不会是上下文无关语言。
- $$L = \{ww|w \in \{0,1\}^* \}$$
- 令 n 为泵引理常数，$w = 0^n1^n0^n1^n$ 属于 L，w = uvxyz，而 |vxy| ≤ n，则 vxy 必然为 $0^i1^j$ 或$1^j0^i$形式（此处有$i,j\in \mathbb{N}, i+j\neq 0$）。即 vxy无法同时包含前后两组0，也无法同时包含前后两组1。将uvxyz转变成uxz必然导致前后两组0或两组1的数目产生差异。使得uxz不再满足ww形式。亦即uxz不属于L。
- 因此，L 都不会是上下文无关语言。
- $$L = \{x^iy^jz^k|i \ne j \; and \; j \ne k \}$$
- $$L = \{b^na^{2n}b^n|n \geq 0\}$$
- $$L = \{a^nb^mc^m|n,m \geq 0\}$$