泵引理

在可計算性理論中的形式語言理論中，泵引理（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\}$$