泵引理

维基百科，自由的百科全书

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

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

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

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

[编辑] 正则語言的泵引理

[编辑] 定义

假设 $L \subseteq \Sigma^*$ 是正则语言，則存在一个自然数 $n \in \mathbb{N}$ ，使得每一个字符串 $w \in L$ 且 $w \ge n$ 可以通过至少一种方式被写成w = xyz的形式时，以下说法成立：

$\left| xy \right| \le n$ ，
$\left| y \right| \ge 1$ ，
$\forall k \ge 0:xy^kz \in L$ 。

泵引理也可以写成以下的形式：…… $w \notin L$ …… $\rightarrow$ …… $xy^kz \notin L$ ……

[编辑] 正确性的证明

因为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$ 是正则语言，令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的时候， $x y k z = x y 0 z = x z$ ，xz中1的数量比0多，所以 $xz \notin L_{01}$
- 与泵引理的第三条矛盾，因此 $L 01$ 不是正则语言

[编辑] 普遍化的泵引理^[2]

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

一个语言是正则语言，当且仅当存在一个自然数，使得每一个字符串且可以通过至少一种方式被写成w = xyz的形式时，以下说法成立：
- 1. $\left| xy \right| \le n$ ，
  2. $\left| y \right| \ge 1$ ，
  3. $\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，字串 uv^kxy^kz 屬於 L 。

[编辑] 應用

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

或或，換句話說，L 就是包含 a ^* b ^* c ^* 所有字串且 a、b、c 三者數目相同的語言。
- 令 n 為泵引理常數，w = aⁿbⁿcⁿ 屬於 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ⁱb^j | j = i²}
- 令 n 為泵引理常數，，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 + m k$ 個 b，由於兩者都是線性成長，不可能永遠滿足 ${a i b j | j = i 2}$ 的條件，不屬於 L。
- 因此，無論是上述何種狀況，L 都不會是上下文無關語言。

- 令 n 為泵引理常數， $w = 0 n 1 n 0 n 1 n$ 屬於 L，w = uvxyz，而 |vxy| ≤ n，|vy| ≥ 1，則 |uxz|≥ 3n。（未完）

$L = \{x^iy^jz^k|i \ne j \; and \; j \ne k \}$
$L = \{b^na^2nb^n|n \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.
^ Jeffrey Jaffe: A necessary and sufficient pumping lemma for regular languages

Michael Sipser（1997）．Introduction to the Theory of Computation．PWS Publishing．ISBN 0-534-94728-X． Section 1.4: Nonregular Languages, pp.77–83. Section 2.3: Non-context-free Languages, pp.115–119.

分类: 形式语言 | 引理

See also ebooksgratis.com: no banners, no cookies, totally FREE.

泵引理

维基百科，自由的百科全书

目录

[编辑] 正则語言的泵引理

[编辑] 定义

[编辑] 正确性的证明

[编辑] 應用

[编辑] 普遍化的泵引理^[2]

[编辑] 上下文無關語言的泵引理

[编辑] 定义

[编辑] 應用

[编辑] 引用

Views

导航

帮助

搜索

其他语言

See also ebooksgratis.com: no banners, no cookies, totally FREE.

泵引理

维基百科，自由的百科全书

目录

[编辑] 正则語言的泵引理

[编辑] 定义

[编辑] 正确性的证明

[编辑] 應用

[编辑] 普遍化的泵引理[2]

[编辑] 上下文無關語言的泵引理

[编辑] 定义

[编辑] 應用

[编辑] 引用

Views

导航

帮助

搜索

其他语言

[编辑] 普遍化的泵引理^[2]