当前课程知识点：软件理论基础 > 第六章 正则语言的性质与DFA优化 > 6.2 泵引理 > Video
欢迎同学们来到《软件理论基础》的MOOC课堂
现在介绍第六章
正则语言的判定性质 第二节 泵引理
我们要讲的是鸽巢引理还有泵引理
首先我们复习一下前面的鸽巢引理
这是在第一章里面我们已经介绍过
有n只鸽子
我们要把n只鸽子要放在m个笼子里面
如果n大于m的话
那我们就看这个巢穴里面
至少有一个巢穴
有两只或者两只以上的鸽子
实际上这就是我们原来学的抽屉原则
这个引理非常简单
那我们现在要用这个引理
要解决我们后面的问题
在前面我们已经学了正则语言
那正则语言像这样表示的
这样表示的
这样表示的
这些对应的语言都是正则语言
实际上正则语言是我们接触的语言当中
很小的一部分
那还有很多语言
实际上像这样的语言
我们之前也见过
还有这样的语言等等
他们不是正则语言
那对于正则语言来说
我们前面讲了
怎么去判断这个正则语言呢
就看它的DFA能不能画得出来
它的NFA能不能画得出来
或者是它的正则表示能不能写得出来
还有正则文法要是能够表示出来
那这个语言肯定是正则语言
那我们怎么去证明一个语言
不是正则语言呢
那我们说是不是证明它
没有DFA来接受这个语言呢
这个想法是不可能呢
那我们的方法就是用泵引理
首先看看这里有四个状态的DFA
q1、q2、q3、q4
我们知道变迁与状态的关系
我一个变迁实际上它连接的是两个状态
那我两个变迁一般的我连接了
或者是一个状态
或者那是自环
或者是两个状态
或者是三个状态
如果是它没有环的话
那它至少要连接三个状态
再看看假如这个字符串
它是大于或等于4的时候
那我们这四个状态的DFA
那这里面肯定有一个状态就会出现重复
一般的我们假设这个字符串的个数
大于或等于自动机状态的个数
那这个时候我们可以看看
在这个自动机的路径上面
至少会有一个状态会出现重复
对一般的字符串来说
我们用变迁来表示鸽子
用这个状态来代表这个笼子
实际上这是我们用前面的鸽巢引理
就可以看出来
我们对一个无限的正则语言
我就可以讨论它的语言的一些必要条件
现在为什么讨论是无限的正则语言呢
因为对于有限的正则语言
它肯定有DFA
也就是说只要是有限的
它肯定是正则的
我要去判定一个语言不是正则的话
那这个语言它肯定不会是有限的
那我们看看对于一个无限的正则语言
它能满足什么样的条件
如果这样的语言不满足这个条件的话
那这个语言肯定就不是正则的
我们首先就看这个无限的正则语言L
如果要接受它的DFA的话
这个DFA状态的个数是n个
假设这个字符串W是∈L的
因为这个语言是无限的
所以这个字符串它的长度
可以说是要多长有多长
如果这个字符串的长度是大于或等于n
也就是DFA当中状态的个数
那根据我们刚才介绍的鸽巢引理
W这个路径上面
至少会有一个状态会出现重复
我们假设q是这个路径上面
第一个出现重复的
我们就可以把这一个路径W
就可以分解为
你看从初始状态到q的这么一个子串x
还有从q开始这个环路y
在剩下的这一部分就是我们的z
也就是W可以表示成为xyz三个部分
我们看因为这个q是第一次出现重复的
所以 x和y
它整个这个长度
肯定不会超过整个自动机的状态个数
也就是小于或等于n
这个q是出现重复的
也就是它的环的上面是有字符的
也就是y的长度肯定是大于或等于1的
那我们再看 从初始状态开始
我利用x字符串到q
到q呢 我这个时候我不在这里做它的环路
我就直接由前面走到终态
那从这个自动机的这个属性
它是初态x再走z到终态
因此这个xz它应该属于这个语言里面
我从初态到了q
我在这里完成一个自环
完成一个环路y
然后因为这反正是一个环路
我在上面转多少次没关系
我再转一次
也就是连接一个y
再之后从q到终态
那从这个自动机你看
也是从初态这个串 它最后到了终态
因此 这个串也是在这个语言里面
那还有我们可以在q这个地方
我们还可以重复一次
那xyyz也在这个语言里面
一般的 对于任意的i
i等于0，1，2等等
xy的i次方z
都应该在这个正则语言里面
也就是说只要是它是一个无限正则语言
它必须满足这个条件
这就是我们的泵引理
我们把刚才的泵引理
用下面的语言来叙述
给定一个无限的正则语言L
它一定存在一个正整数m
你像我们刚才的DFA状态的个数
实际上可以看出一个m
实际上比m大的任何一个正整数
都可以作用我们正面的正整数
那对于任意的W∈L
只要这个W等于或等于m的话
这个W它一定能够分解为x、y、z
也就存在x、y、z三个子串
这三个子串 它要满足下面这两个条件
xy它的长度是小于或等于这里面的m的
而y的长度 它是大于或等于1的
在这样的串
xy的i次方z
我们也就是表示成wi
它一定是∈L的
这里对任意的i 它都是成立的
只要是无限的正则语言
这个结论是一定成立的
这也就是无限正则语言
它满足的必要条件
我们下面就要通过这个条件
来判定一些语言不是正则语言
好 这节内容介绍到这里
谢谢大家
-1.1 概要
--第一节
-1.2 数学基础
--Video
-1.3 图
--Video
-1.4 证明方法
--Video
-1.5 语言基础
--Video
-1.6 语言运算
--Video
-习题--作业
-2.1 确定有限自动机的概念
--Video
-2.2 确定有限自动机的定义
--Video
-2.3 扩展转移函数
--Video
-2.4 正则语言
--Video
-2.5 DFA构造
--Video
-习题--作业
-3.1 非确定有限自动机的概念
--Video
-3.2 e转移
--Video
-3.3 非确定有限自动机的定义
--Video
-3.4 扩展转移函数
--Video
-3.5 等价性证明
--Video
-3.6 文本搜索
--Video
-习题--作业
-4.1 单一终结状态的NFA
--Video
-4.2 正则语言的运算性质
--Video
-4.3 正则表示和语言
--Video
-4.4 正则表示和正则语言
--Video
-4.5 正则语言的同态
--Video
-4.6 正则表示的代数定律
--Video
-习题--作业
-5.1 文法
--Video
-5.2 线性文法
--Video
-5.3 正则文法与正则语言
--Video
-5.4 自动机的积
--Video
-习题--作业
-6.1 基本问题
--Video
-6.2 泵引理
--Video
-6.3 非正则语言的判定 1
--Video
-6.4 非正则语言的判定 2
--Video
-6.5 DFA的优化 1
--Video
-6.6 DFA的优化 2
--Video
-习题--作业
-7.1 上下文无关文法
--Video
-7.2 规约和推导
--Video
-7.3 语法分析树
--Video
-7.4 规约、推导和语法分析树之间的关系
--Video
-7.5 上下文无关语言
--Video
-习题--作业
-8.1 CFG的应用
--Video
-8.2 CFG的转化
--Video
-8.3 文法二义性
--Video
-8.4 二义性的消除方法
--Video
-8.5 CFG的构造方法
--Video
-8.6 CFG的构造实例
--Video
-第八章 CFG的应用与文法的二义性--习题
-9.1 PDA介绍
--Video
-9.2 PDA的定义
--Video
-9.3 PDA的即时描述
--Video
-9.4 PDA的语言
--Video
-9.5 PDA与CFG的关系
--Video
-习题--作业
-10.1 确定下推自动机
--Video
-10.2 DPDA与其他语言的关系
--Video
-10.3 终态型DPDA和空栈型DPDA
--Video
-10.4 消除无用符号
--Video
-10.5 消除e产生式
--Video
-10.6 消除单一产生式
--Video
-10.7 CFG的化简与Chomsky范式
--Video
-习题--作业
-11.1 CFL的必要条件
--Video
-11.2 CFL的Pumping引理
--Video
-11.3 CFL的闭运算性质
--Video
-11.4 CFL的同态性质
--Video
-11.5 CFL的交运算
--Video
-11.6 CFL的判定性质
--Video
-习题--作业
-12.1 图灵机的介绍
--Video
-12.2 图灵机的定义
--Video
-12.3 图灵机的即时描述
--Video
-12.4 图灵机的计算
--Video
-12.5 图灵机的编程技术
--Video
-习题--作业
-13.1 Turing理论
--Video
-13.2 图灵机带的扩展
--Video
-13.3 图灵机移动的扩展
--Video
-13.4 受限图灵机
--Video
-13.5 图灵机与其他自动机
--Video
-习题--作业
-14.1 图灵机编码
--Video
-14.2 对角线语言与通用语言
--Video
-14.3 图灵机语言的性质
--Video
-14.4 判定问题和语言
--Video
-14.5 计算复杂性问题
--Video
-第十四章 不可判定问题--习题
-15.1 时间自动机
--Video
-15.2 Buchi自动机
--Video
-15.3 软件形式化验证
--Video
-15.4 模型检测方法
--Video
-15.5 M3C模型检测系统
--Video
-习题--作业
-期中考试
