泵引理

在可計算性理論中的形式語言理論中，**泵引理**（Pumping lemma）聲稱給定類的任何語言可以被「抽吸」並仍屬於這個類。一個語言可以被抽吸，如果在這個語言中任何足夠長的字符串可以分解成片段，其中某些可以任意重複來生成語言中更長的字符串。這些引理的證明典型的需要計數論證比如鴿籠原理。

兩個最重要例子是**正則語言的泵引理**和**上下文無關語言的泵引理**。**鄂登引理**是另一種更強的上下文無關語言的泵引理。

這些引理可以用來確定特定語言**不**在給定語言類中。但是它們不能被用來確定一個語言在給定類中，因為滿足引理是類成員關係的必要條件，但不是充分條件。

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

## 正則語言的泵引理

### 定義

假設 $L\subseteq \Sigma ^{*}$ 是正則語言，則存在整數 $n\geq 1$ ，對任意字符串 $w\in L$ 且 $\left|w\right|\geq n$ （n 為泵長度，可理解為正則語言等效的極小化 DFA 的狀態個數），可以將 $w$ 寫成 $w=xyz$ 的形式，使得以下說法成立：

 1. $\left|xy\right|\leq n$ ，
2. $\left|y\right|\geq 1$ ，
3. $\forall k\geq 0:xy^{k}z\in L$ 。

### 正確性的證明

* 因為 L 是正則語言，所以存在一個與之等價的確定有限狀態自動機，
* 假設 n 是這個確定有限狀態自動機中狀態的數量，
* 假設 $w\in L$ 和 $\left|w\right|\geq n$
* 在這個自動機讀入 w 的前 n 個字符後一定有一個狀態達到過兩次，
* 也就是說對於其中一種 w 的分解方式 w=xyz 有 $\delta ^{*}\left(s,x\right)=\delta ^{*}\left(s,xy\right)$
* 因此對於所有的 $k\geq 0$ 都有 $\delta ^{*}(s,xyz)\in L\leftrightarrow \delta ^{*}(s,xy^{k}z)\in L$

### 應用

通過泵引理可以用反證法證明 L 不是正則語言。證明的時候需要注意以下幾點：

1. 假設要證明的語言為正則語言
2. $n$ 是未知的
3. $w$ 可以在滿足 $w\in L$ 和 $\left|w\right|\geq n$ 的條件下自由選擇
4. $x,y,z$ 也是未知的
5. 找到一個 $k$ ，使得 $xy^{k}z\notin L$ ，也就是說和泵引理的第三條矛盾

一個證明 L 不是正則語言的例子

* 證明 $L_{01}=\{0^{n}1^{n}|n\geq 1\}$ 不是正則語言
  * 假設 $L_{01}$ 是正則語言，令 n 為泵引理常數
  * 選擇 $w=0^{n}1^{n}\in L$ ，則 $\left|w\right|\geq n$
  * 於是存在 $x,y,z$ 使得 $w=xyz$ 滿足條件 $\left|xy\right|\leq n$ ， $\left|y\right|\geq 1$ ， $\forall k\geq 0:xy^{k}z\in L_{01}$ 。
  * 因為 $\left|xy\right|\leq n$ 且， $\left|y\right|\geq 1$ 所以 $y$ 中不包含 $1$ 但最少有一個 $0$
  * 當 $k=0$ 的時候， $xy^{k}z=xy^{0}z=xz$ ， $xz$ 中 $1$ 的數量比 $0$ 多，所以 $xz\notin L_{01}$
  * 與泵引理的第三條矛盾，因此 $L_{01}$ 不是正則語言

### 普遍化的泵引理

並不是所有滿足泵引理的語言都是正則語言。 $L=\{a^{m}b^{n}c^{n}|m,n\geq 1\}\cup \{b^{m}c^{n}|m,n\geq 0\}$ 就是這樣的一個例子，它雖然滿足泵引理，但並不是正則語言。Jeffrey Jaffe 發展出了一個普遍化的泵引理，使它可以證明一個語言是正則語言。它的描述如下：

* 一個語言 $L\subseteq \Sigma ^{*}$ 是正則語言，若且唯若存在一個自然數 $n\in \mathbb {N} $ ，使得任意字符串 $w\in \Sigma ^{*}$ 可以通過至少一種方式被寫成 $w=xyz$ 的形式時，以下說法成立：
   * 1. $\left|xy\right|\leq n$ ，
    2. $\left|y\right|\geq 1$ ，
    3. $\forall k\geq 0$ ， $\forall v\in \Sigma ^{*}:xyzv\in L\leftrightarrow xy^{k}zv\in L$ 。

一個可行的用於判斷一個語言是否為正則語言的方法，可以參見邁希爾－尼羅德定理。一般來說證明一個語言是正則的，可以通過對該語言構造一個有限狀態機或正則表達式來實現。

