泵引理

Template:Multiple issues 在可计算性理论中的形式语言理论中，泵引理（Pumping lemma）声称给定类的任何语言可以被“抽吸”并仍属于这个类。一个语言可以被抽吸，如果在这个语言中任何足够长的字符串可以分解成片段，其中某些可以任意重复来生成语言中更长的字符串。这些引理的证明典型的需要计数论证比如鸽笼原理。

两个最重要例子是正则语言的泵引理和上下文无关语言的泵引理。鄂登引理是另一种更强的上下文无关语言的泵引理。

这些引理可以用来确定特定语言不在给定语言类中。但是它们不能被用来确定一个语言在给定类中，因为满足引理是类成员关系的必要条件，但不是充分条件。

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

正则語言的泵引理

定义

假设$L\subseteq {\mathrm{\Sigma }}^{*}$是正则语言，则存在整数$n\ge 1$，对任意字符串$w\in L$且$\left|w\right|\ge n$（n为泵长度，可理解为正则语言等效的极小化DFA的状态个数），可以将$w$写成$w=xyz$的形式，使得以下说法成立：

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

正确性的证明

• 因为L是正则语言，所以存在一个与之等价的确定有限状态自动机，
• 假设n是这个确定有限状态自动机中状态的数量，
• 假设$w\in L$和$\left|w\right|\ge n$
• 在这个自动机读入w的前n个字符后一定有一个状态达到过两次，
• 也就是说对于其中一种w的分解方式w=xyz有${\delta }^{*}(s,x)={\delta }^{*}(s,xy)$
• 因此对于所有的$k\ge 0$都有${\delta }^{*}(s,xyz)\in L\leftrightarrow {\delta }^{*}(s,x{y}^{k}z)\in L$

應用

通过泵引理可以用反證法證明L不是正则語言。证明的时候需要注意以下几点：

1. 假设要证明的语言为正则语言
2. $n$是未知的
3. $w$可以在满足$w\in L$和$\left|w\right|\ge n$的条件下自由选择
4. $x,y,z$也是未知的
5. 找到一个$k$，使得$x{y}^{k}z\notin L$，也就是说和泵引理的第三条矛盾

一个证明L不是正则语言的例子

• 证明$L_{01}=\{0^n{1}^n|n\ge 1\}$不是正则语言
  • 假设$L_{01}$是正则语言，令n為泵引理常數
  • 选择$w=0^n{1}^n\in L$，则$\left|w\right|\ge n$
  • 于是存在$x,y,z$使得$w=xyz$满足条件$\left|xy\right|\le n$，$\left|y\right|\ge 1$，$\mathrm{\forall }k\ge 0:x{y}^{k}z\in L_{01}$。
  • 因为$\left|xy\right|\le n$且，$\left|y\right|\ge 1$所以$y$中不包含$1$但最少有一个$0$
  • 当$k=0$的时候，$x{y}^{k}z=x{y}^{0}z=xz$，$xz$中$1$的数量比$0$多，所以$xz\notin L_{01}$
  • 与泵引理的第三条矛盾，因此$L_{01}$不是正则语言

普遍化的泵引理

并不是所有满足泵引理的语言都是正则语言。$L=\{a^m{b}^n{c}^n|m,n\ge 1\}\cup \{b^m{c}^n|m,n\ge 0\}$就是这样的一个例子，它虽然满足泵引理，但并不是正则语言。Jeffrey Jaffe发展出了一个普遍化的泵引理，使它可以证明一个语言是正则语言。它的描述如下：

• 一个语言$L\subseteq {\mathrm{\Sigma }}^{*}$是正则语言，当且仅当存在一个自然数$n\in \mathbb{N}$，使得任意字符串$w\in {\mathrm{\Sigma }}^{*}$可以通过至少一种方式被写成$w=xyz$的形式时，以下说法成立：
  • 1. $\left|xy\right|\le n$，
    2. $\left|y\right|\ge 1$，
    3. $\mathrm{\forall }k\ge 0$，$\mathrm{\forall }v\in {\mathrm{\Sigma }}^{*}:xyzv\in L\leftrightarrow x{y}^{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 不是上下文無關語言。

• $L=\{a^n{b}^n{c}^n|n\ge 1\}$ 或 $L=\{a^i{b}^i{c}^i|i\ge 0\}$ 或 $L=\{a^i{b}^i{c}^i|i\ge 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，$u{v}^{2}x{y}^{2}z$ 不在 $\{a^i{b}^j\}$ 裡；
       2. 若 v 只包含 l 個 a，且 y 只包含 m 個 b，$u{v}^{1+k}x{y}^{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\ne 0$）。即 vxy无法同时包含前后两组0，也无法同时包含前后两组1。将uvxyz转变成uxz必然导致前后两组0或两组1的数目产生差异。使得uxz不再满足ww形式。亦即uxz不属于L。
  • 因此，L 都不會是上下文無關語言。

• $L=\{x^i{y}^j{z}^k|i\ne jandj\ne k\}$
• $L=\{b^n{a}^{2n}{b}^n|n\ge 0\}$
• $L=\{a^n{b}^m{c}^m|n,m\ge 0\}$

引用

• Template:Cite book Section 1.4: Nonregular Languages, pp.77–83. Section 2.3: Non-context-free Languages, pp.115–119.