泵引理

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

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

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

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

正則語言的泵引理

定義

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

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

正確性的證明

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

應用

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

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

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

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

普遍化的泵引理[2]

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

• 一個語言${\displaystyle L\subseteq \Sigma ^{*}}$是正則語言，若且唯若存在一個自然數${\displaystyle n\in \mathbb {N} }$，使得任意字符串${\displaystyle w\in \Sigma ^{*}}$可以通過至少一種方式被寫成${\displaystyle w=xyz}$的形式時，以下說法成立：
  • 1. ${\displaystyle \left|xy\right|\leq n}$，
    2. ${\displaystyle \left|y\right|\geq 1}$，
    3. ${\displaystyle \forall k\geq 0}$，${\displaystyle \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，字串 uv^kxy^kz 屬於 L 。

應用

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

• ${\displaystyle L=\{a^{n}b^{n}c^{n}|n\geq 1\}}$ 或 ${\displaystyle L=\{a^{i}b^{i}c^{i}|i\geq 0\}}$ 或 ${\displaystyle L=\{a^{i}b^{i}c^{i}|i\geq 2\}}$，換句話說，L 就是包含 ${\displaystyle a^{*}b^{*}c^{*}}$ 所有字串且 a、b、c 三者數目相同的語言。
  • 令 n 為泵引理常數，${\displaystyle 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 都不會是上下文無關語言。

• ${\displaystyle L=\{a^{i}b^{j}|j=i^{2}\}}$
  • 令 n 為泵引理常數，${\displaystyle w=a^{n}b^{n^{2}}}$，w = uvxyz，而 |vxy| ≤ n，|vy| ≥ 1
    1. 若 vxy 只包含 a，則 uxz 會包含不到 n 個 a 及 ${\displaystyle n^{2}}$ 個 b，不屬於 L；
    2. 若 vxy 只包含 b，則 uxz 會包含 n 個 a 及不到 ${\displaystyle n^{2}}$ 個 b，不屬於 L；
    3. 若 vxy 裏有 a 也有 b，
       1. 若 v 或 y 包含 a 與 b，${\displaystyle uv^{2}xy^{2}z}$ 不在 ${\displaystyle \{a^{i}b^{j}\}}$ 裏；
       2. 若 v 只包含 l 個 a，且 y 只包含 m 個 b，${\displaystyle uv^{1+k}xy^{1+k}z}$ 會包含 n + lk 個 a 與 ${\displaystyle n^{2}+mk}$ 個 b，由於兩者都是線性成長，不可能永遠滿足 ${\displaystyle \{a^{i}b^{j}|j=i^{2}\}}$ 的條件，不屬於 L。
  • 因此，無論是上述何種狀況，L 都不會是上下文無關語言。

• ${\displaystyle L=\{ww|w\in \{0,1\}^{*}\}}$
  • 令 n 為泵引理常數，${\displaystyle w=0^{n}1^{n}0^{n}1^{n}}$ 屬於 L，w = uvxyz，而 |vxy| ≤ n，則 vxy 必然為 ${\displaystyle 0^{i}1^{j}}$ 或${\displaystyle 1^{j}0^{i}}$形式（此處有${\displaystyle i,j\in \mathbb {N} ,i+j\neq 0}$）。即 vxy無法同時包含前後兩組0，也無法同時包含前後兩組1。將uvxyz轉變成uxz必然導致前後兩組0或兩組1的數目產生差異。使得uxz不再滿足ww形式。亦即uxz不屬於L。
  • 因此，L 都不會是上下文無關語言。

• ${\displaystyle L=\{x^{i}y^{j}z^{k}|i\neq j\;and\;j\neq k\}}$
• ${\displaystyle L=\{b^{n}a^{2n}b^{n}|n\geq 0\}}$
• ${\displaystyle L=\{a^{n}b^{m}c^{m}|n,m\geq 0\}}$

引用

1. Y. Bar-Hillel, M. Perles, E. Shamir, "On formal properties of simple phrase structure grammars", Zeitschrift für Phonetik, Sprachweissenshaft und Kommunikationsforschung 14 (1961) pp. 143-172.
2. Jeffery Jaffe: A necessary and sufficient pumping lemma for regular languages （頁面存檔備份，存於互聯網檔案館）

• 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.