泵引理

在可计算性理论中的形式语言理论中，泵引理（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.