## 上下文無關語言的泵引理

### 定義

若 _L_ 是上下文無關語言，則存在一常數 _n_ > 0 使得語言 _L_ 中每個字串 _w_ 的長度 |_w_| ≧ _n_，而當 _w_ = _uvxyz_ 時：

1. |_vxy_| ≦ _n_，
2. |_vy_| ≧ 1，且
3. 對所有的 _k_ ≧ 0，字串 _uvkxykz_ 屬於 _L_ 。

### 應用

透過**泵引理**以反證法證明 _L_ 不是上下文無關語言。

 * $L=\{a^{n}b^{n}c^{n}|n\geq 1\}$ 或 $L=\{a^{i}b^{i}c^{i}|i\geq 0\}$ 或 $L=\{a^{i}b^{i}c^{i}|i\geq 2\}$ ，換句話說，_L_ 就是包含 $a^{*}b^{*}c^{*}$ 所有字串且 _a_、_b_、_c_ 三者數目相同的語言。
  * 令 _n_ 為**泵引理**常數， $w=a^{n}b^{n}c^{n}$ 屬於 _L_，_w_ = _uvxyz_，而 |_vxy_| ≤ _n_，|_vy_| ≥ 1，則 _vxy_ 不可能同時包含 _a_ 與 _c_。
    1. 當 _vxy_ 不包含 _a_ 時，_vy_ 只可能包含 _b_ 或 _c_，則 _uxz_ 包含 _n_ 個 _a_ 及不到 _n_ 個的 _b_ 或 _c_，使得 _uxz_ 不屬於 _L_。
    2. 當 _vxy_ 不包含 _c_ 時，_uxz_ 會包含 _n_ 個 _c_ 及不到 _n_ 個的 _a_ 或 _b_，使得 _uxz_ 不屬於 _L_。
  * 因此，無論是上述何種狀況，_L_ 都不會是上下文無關語言。
 * $L=\{a^{i}b^{j}|j=i^{2}\}$
  * 令 _n_ 為**泵引理**常數， $w=a^{n}b^{n^{2}}$ ，_w_ = _uvxyz_，而 |_vxy_| ≤ _n_，|_vy_| ≥ 1
    1. 若 _vxy_ 只包含 _a_，則 _uxz_ 會包含不到 _n_ 個 _a_ 及 $n^{2}$ 個 _b_，不屬於 _L_；
    2. 若 _vxy_ 只包含 _b_，則 _uxz_ 會包含 _n_ 個 _a_ 及不到 $n^{2}$ 個 _b_，不屬於 _L_；
    3. 若 _vxy_ 裡有 _a_ 也有 _b_，
      1. 若 _v_ 或 _y_ 包含 _a_ 與 _b_， $uv^{2}xy^{2}z$ 不在 $\{a^{i}b^{j}\}$ 裡；
      2. 若 _v_ 只包含 _l_ 個 _a_，且 _y_ 只包含 _m_ 個 _b_， $uv^{1+k}xy^{1+k}z$ 會包含 _n_ + _lk_ 個 _a_ 與 $n^{2}+mk$ 個 _b_，由於兩者都是線性成長，不可能永遠滿足 $\{a^{i}b^{j}|j=i^{2}\}$ 的條件，不屬於 _L_。
  * 因此，無論是上述何種狀況，_L_ 都不會是上下文無關語言。
 * $L=\{ww|w\in \{0,1\}^{*}\}$
  * 令 _n_ 為**泵引理**常數， $w=0^{n}1^{n}0^{n}1^{n}$ 屬於 _L_，_w_ = _uvxyz_，而 |_vxy_| ≤ _n_，則 _vxy_ 必然為 $0^{i}1^{j}$ 或 $1^{j}0^{i}$ 形式（此處有 $i,j\in \mathbb {N} ,i+j\neq 0$ ）。即 _vxy_ 無法同時包含前後兩組 0，也無法同時包含前後兩組 1。將 _uvxyz_ 轉變成 _uxz_ 必然導致前後兩組 0 或兩組 1 的數目產生差異。使得 _uxz_ 不再滿足 _ww_ 形式。亦即 _uxz_ 不屬於 _L_。
  * 因此，_L_ 都不會是上下文無關語言。
 * $L=\{x^{i}y^{j}z^{k}|i\neq j\;and\;j\neq k\}$
* $L=\{b^{n}a^{2n}b^{n}|n\geq 0\}$
* $L=\{a^{n}b^{m}c^{m}|n,m\geq 0\}$

## 引用

* Michael Sipser. Introduction to the Theory of Computation. PWS Publishing. 1997. ISBN 978-0-534-94728-6.  Section 1.4: Nonregular Languages, pp.77–83. Section 2.3: Non-context-free Languages, pp.115–119.