[音乐]嗨，欢迎回来。
那么接下来呢我们来介绍一个叫做泵引理，嗯，这么一个定理。
我们实际上我们说有，对于有限状态机来说，它的状态
数量是有限的，所以呢我们可能会猜想它很可能它做的事情也 必须要很有限。
因为我们在介绍这个短语结构文法的 时候，短语结构语法的时候我们就指出来说
有一些的这个语言，或者有一些字符上集合 它没法用这个正则表达式来表示，
那么，既然正则表达式或者说正则文法它跟这个有限状态机其实是一一
对应的，所以呢我们说有限状态接大概也不能够做一些事情。
那么所以呢我们就介绍这个泵引理，来看看有限状态机
它所能够识别的这个语言都有什么样的一个特征，从机器的角度上来说。
当然从文法、 从正则表达式角度上来说我们都 已经历经了、 例数了它的不少的这个特征，我们从机器的角度上
来说，那这个泵引理呢挺形象的，因为我们接触到的泵呢本来就是一个机器，
看看这个有限状态机和泵有什么关系。
这个泵引理是说 只要是长度超过状态数目，这里来了，
有限状态，它最要命的就是它的状态数目是有限的。
那么，我们说这个串，如果串的这个包含的字符的长度超过了这个
状态的数目的话，而这个串呢同时会被有限状态机接受；
长度超过状态数目的接受串w，它这个泵引理是
这个，嗯，断言说 这个w呢都可以表示成w=xyz这样的
形式，那所有的xyz就是头尾相连把它切成三段； 第一段叫x，第二段叫y，第三段叫z。
它都有这样一个形式，而且呢 就把这个y中间这一段，它为什么切成这三段呢？
它是说中间这段y不管重复多少次 也同样会被M接受，那么这个呢就好象一个泵
在那儿旋转，转一圈这个y，转两圈y平方；
转三圈y重复三次，转四圈y重复四次 这样， 那所以呢它叫做泵引理。
嗯，也就是说只要长度，字符包含的字符长度超过状态数目 这个，这个w它能够被有限状态机接受
那么这个w呢都会、 都可以被表现成三段的这种形式，其中的中间这一段
可以不停的重复很多次，嗯，这些所有产生的这些 所有的新的这些串，比w更长的这些 串都能够被M所接受。
那么我们来证明这一点， 假设呢w所对应的这个状态序列它是s0,s1,s2,sn；
因为我们，既然它是一个接受串嘛！那么根据我们所谓接受的这个定义
那么它就存在一条拟路径，对吧？拟路径呢从s0这个节点出发， 然后有a1，然后s1，a2，s2；一直到
嗯，这个an，sn，那么所以呢把单，单独把结点序列提出来就是一个状态序列，从s0- 到sn。
那么既然是s0到sn，这个n的 它的，n本身这个数值就大于状态的数目
s的基数，s的基数。
我们刚才说了 这个它的长度超过了这个状态数目，所以这个n呢大于状态数目。
所以呢根据这个鸽笼原理，鸽笼原理就是说，嗯，n只鸽子放在n-1个笼子里
那么必然会有一只笼子至少有两只鸽子，对吧？
那么所以呢这个根据鸽笼原理说，必然这个s0到sn之间会有两个是一样的状态、 相同的状态。
比如说，i和j啊就会有si=sj，而且i比j小。
它不会，它必然是小，必然是不同的两个数。
那我们就从这个i,j这儿开始把这个w呢砍成三段，
第一段呢就是a1到ai， 第二段呢y=ai+1到aj，
第三段呢是aj+1到an，这样呢这个三段就出来啦！ 那么它总量拼起来呢还是a1到an，这个没错。
那么这样呢这个x，当这个有限状态机
读完了ai之后它的状态呢就会停在si，对吧？ 那么我们看看右边这个图就知道了，从s0出发
读，因为x是一个字符串，那么历经这是一个缩略图，好，缩略图。
它历经这个x之后 它最终呢会停在si这个状态。
那么xy 就是再读y，那么因为y呢这个会停在sj这个状态，
而sj状态和si状态是同一个状态，所以那就相当于si
这样的读如了一个y以后又会回到si，那么所以呢， 就是你不管读这个y多少次
比如说m次，多少次它都会停在这个si。
那么就右边这个图的这个样子，所以呢就像一个泵一样 不停的转啊转、 转，转完了以后你如果再读如z的话，
那么最后呢这个xy的m次z它的结尾状态还是z的结尾状态sn； 就是接受这个状态。
所以呢这个 泵引理呢是非常的简洁，嗯，那么证明起来呢也不难。
那么它这呢恰恰也说明了有限状态机 它对于这个字符串的识别、
字符串的模式呢有某一种的 这个局限性。
是吧？那么它有什么用？那么用处呢其实也，
其中的一个用处也就是用来证明某一些语言它不是正则语言。
比如说我们下面来证明ambm那个m>0 这样的不是正则语言。
那ambm这种模式呢就是说，嗯，这个所有的字符串 左边全是a右边全是b，然后呢a跟b的数量相等；
那所以呢事情坏就坏在这个数量相等上。
我们知道这个正则表达是a*b*， 它也是左边全是a右边全是b，但是这个*呢它是相互
独立的，它并没有指就是说a的数量和b的数量有什么关联。
嗯，那么这儿呢我们这个集合，特殊的集合，特殊语言，就是a和b的数量是一样的。
比如ab ,aabb， aaabbb这样的，嗯，它不是正则语言那我们用泵引理来进行证明。
嗯，我们用反证法，假设L是一个正则语言 那么就会有一个有限状态机M来接受这个L。
那么我们假设这个M的这个状态个数为k，它既然是有限的嘛！它所以 这个状态的个数我们假设它是一个k。
好，我们既然有了这个k我们就构造一个字符串 akbk，就是左边有k个a右边有k个b；
那这样呢已经是两倍的k了，两倍的k，那肯定它的这个长度会超过k。
那么既然超过了这个状态的个数k，那么根据泵引理
来说我们就可以把w拆成三段，有xyz，其中的这个y呢是非空的；
嗯，同时呢xy平方z也会被M所接受 也就是把这个y呢重复一次也能够被M所接受。
那么，能够被M所接受那就意味着什么？ 意味着它遵循这个字符串的模式，
也就是说左边全是a右边全是b，然后ab的数量相等。
这个是唯一被M所接受的的字符串的模式，那么接下来我们看看会不会有问题。
然后我们来看中间这个y，因为y被重复了一次，xz没变嘛！所以我们把注意力集中在这- 个y上。
我们说y呢它就有两种情况，要么呢它仅含有a或者仅含有b； 那这样的话如果用y重复一次
那这样呢要么就会ab a变多要么b变多，也就说a和b的这个个数就不相等了。
那既然不相等了，那就不会符合ambm这样的一个模式。
那么这个字符串呢就不会属于L，那好，我们碰到了困难再转向另一种可能，
就是y呢同时含有ab而且数量相等。
那么这样重复一下，但是重复一下呢我们知道这个所谓的重复一下是把 y呢再，再放在y的后边再放一下。
而y当中已经重复混合了ab 那y的平方一定会出现这个a在b之后的情况，
那么这就破坏了a始终在，所有的a都在 所有的b的左边这么一个规则，所以呢xy平方z也不属于L。
那这两种情况穷举了都不属于L，那就是一个 出现矛盾，就是说y平方z呢不会被M所接受。
那既然不会被M所接受呢，这个两个矛盾就说明了我们假设是错误的， 那我们最初的假设是说L是一个正则语言，
因为泵引理不会错，所以只能说是L是正则语言这个事情是错的。
那既然是错的呢，就L就不是正则语言。
那么同样呢，我们以前我们举个例子 amcbm它也不是正则语言。
所以我们说只要涉及到这个数量关系 嗯，它都，这种的模式啊，它都不会是正则语言。
因为从正则表达式来说这个*号 它每一个*号相互都是独立，它们相互之间
是没有这个数量的关系的这个约束， 这个呢就是正则语言它的短处了。
陈斌副教授
