泵引理

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

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

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

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

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

應用
通过泵引理可以用反證法證明L不是正则語言。证明的时候需要注意以下几点：
#假设要证明的语言为正则语言
#n是未知的
#w可以在满足w \in L和\left| w \right| \ge n的条件下自由选择
#x,y,z也是未知的
#找到一个k，使得xy^kz \notin L，也就是说和泵引理的第三条矛盾
一个证明L不是正则语言的例子
*证明L_{01} = \{0^n1^n|n\geq1\}不是正则语言
**假设L_{01}是正则语言，令n為泵引理常數
**选择w = 0^n1^n \in L，则\left| w \right| \ge n
**于是存在x,y,z使得w=xyz满足条件\left| xy \right| \le n，\left| y \right| \ge 1，\forall k \ge 0:xy^kz \in L_{01}。
**因为\left| xy \right| \le n且，\left| y \right| \ge 1所以y中不包含1但最少有一个0
**当k=0的时候，xy^kz = xy^0z = xz，xz中1的数量比0多，所以xz \notin L_{01}
**与泵引理的第三条矛盾，因此L_{01}不是正则语言

普遍化的泵引理
并不是所有满足泵引理的语言都是正则语言。L = \{ a^mb^nc^n | m,n \ge 1 \} \cup \{b^mc^n|m,n \ge 0 \}就是这样的一个例子，它虽然满足泵引理，但并不是正则语言。Jeffrey Jaffe发展出了一个普遍化的泵引理，使它可以证明一个语言是正则语言。它的描述如下：
一个语言L \subseteq \Sigma^是正则语言，当且仅当存在一个自然数n \in \mathbb{N}，使得任意字符串w\in \Sigma^*可以通过至少一种方式被写成w = xyz的形式时，以下说法成立：
**#\left| xy \right| \le n，
**#\left| y \right| \ge 1，
*#\forall k \ge 0，\forall v \in \Sigma^ :xyzv \in L \leftrightarrow xy^kzv \in L。
一个可行的用于判断一个语言是否为正则语言的方法，可以参见迈希尔－尼罗德定理。一般来说证明一个语言是正则的，可以通过对该语言构造一个有限状态机或正则表达式来实现。

上下文無關語言的泵引理
定義
若 L 是上下文無關語言，則存在一常數 n > 0 使得語言 L 中每個字串 w 的長度 |w| ≧ n，而當 w = uvxyz 時：
#|vxy| ≦ n，
#|vy| ≧ 1，且
#對所有的 k ≧ 0，字串 uvkxykz 屬於 L 。

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

L = \{a^nb^nc^n|n \geq 1 \} 或 L = \{a^ib^ic^i|i \geq 0\} 或 L = \{a^ib^ic^i|i \geq 2\}，換句話說，L 就是包含 a^b^c^ 所有字串且 a、b、c 三者數目相同的語言。
*令 n 為泵引理常數，w = a^nb^nc^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^ib^j|j = i^2\}
*令 n 為泵引理常數，w = a^nb^{n^2}，w = uvxyz，而 |vxy| ≤ n，|vy*| ≥ 1
*#若 vxy 只包含 a，則 uxz 會包含不到 n 個 a 及 n^2 個 b，不屬於 L*；
*#若 vxy 只包含 b，則 uxz 會包含 n 個 a 及不到 n^2 個 b，不屬於 L*；
*#若 vxy 裡有 a 也有 b*，
*##若 v 或 y 包含 a 與 b*，uv^2xy^2z 不在 \{a^ib^j\} 裡；
*##若 v 只包含 l 個 a，且 y 只包含 m 個 b，uv^{1+k}xy^{1+k}z 會包含 n + lk 個 a 與 n^2 + mk 個 b，由於兩者都是線性成長，不可能永遠滿足 \{a^ib^j|j = i^2\} 的條件，不屬於 L*。
*因此，無論是上述何種狀況，L* 都不會是上下文無關語言。

L = \{ww|w \in \{0,1\}^ \}
*令 n 為泵引理常數，w = 0^n1^n0^n1^n 屬於 L，w = uvxyz，而 |vxy| ≤ n，则 vxy 必然为 0^i1^j 或1^j0^i形式（此处有i,j\in \mathbb{N}, i+j\neq 0）。即 vxy无法同时包含前后两组0，也无法同时包含前后两组1。将uvxyz转变成uxz必然导致前后两组0或两组1的数目产生差异。使得uxz不再满足ww形式。亦即uxz不属于L*。
*因此，L* 都不會是上下文無關語言。

*L = \{x^iy^jz^k|i \ne j \; and \; j \ne k \}
*L = \{b^na^{2n}b^n|n \geq 0\}
*L = \{a^nb^mc^m|n,m \geq 0\}

引用

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

评论 (0)