[音乐]嗨,欢迎回来。
那么接下来呢我们来介绍一个叫做泵引理,嗯,这么一个定理。
我们实际上我们说有,对于有限状态机来说,它的状态
数量是有限的,所以呢我们可能会猜想它很可能它做的事情也 必须要很有限。
因为我们在介绍这个短语结构文法的 时候,短语结构语法的时候我们就指出来说
有一些的这个语言,或者有一些字符上集合 它没法用这个正则表达式来表示,
那么,既然正则表达式或者说正则文法它跟这个有限状态机其实是一一
对应的,所以呢我们说有限状态接大概也不能够做一些事情。
那么所以呢我们就介绍这个泵引理,来看看有限状态机
它所能够识别的这个语言都有什么样的一个特征,从机器的角度上来说。
当然从文法、 从正则表达式角度上来说我们都 已经历经了、 例数了它的不少的这个特征,我们从机器的角度上
来说,那这个泵引理呢挺形象的,因为我们接触到的泵呢本来就是一个机器,
看看这个有限状态机和泵有什么关系。
这个泵引理是说 只要是长度超过状态数目,这里来了,
有限状态,它最要命的就是它的状态数目是有限的。
那么,我们说这个串,如果串的这个包含的字符的长度超过了这个
状态的数目的话,而这个串呢同时会被有限状态机接受;
长度超过状态数目的接受串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它也不是正则语言。
所以我们说只要涉及到这个数量关系 嗯,它都,这种的模式啊,它都不会是正则语言。
因为从正则表达式来说这个*号 它每一个*号相互都是独立,它们相互之间
是没有这个数量的关系的这个约束, 这个呢就是正则语言它的短处了。