pumping lemma/泵引理/反复引理

pumping lemma是我在阅读<<The introduction of the computation theory>>遇到的一个引理，常用于证明一个language不是regular的！

感觉还挺好玩的，而且我也花了一定的时间才理解它，所以记录在这里。

计算理论研究的问题阅读导论 Introduction to the theory of computation导论

要明白这个引理，需要理解什么是正则语言，DFA，NFA。

• 正则语言（regular language）是指可以被DFA识别的语言。
• DFA与NFA是等价的，具有相同的计算能力。
• DFA是确定性有限状态机（deterministic finite automaton)，NFA (nondeterministic finite automaton)则是不确定性有限状态机。后面再开文章讲述一下。

所以这个引理的作用之一，就是如果我们要解析一种语言，看看是否可以用DFA、NFA表示。

比如判定是不是正则语言。

注：引理是指常用于证明某些命题真假的定理。

pumping lemma

pumping lemma直译为泵引理，有些人又说意为反复引理更直观。

它的意思是如果一个语言是正则的话，那么选取其中的一个特定字符串，重复字符串一部分得到的新串仍然属于这个语言。也就是,

那么 也是正则字符串。

因为字串y可以被一直重复，也就是反复出现，所以有人喜欢反复引理。

不过pump有涌出的意思，所以不停地涌出重复子串后，仍然属于A，那么泵引理也是可以的接受的翻译。

言归正传，让我们看看它的定义以及使用例子。

pumping lemma如果一个语言A是正则语言，那么存在一个数p，使得任何A中长度至少为p的字符串s，可以被分割为三部分为，并满足如下三个条件，

• 对于所有的 ,
• 
• 

表示字符串y的长度。

用途

这个引理的证明先略过，让我们看看它的用途——判定语言是不是正则语言。

假设，它是正则语言（有两部分组成，第一部分都是0，第二部分都是1，且0和1的个数相等。

可以令，如果x和z都是空字符串，那么条件1和2都可以满足。

但是条件3不行，因为 说明y只能含有0字符，因为s开始p个字符是0。

如果y只有0字符，那么中0和1的个数就不相等了，所以不属于条件1不满足，与一开始说条件1满足相违背。所以B不是正则语言。

证明假设正则语言可以被DFA M 表示。

M有p个状态，我们选取一个长度为p的字符串s。

s从状态一直到状态，如下图。

因为的长度为,那么经过的状态肯定为，根据鸽巢原理，肯定有两个状态是同一个。

我们可以假定这个状态为， 如下图，

从到可以设为，到为，而第一个经过的到为.

这样子，pumping lemma的三个条件就会被满足——

条件1,因为y无论怎么重复，都会回到q_9，所以xy^iz都会被这个DFA接受。

条件2，因为显然大于0，因为它至少包含了q_9两次。

条件3，因为y的开头是第一个经过的，总的状态为, 那么肯定小于等于.

我一开始还疑惑比如正则语言"abcd"，它的长度只有4，为什么这三个条件会被满足。
现在我才理解了，因为当我令的时候，没有字符串有长度是5,所以结论自然而然成立。

就像你说当太阳如果小于乒乓球，那么地球就会爆炸。这个命题是成立的。因为不能证伪。

这也就是数学中的蕴含关系 ，当为假的时候，这个命题是成立的。

所以pumping lemma可以让我们判定一个语言不是正则的。

而方法的关键是假设要判定的语言是正则的，然后选取一个p，并构造一个字符串s，使得三个条件不满足。也就是反证法。

本文第一次用Zhihu on VScode发布。因为知乎的编辑器经常抽风，所以换个工具试试。