当前课程知识点:软件理论基础 > 第六章 正则语言的性质与DFA优化 > 6.5 DFA的优化 1 > Video
欢迎同学们来到《软件理论基础》的MOOC课堂
我是清华大学的教师吴国民
今天讲述的内容是DFA的优化
内容包括
集合上的等价关系与集合的划分
DFA状态集合上的一个等价关系
状态集划分的算法与填表法
最后我们介绍最优的DFA
首先我们介绍第一部分
集合上的等价关系与集合的划分
在第一章里面我们介绍了
集合上的等价关系以及集合的划分
那我们就讲到
假设R是集合Q上面的一个关系
假设是一个等价关系的话
它就产生一个等价类或者是块
这个块就构成了这个集合Q的一个划分
我们把集合当中任何一个元素a
与a它等价的这一个元素
放在一个集合里面
用这样一个集合表示
也就是所有x与a等价的
这个a是放在这个集合里面
我们叫做a的一个等价类
那我们就对于这个集合Q里面
任何一个元素
它都有唯一的一个等价类
那这就 意思就说明了在集合当中
任何两个元素
要么等价
要么就 他们的等价类是不交的
把所有的等价类 把它并起来之后
它就等于这个集合或者是全集
这就是我们这个集合划分的它的意义
那我们下面就讲DFA集合上的
一个等价关系
在前面我们介绍了自动机
我们知道自动机
它是我们软件理论基础当中
一个重要的一个模型
我们讲了自动机有DFA、NFA
它描述的语言是正则语言
同样一个语言
你可以用不同的DFA来描述
还可以用NFA描述
而且说明这些不同的DFA
不同的NFA
它可以描述同一个语言
因为语言是我们软件理论当中的一个核心
那选择什么样的自动机
来描述这个语言最好呢
那我们知道 希望状态越少越好
因为状态是需要计算机的资源
那怎么样去选择一个较少的状态
描述这样的语言
这是我们这节课要解决的问题
那对于DFA
我们刚才讲了等价关系
是能够减少这个集合元素的一种方法
那下面我们的DFA
怎么样去定义
这个状态集上的一个等价关系
假设我们给的这个DFA这个模型
这就是一个五元组
下面我们这样定义
它的状态集合上的一个关系
就R关系
这个关系是这样的
对于q当中
任何两个元素p和q
p和q它有关系
当且仅当是对于任意的这个输入串W
p在W上面它做迁移的时候
它能够转移到终态
当且仅当这个q也可以转移到终态
我们用这样的一种方法
就定义了这个q上面的它的一种关系
那这样定义关系
我们说它是一个等价关系
你要证明这个等价关系的话
就必须要证明等价关系满足的三个条件
第一个条件 就是我们证明它
这个关系具有自反性
那根据我们刚才构造的关系
自反性是显而易见的
第二个 对称性
那根据刚才的定义
这个对称性也是很容易满足的
关键是第三条 传递性
传递性 假设对于q上面任意的三个状态
p,q,r
p跟q它有关系R
q跟r它有关系R
那也就是说有下面这类关系
和这类关系是成立的
那我们要证明
p跟这个r是不是有关系R呢
那我们从这个定义 这个推导
马上得出这个q跟r
它的确是具有关系R的
那这样就说明
我们刚才定义的
状态集合q上面的关系r
的确是一个等价关系
那既然是状态集合上面一个等价关系
我们对于p跟q假如它具有关系R
也就是我们刚说的它是等价的
如果p和q它不具有关系R
我们就称p和q是不等价的
或者是称p和q是可区别的
那这个关系R是个等价关系
它对于我们DFA状态集上面的Q
就是一个划分了
那这样划分 我们就可以对状态集
原来是单个单个状态
那现在可以把它看作
一个块 一个块做个元素
构成了这一个状态由子集构成的集合
在这个划分里面
那每一个等价类或者每个块里面
它包含的状态它是等价的
那不同的块或者不同的等价在里面
它的状态它是不等价或者可区分的
那我们既然在状态集上面
定义了一个等价关系
已有一个划分
那我们就希望能够把等价的状态
就放在一起
这样我们的状态的集合表示
就应该是减少了
那我们的DFA的优化
实际上就是通过合并等价的状态
或者不可区分的状态
那既然我们的算法有了
那怎么样去实现这类算法
也就是说我们怎么样去构造刚才的
那个等价关系的那个算法
这就是我们下面要介绍的
状态集合上面划分的算法 填表法
填表法
它实际上是用递归的形式来定义的
那递归的形式 它是把每两个状态
看他们是不是等价进行标记
这个标记过程
我们既然是递归的话
我们有归纳基础
这个基础是对于终态和非终态
我们马上可以标记出来
因为终态可以通过空串转移到它自己
而非终态 它就是通过空串
它就不能转移到终态
这样我们终态和非终态
马上可以标记出来 它是可区分的
那接下来我们递归
假设p和q这两个状态已经标记出来
它们是可区分的
r和s是他们的前期状态
也就是说有一个输入字母a
它通过这个输入a
r可以转移到p
s可以转移到q
比如假定p和q是可区分的
那我们马上就可以得到这个r和s
它的前期状态也是可区分的
那我们通过这类算法
就可以把所有的它的可区分状态
都可以找出来
那下面我们看一个例子
这给了一个DFA
这个DFA有七个状态
其中5、6、7是终态
1是初态
那我们现在要用填表法
要把他们那个可区分的
和等价的状态都标出来
那怎么标记
因为我们刚才给的那个等价关系
它满足的自反性和对称性
那我们在进行状态对比的时候
我们就不需要把所有的状态都拿来对比
因为有对称性
我们只需要把他们有一半的状态
拿来对比就可以了
那我们怎么
对于在1、2、3、4、5、6、7这个状态
我们进行他们两两对比的时候
我们把状态1、2、3、4、5、6放在下面
而状态2、3、4、5、6、7放在这一列里面
那这样我们就可以把
任意一个状态和另一个状态
就他们进行对比了
我们把可区分的用个xx表示
那首先我们知道终态和非终态
根据刚才的归纳算法 它们是可区分的
5、6、7是终态
1、2、3、4是非终态
那我们就知道在这个里面
5、6、7和1、2、3、4这类状态
它们都是分别可区分的
也就是这里状态1和状态5是可区分的
状态2和状态5是可区分的
状态3和状态5可区分
状态4和状态5也是可区分的
状态1和状态6也是可区分的等等
我们就把终态和非终态分别都标出来了
首先我们看看状态1和状态3
这是状态1和状态3
那我们看一个路径
你比如说我们给一个输入字母a
输入字母a
状态1通过a转移到6
是终态
而3通过a是转移到1 非终态
那我们就找到一个路径
一个是转移到终态
一个转移到非终态
所以状态1和状态3是可区分的
我们再看看状态1和状态4
输入字母a
1通过a这个路径到达终态
4通过a 你看到了4 是非终态
因此终态1和终态4也是可区分的
同样我们可验证状态2 状态3
也是可区分的
状态2 状态4
这2和4 它们也是可区分的
还有5和6是可区分的
5和7也是可区分的
下面我们再看看状态3和状态4
状态3 状态4
我们不能像刚才那样直接找一个路径
但是我们可以递归的方式
我们看找数字字母a
状态3通过字母a到的状态1
状态4通过字母a到达状态4
也就是说状态3 状态4
是状态1和4的它的前期状态
就是通过输入a到达状态1和状态4
根据我们刚才递归的算法
那我们知道状态1和状态4是可区分的
因此状态3和状态4根据刚才的归纳
他们也是可区分的
这样 我们通过这次方法
就要把这些可区分的状态都标记出来了
那剩下的还有状态1 状态2
状态6和状态7
这两的状态 大家可以检验了
它对所有的输入串
它们实际上就标不出来了
它是不可区分的
因此 我们找到了这个划分的结果
这个等价类1和2是一个等价类
3它等价类只包含了它一个状态
4也只包含一个状态
5也只包含一个状态
6、7这个等价类包含两个状态
那这样我们把这样一个状态集合 7个状态
实际上就划分为五个等价的
这个类和这个块
那我们刚才讲了对状态级上面
定义了一个等价关系
也介绍了填表法
那大家对这个填表法
它是不是一定是正确的
这个正确意味着什么呢
如果有两个状态
在我们刚才算法里面没标记
那是不是这两个状态一定是等价的
那我们要现在要证明这件事实
证明这件事实实际上我们可以用反证法
反证法如果说有两个状态 没标记
但是它们是不等价的
那不等价就肯定就有一个串
使一个状态到终态
另外一个状态到非终态
假设我们就是状态p经过w
它到的终态
而q经过w它到的非终态
我们下面要推出矛盾
推出矛盾
我们首先就说这个w
肯定是不能够为空串的
因为我们在刚才的填表法里面
终态和非终态是可区分的
因此 这个w它肯定不会是空串
下面我们假设w是等于a和x
我们一步步的把它要前面推进
a我们假设p经过a到达r
q经过a到达s
那根据我们刚才讲的填表法的归纳是因为它
因为p1和q做过区分的
那我们就推出了这个r和s
也是可区分的
因为p和q是没被标记的
那你这个x就得到了它长度比w少一个
它也不能为空串
它为空串的话
那这个r和s它不就被标记了嘛
这样x也不能空串
因为w它的长度是有限的
它要按这样的方法我们就证明了
我们的填表法是正确的
这节里面
我们介绍了状态集上面的
一个等价关系和等价关系的算法 填表法
那这个填表法 怎么样去应用到
一个DFA的优化
这是我们下节要介绍的内容
好 这节内容介绍完毕
谢谢大家
-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
-习题--作业
-期中考试