当前课程知识点:软件理论基础 >  第六章 正则语言的性质与DFA优化 >  6.5 DFA的优化 1 >  Video

返回《软件理论基础》慕课在线视频课程列表

Video在线视频

Video

下一节:Video

返回《软件理论基础》慕课在线视频列表

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

-习题--作业

第六章 正则语言的性质与DFA优化

-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

-习题--作业

第八章 CFG的应用与文法的二义性

-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

-习题--作业

第十章 下推自动机与CFG化简规范

-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

-习题--作业

第十二章 Turing机

-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

-习题--作业

期中考试

-期中考试

Video笔记与讨论

也许你还感兴趣的课程:

© 柠檬大学-慕课导航 课程版权归原始院校所有,
本网站仅通过互联网进行慕课课程索引,不提供在线课程学习和视频,请同学们点击报名到课程提供网站进行学习。