泵引理 Pumping Lemma

 📢 参考：

• 抽屉原理（数学原理）_百度百科 (百度.com)
• pumping lemma/泵引理/反复引理 - 知乎 (zhihu.com)
• 【CS106】编译原理笔记4 —— 用普遍性泵引理（Pumping lemma）证明语言的正则性_YY同学Serendipity的博客-CSDN博客_pumping引理
• 【计算理论】Pumping 引理 ( 四个等价概念 | 自动机界限 | Pumping 引理简介 | Pumping 引理证明正则表达式 | Pumping 引理示例分析 )_韩曙亮的博客-CSDN博客

泵引理是用于判断一个语言是否是正则语言的定理。一般在进行正则语言的判断时，

• 如果这种语言可以用 DFA、NFA 或者使用正则表达式来描述，那么这个语言就是正则语言。
• 如果不是正则语言，没有办法画出 DFA 和 NFA 或者写出正则表达式，则可以用pumping lemma来证明。

在正式介绍泵引理之前，首先介绍鸽笼原理的概念，这是泵引理的理论基础

一、鸽笼原理（抽屉原理）

• 一般性含义：设把n 1个元素划分至n个集合中，用分别表示这n个集合对应包含的元素个数，则：至少存在某个集合，其包含元素个数值大于或等于2。
• 形象的例子：桌上有十个苹果，要把这十个苹果放到九个抽屉里，无论怎样放，我们会发现至少会有一个抽屉里面放不少于两个苹果。

二、泵引理原理 (Proof of pummping lemma)

假设正则语言可以被DFA表示，设这个状态机为M，M有p个状态。

我们从该正则语言中选取一个长度为 (pumping length, 可理解为等价DFA的状态个数)的字符串s，且s可以被分成x，y，z三部分（），从状态一直到状态，如下图。

在DFA 的单状态性下，每读取一个字符，状态就会进行对应的转换，因此s的p个字符在状态机中应该要移动p次，需要p 1个状态。但是因为状态机M只有p个状态（状态之间的连线只有p-1条），根据鸽巢原理，肯定至少有两次移动在同一个状态上进行（成环）。我们可以假定这个状态为， 如下图， 

从到可以设为x，到为z，而第一个回到为y。这样子，pumping lemma的三个条件就会被满足 

• 条件1：。因为y无论怎么重复，都会回到（回到状态机中，通过z字符串到达接收状态），所以都会被这个DFA接受。
• 条件2：。因为y至少包含了两次，因此显然大于0
• 条件3：。由于，且在需要个状态进行转换的情况下DFA只有p个状态，那么作为s的字串xy（或者假设），的长度也不会超过p。

至此，泵原理的原理介绍完毕

三、泵引理（Pumping lemma）

这里给出正式的泵引理定义：

如果A是正则语言，那么就会有一个数字p（pumping length），使得任意一个A的长度至少为p的字串s，且s可以被分成三个部分，都满足以下三个条件

• 对每个 
• 
• 

使用泵引理证明是否为正则语言的步骤

1. 提出假设 : 首先假设该语言是正则的 ;
2. Pumping 引理证明 : 存在长度至少为 p 的任何字符串 , 都满足 Pumping 引理 的三个性质 ;
3. 矛盾，假设不成立 : 如果不满足 Pumping 引理 , 说明上面假设该语言是正则语言是不成立的，该语言不是正则语言 ;

这篇好文章是转载于：学新通技术网