在可計算性理論 中的形式語言 理論中，泵引理 （Pumping lemma）聲稱給定類的任何語言可以被「抽吸」並仍屬於這個類。一個語言可以被抽吸，如果在這個語言中任何足夠長的字符串可以分解成片段，其中某些可以任意重複來生成語言中更長的字符串。這些引理的證明典型的需要計數論證 比如鴿籠原理 。
兩個最重要例子是正則語言的泵引理 和上下文無關語言的泵引理 。鄂登引理 上下文無關語言 的泵引理。
這些引理 可以用來確定特定語言不 在給定語言類中。但是它們不能被用來確定一個語言在給定類中，因為滿足引理是類成員關係的必要條件 ，但不是充分條件。
泵引理是1961年由 Y. Bar-Hillel 、M. Perles 和 E. Shamir 首次發表的[1]
正則語言的泵引理 [ 編輯 ] 假設
L
⊆
Σ
∗
{\displaystyle L\subseteq \Sigma ^{*}}
正則語言 ，則存在整數
n
≥
1
{\displaystyle n\geq 1}
w
∈
L
{\displaystyle w\in L}
|
w
|
≥
n
{\displaystyle \left|w\right|\geq n}
w
{\displaystyle w}
w
=
x
y
z
{\displaystyle w=xyz}
|
x
y
|
≤
n
{\displaystyle \left|xy\right|\leq n}
|
y
|
≥
1
{\displaystyle \left|y\right|\geq 1}
∀
k
≥
0
:
x
y
k
z
∈
L
{\displaystyle \forall k\geq 0:xy^{k}z\in L}
正確性的證明 [ 編輯 ] 因為L是正則語言，所以存在一個與之等價的確定有限狀態自動機 ，
假設n是這個確定有限狀態自動機中狀態的數量，
假設
w
∈
L
{\displaystyle w\in L}
|
w
|
≥
n
{\displaystyle \left|w\right|\geq n}
在這個自動機讀入w的前n個字符後一定有一個狀態達到過兩次，
也就是說對於其中一種w的分解方式w=xyz有
δ
∗
(
s
,
x
)
=
δ
∗
(
s
,
x
y
)
{\displaystyle \delta ^{*}\left(s,x\right)=\delta ^{*}\left(s,xy\right)}
因此對於所有的
k
≥
0
{\displaystyle k\geq 0}
δ
∗
(
s
,
x
y
z
)
∈
L
↔
δ
∗
(
s
,
x
y
k
z
)
∈
L
{\displaystyle \delta ^{*}(s,xyz)\in L\leftrightarrow \delta ^{*}(s,xy^{k}z)\in L}
通過泵引理可以用反證法 證明L不是正則語言。證明的時候需要注意以下幾點：
假設要證明的語言為正則語言
n
{\displaystyle n}
w
{\displaystyle w}
w
∈
L
{\displaystyle w\in L}
|
w
|
≥
n
{\displaystyle \left|w\right|\geq n}
x
,
y
,
z
{\displaystyle x,y,z}
找到一個
k
{\displaystyle k}
x
y
k
z
∉
L
{\displaystyle xy^{k}z\notin L}
一個證明L不是正則語言的例子
證明
L
01
=
{
0
n
1
n
|
n
≥
1
}
{\displaystyle L_{01}=\{0^{n}1^{n}|n\geq 1\}}
假設
L
01
{\displaystyle L_{01}}
選擇
w
=
0
n
1
n
∈
L
{\displaystyle w=0^{n}1^{n}\in L}
|
w
|
≥
n
{\displaystyle \left|w\right|\geq n}
於是存在
x
,
y
,
z
{\displaystyle x,y,z}
w
=
x
y
z
{\displaystyle w=xyz}
|
x
y
|
≤
n
{\displaystyle \left|xy\right|\leq n}
|
y
|
≥
1
{\displaystyle \left|y\right|\geq 1}
∀
k
≥
0
:
x
y
k
z
∈
L
01
{\displaystyle \forall k\geq 0:xy^{k}z\in L_{01}}
因為
|
x
y
|
≤
n
{\displaystyle \left|xy\right|\leq n}
|
y
|
≥
1
{\displaystyle \left|y\right|\geq 1}
y
{\displaystyle y}
1
{\displaystyle 1}
0
{\displaystyle 0}
當
k
=
0
{\displaystyle k=0}
x
y
k
z
=
x
y
0
z
=
x
z
{\displaystyle xy^{k}z=xy^{0}z=xz}
x
z
{\displaystyle xz}
1
{\displaystyle 1}
0
{\displaystyle 0}
x
z
∉
L
01
{\displaystyle xz\notin L_{01}}
與泵引理的第三條矛盾，因此
L
01
{\displaystyle L_{01}}
並不是所有滿足泵引理的語言都是正則語言。
L
=
{
a
m
b
n
c
n
|
m
,
n
≥
1
}
∪
{
b
m
c
n
|
m
,
n
≥
0
}
{\displaystyle L=\{a^{m}b^{n}c^{n}|m,n\geq 1\}\cup \{b^{m}c^{n}|m,n\geq 0\}}
Jeffrey Jaffe 發展出了一個普遍化的泵引理，使它可以證明一個語言是正則語言。它的描述如下：
一個語言
L
⊆
Σ
∗
{\displaystyle L\subseteq \Sigma ^{*}}
n
∈
N
{\displaystyle n\in \mathbb {N} }
w
∈
Σ
∗
{\displaystyle w\in \Sigma ^{*}}
w
=
x
y
z
{\displaystyle w=xyz}
|
x
y
|
≤
n
{\displaystyle \left|xy\right|\leq n}
|
y
|
≥
1
{\displaystyle \left|y\right|\geq 1}
∀
k
≥
0
{\displaystyle \forall k\geq 0}
∀
v
∈
Σ
∗
:
x
y
z
v
∈
L
↔
x
y
k
z
v
∈
L
{\displaystyle \forall v\in \Sigma ^{*}:xyzv\in L\leftrightarrow xy^{k}zv\in L}
一個可行的用於判斷一個語言是否為正則語言的方法，可以參見邁希爾－尼羅德定理 。一般來說證明一個語言是正則的，可以通過對該語言構造一個有限狀態機 或正則表達式 來實現。
上下文無關語言的泵引理 [ 編輯 ] 若 L 是上下文無關語言 ，則存在一常數 n > 0 使得語言 L 中每個字串 w 的長度 |w | ≧ n ，而當 w = uvxyz 時：
|vxy | ≦ n ，
|vy | ≧ 1，且
對所有的 k ≧ 0，字串 uvk xyk z 屬於 L 。 透過泵引理 以反證法 證明 L 不是上下文無關語言 。
L
=
{
a
n
b
n
c
n
|
n
≥
1
}
{\displaystyle L=\{a^{n}b^{n}c^{n}|n\geq 1\}}
L
=
{
a
i
b
i
c
i
|
i
≥
0
}
{\displaystyle L=\{a^{i}b^{i}c^{i}|i\geq 0\}}
L
=
{
a
i
b
i
c
i
|
i
≥
2
}
{\displaystyle L=\{a^{i}b^{i}c^{i}|i\geq 2\}}
L 就是包含
a
∗
b
∗
c
∗
{\displaystyle a^{*}b^{*}c^{*}}
a 、b 、c 三者數目相同的語言。
令 n 為泵引理 常數，
w
=
a
n
b
n
c
n
{\displaystyle w=a^{n}b^{n}c^{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
i
b
j
|
j
=
i
2
}
{\displaystyle L=\{a^{i}b^{j}|j=i^{2}\}}
令 n 為泵引理 常數，
w
=
a
n
b
n
2
{\displaystyle w=a^{n}b^{n^{2}}}
w = uvxyz ，而 |vxy | ≤ n ，|vy | ≥ 1
若 vxy 只包含 a ，則 uxz 會包含不到 n 個 a 及
n
2
{\displaystyle n^{2}}
b ，不屬於 L ；
若 vxy 只包含 b ，則 uxz 會包含 n 個 a 及不到
n
2
{\displaystyle n^{2}}
b ，不屬於 L ；
若 vxy 裏有 a 也有 b ，
若 v 或 y 包含 a 與 b ，
u
v
2
x
y
2
z
{\displaystyle uv^{2}xy^{2}z}
{
a
i
b
j
}
{\displaystyle \{a^{i}b^{j}\}}
若 v 只包含 l 個 a ，且 y 只包含 m 個 b ，
u
v
1
+
k
x
y
1
+
k
z
{\displaystyle uv^{1+k}xy^{1+k}z}
n + lk 個 a 與
n
2
+
m
k
{\displaystyle n^{2}+mk}
b ，由於兩者都是線性成長，不可能永遠滿足
{
a
i
b
j
|
j
=
i
2
}
{\displaystyle \{a^{i}b^{j}|j=i^{2}\}}
L 。
因此，無論是上述何種狀況，L 都不會是上下文無關語言。
L
=
{
w
w
|
w
∈
{
0
,
1
}
∗
}
{\displaystyle L=\{ww|w\in \{0,1\}^{*}\}}
令 n 為泵引理 常數，
w
=
0
n
1
n
0
n
1
n
{\displaystyle w=0^{n}1^{n}0^{n}1^{n}}
L ，w = uvxyz ，而 |vxy | ≤ n ，則 vxy 必然為
0
i
1
j
{\displaystyle 0^{i}1^{j}}
1
j
0
i
{\displaystyle 1^{j}0^{i}}
i
,
j
∈
N
,
i
+
j
≠
0
{\displaystyle 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
≠
j
a
n
d
j
≠
k
}
{\displaystyle L=\{x^{i}y^{j}z^{k}|i\neq j\;and\;j\neq k\}}
L
=
{
b
n
a
2
n
b
n
|
n
≥
0
}
{\displaystyle L=\{b^{n}a^{2n}b^{n}|n\geq 0\}}
L
=
{
a
n
b
m
c
m
|
n
,
m
≥
0
}
{\displaystyle L=\{a^{n}b^{m}c^{m}|n,m\geq 0\}}
^ 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.
^ Jeffery Jaffe: A necessary and sufficient pumping lemma for regular languages （頁面存檔備份 ，存於互聯網檔案館 ）
