查看“︁泵引理”︁的源代码

{{Multiple issues|
{{Copy edit|time=2021-02-22T16:08:22+00:00}}
{{Disputed|time=2021-02-22T16:08:22+00:00}}
}}
在[[可计算性理论]]中的[[形式语言]]理论中，'''泵引理'''（Pumping lemma）声称给定类的任何语言可以被“抽吸”并仍属于这个类。一个语言可以被抽吸，如果在这个语言中任何足够长的字符串可以分解成片段，其中某些可以任意重复来生成语言中更长的字符串。这些引理的证明典型的需要[[计数论证]]比如[[鸽笼原理]]。

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

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

泵引理是1961年由 [[Yehoshua Bar-Hillel|Y. Bar-Hillel]]、[[M. Perles]] 和 [[E. Shamir]]首次发表的<ref>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. </ref>。

== 正则語言的泵引理 ==
===定义===
假设<math>L \subseteq \Sigma^*</math>是[[正規語言|正则语言]]，则存在整数<math>n \ge 1</math>，对任意字符串<math>w \in L</math>且<math>\left| w \right| \ge n</math>（n为泵长度，可理解为正则语言等效的极小化DFA的状态个数），可以将<math>w</math>写成<math>w = xyz</math>的形式，使得以下说法成立：
#<math>\left| xy \right| \le n</math>，
#<math>\left| y \right| \ge 1</math>，
#<math>\forall k \ge 0:xy^kz \in L</math>。

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

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

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

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

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

*<math>L = \{a^nb^nc^n|n \geq 1 \}</math> 或 <math>L = \{a^ib^ic^i|i \geq 0\}</math> 或 <math>L = \{a^ib^ic^i|i \geq 2\}</math>，換句話說，''L'' 就是包含 <math>a^*b^*c^*</math> 所有字串且 ''a''、''b''、''c'' 三者數目相同的語言。
**令 ''n'' 為'''泵引理'''常數，<math>w = a^nb^nc^n</math> 屬於 ''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'' 都不會是[[上下文無關語言]]。 

*<math>L = \{a^ib^j|j = i^2\}</math>
**令 ''n'' 為'''泵引理'''常數，<math>w = a^nb^{n^2}</math>，''w'' = ''uvxyz''，而 |''vxy''| ≤ ''n''，|''vy''| ≥ 1
**#若 ''vxy'' 只包含 ''a''，則 ''uxz'' 會包含不到 ''n'' 個 ''a'' 及 <math>n^2</math> 個 ''b''，不屬於 ''L''；
**#若 ''vxy'' 只包含 ''b''，則 ''uxz'' 會包含 ''n'' 個 ''a'' 及不到 <math>n^2</math> 個 ''b''，不屬於 ''L''；
**#若 ''vxy'' 裡有 ''a'' 也有 ''b''，
**##若 ''v'' 或 ''y'' 包含 ''a'' 與 ''b''，<math>uv^2xy^2z</math> 不在 <math>\{a^ib^j\}</math> 裡；
**##若 ''v'' 只包含 ''l'' 個 ''a''，且 ''y'' 只包含 ''m'' 個 ''b''，<math>uv^{1+k}xy^{1+k}z</math> 會包含 ''n'' + ''lk'' 個 ''a'' 與 <math>n^2 + mk</math> 個 ''b''，由於兩者都是線性成長，不可能永遠滿足 <math>\{a^ib^j|j = i^2\}</math> 的條件，不屬於 ''L''。
**因此，無論是上述何種狀況，''L'' 都不會是上下文無關語言。

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

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

== 引用 ==
<references/>
* {{cite book|author = [[Michael Sipser]] | year = 1997 | title = Introduction to the Theory of Computation |url = https://archive.org/details/introductiontoth00sips | publisher = PWS Publishing | id = ISBN 978-0-534-94728-6}} Section 1.4: Nonregular Languages, pp.77–83. Section 2.3: Non-context-free Languages, pp.115–119.

[[Category:形式语言|B]]
[[Category:引理]]