2.4  DFA construction, Subset construction, Simpleset DFA在线视频

各位同学大家好

这节课

我们继续学习

词法分析的内容

连接上一章的内容

我们知道

我们如果想把正规式

变成一个状态转换图的话

我们需要采取一种迂回的策略

也就是先把正规式

用NFA不确定的有限状态自动机来表示

进而把它转换成确定的有限状态自动机

再来化简

就可以得到

最精简的状态转换图了

上一节课我们学习了

如何把正规式

变成NFA不确定的有限状态自动机

那么在这节课里

我们就来讲

接下来的内容

也就是把NFA要如何转换成DFA呢？

以及这样的DFA

是不是一个最简的表示形式呢？

如何让我们的词法分析的编译程序

更加的精简有效呢？

这就是我们本节要讲的内容

首先我们看

我们的NFA转换成DFA的办法

实际上就是把NFA的不确定性

给它去掉的这样的一种策略

也就是说

我们构造完NFA之后

把它变成DFA用的一种方法

叫做子集构造法

简单的来说

就是在NFA当中

那些 ε 边 这是不确定的

那么我们把它去掉

如果从NFA的一个状态

可以跳转到好多个状态的话

我们把这些状态合并到一起

变成一个状态

也就是说在NFA里的好多个状态

在DFA里就是一个状态集合

它是它的一个子集

由此我们可以得到

子集构造法这个的定义

我们看整个的理论依据

我们是依据任何一个NFA都可以

得到一个确定的一个DFA这样的一个过程

那么整个转换的方式

就采用子集构造法

这样的一种方法

我们看一下整个过程

它的原理

也就是说当我们读入了

从 a1~an 这样的一个串以后

我如果NFA能到达的状态

是s1、s2、一直到sk

那么DFA到达的状态

就是以上这些状态的一个状态集合

比如说我们识别a 或b 的这样的一个闭包

再连接一个a 连接一个b 这样的一个正规式

那么对应的NFA就是从状态0开始

如果它识别a 可以回来

也可以跳转到下一个状态

那么在DFA 里

我就需要把这样的

同样的两条边合并成一条边

也就是说把这种不确定的跳转

让它变得确定了

把 0 和 1 这个状态合并到一起

产生一个新的状态

如果有 ε 边的话

那么通过 ε 能够跳转到的状态

就相当于

我通过不识别任何一个符号

都可以到达

那么这样的状态

也可以合并到一起

这就是它的基本的原理

我们通过一个实际的例子

来看一下

我们看这样的一个状态转换图

就是我们上节课学习的

a 或 b的闭包连接 a 连接 b

这样的一个状态转换图

它是一个NFA

那么怎么变成一个DFA呢？

这个过程就是从开始状态 0 开始

我们先求 ε 闭包

什么意思呢

就是说

从状态 0 开始

不通过任何字母表上的输入

不通过a 或者b 的输入

我就可以随意到达的状态

都合并到一起

所谓随意到达

就是通过 ε 转换能到达的

我们看以状态 0 为例

我们可以跳转到 1、 2 、4 、7

那么在DFA当中

这样的几个状态

就是一个新的状态

合并成一个新的状态

我们看这里就是

那么 0 1 2 4 7 给它称其为一个新的集合

一个新的状态 起一个名字叫做A

那么在DFA里

我们就产生了一个新的状态

这个状态就是我们的开始状态

由开始状态

我们要看

它对A和b分别跳转到哪里

我们要怎么看呢？

我们就要看我们的状态里的

任何一个状态

通过a和b跳转到哪里

把跳转到的状态

合并到一个集合

分别写到下面

我们首先看0 1 2 4 7

遇到a会怎么样

0 遇到a没有跳转

唯一有跳转的是 2 和 7

这两个状态

分别跳转到3号状态和8号状态

那么3号状态和8号状态

就是 A 这个状态

遇到小 a 的输出到达的状态

仅有3和8还不够

3和8号状态

凡是通过 ε 边

能跳转到的状态

也和它们都是在一起的

因此到达3号状态之后

还继续求 ε 闭包

那我们可以到达6号

回到1号 还有7号

因此 3 6 1 7 8

就是我们新的状态集合

因此我们可以看到

如果从状态A跳转到A的话

通过跳转

然后进而求闭包

我们就可以得到一个新的状态B

这个b就包含

我们看（状态）2 识别一个 a 的话 到达（状态）3

然后通过 ε 闭包到的（状态）6 1 2 4 7 以及 8

那么我们给这个状态集合

起一个新的名字叫做b

那么这个b我们就可以在

DFA当中

它的新的状态里出现进入

我们看状态遇到b会怎么样

状态A 是0 1 2 4 7

那么它遇到字母b的话

我们看只有4号状态会遇到字母b

那么遇到字母b会跳到5

状态5 进而求 ε 闭包

就是到了

6 7 1 2 4 这样的状态

我们看这样的状态集合在之前没有出现过

没有出现过就是一个新的状态集合

新的状态集合

我们给它起一个名字 就是 1 2 4 5 6 7

这样的状态 我们称其为C

那就A遇到b这个符号

会跳转到C这个状态

由此我们得到了三个新的状态

并且完成了状态 A

对字母表上

所有输入的这样一个跳转

进而我们需要做的

就是看状态 B 遇到 a 和 b 分别跳转到哪？

我们会发现

B 遇到 a 还是到 B 本身

然后 B 遇到 b 会到达一个新的状态

我们来看一下

状态 B 是这里 1 2 3 4 6 7 8

遇到字母b 有字母b 跳转的就是

状态4 以及状态8

状态4 遇到b 会到5

到5的话 那会跳转到 6 1 2 4 以及 7

那么状态8 遇到b 会跳转到状态9

很显然 这个集合

没有在之前任何一个集合当中出现过

它就是一个新的状态集合

我们起名为D

把D也写下来

可以用同样的方式

我们把状态C 对于a b

和状态D 对于a b 的跳转

给它补充完整

如果在这个过程当中

没有新的状态集合出现

那么到此为止

整个NFA转换成DFA的子集构造法就完成了

在这里需要注意的是

对于转换结束的DFA来说

它的开始状态

就是包含原有开始状态0 的状态A

接受状态是在这些集合当中

凡是包含了原有NFA的接受状态的状态集合

都是接受状态

原有的接受状态是状态9

而在这里面状态D包含了状态9

因此在转换之后的状态转换图里面

状态D就是一个接受状态

我们看根据刚才的整个的画法

我们就可以得到复杂的NFA对应的DFA

它就是这样的一种形式

那么我们以其中的一个状态为例

状态A遇到 a 到状态b

状态A遇到 b 到状态C

进而我们可以把其他的补全

而状态D 就是一个双圈的形式

它是一个接受状态

我们来看一下

同样的这样的一个正规式

我们可以给它表示成

这样复杂的一个结构

也可以表示成我们化简的

我们得到的 DFA的形式

那么还有这样的一种

相对简单的NFA的形式

其实除此之外

还有另一种更简单的方式

也就是粉色的图的表示

这个粉色的图

实际上

我们看

它没有对一个状态

好多个输出 同样的输出边

它也是一个DFA

它也是识别这样的语言的DFA

不同在于它有三个状态

而我们转换得到它有4个状态

因此我们为了提高编译器的效率

我们希望得到的是

最左侧的粉色的

这样的一个最简的DFA

因此接下来

我们来学习

整个过程的最后一项内容

也就是DFA的化简

DFA的化简

整个过程

就是我们先通过构造NFA

然后子集构造法得到DFA

最后再来判断DFA是不是一个最简的

那么如何判断

一个确定的有限状态自动机

是不是一个最简的形式呢？

我们来看

是通过状态的可区分性来判断的

也就是说一个DFA拿过来

它究竟是不是一个最简的形式

我们要看的就是

这里面是不是有两个或者两个以上的状态

起着同样的作用

担负着同样的功能

也就是说如果很多状态

它们识别同样的串 跳转到的 目的状态是相同的话

那么这样的状态

就可以合并到一起

这就是我们化简的一个基本的思想

也就是通过划分可区别状态

和不可区别状态来区分

以我们刚才NFA转DFA

得到的这么一个转换图为例

我们来看

A和b状态

A遇到a 到b, 遇到b 到C

然后b 遇到a 也到b, 遇到b 到D了

也就是说 这里面的A和b

尽管遇到a 都到了b

但是遇到b到了不同的地方

它们两个的作用就是不同的

既然不同就是可区别、可区分

功能不同

作用不同

就不能合并到一起

而对于这里面

我们再看A和C的状态

A 和C 遇到a 都到同样的状态B

遇到b 都到同样的状态C

也就是 不管是从它俩 A或者C 哪个状态开始

对于同样的输入

得到的结果都是一样的

它俩的职责是相同的

因此

我们就可以把这样的状态

合并到一起

因此我们这里面

化简的基本的想法就是

找那些不可区别的、区分不开的、功能相同的状态

让它们合并到一起

也就是说 根据状态是不是可以区分

我们来对它进行化简

整个化简的第1步

也是很关键的一步

我们需要先考察一下

原有的状态转换图 DFA

考察什么呢

看它是不是一个完全转换的函数

意思就是说

对于这里面的每一个状态

它是不是有所有的输出

比如说我们先看左侧的

橙色的

这样的一个图

对于每一个状态A 和B 的输出边

我们看

B也有a 和 b， D也有a 和b 的输出

都是完全的

那这样的图就叫一个完全的转换图

而对于右面的这个图

如果我们忽略粉色的部分的话

我们看

C只有a 的转换, 没有b 的转换

而D只有a 的转换, 也没有b e的转换

这种情况下

我们为了能够考察每一个状态的作用

它对每一个输出的它的方向

因此我们需要补入一个状态

这个状态E

我们就是补入的状态

称其为死状态

它的作用就是

把其他的状态

所不具备的那条输出边 都指向它

它自己也要是有完全的输出

也就是遇到a 和b 都回到状态E

为什么管它叫死状态呢

从这里可以看出的是

状态E 只有流入没有流出

也就是说

它对应字母表上的输入

它不会再跳转到其他地方

如果有某个状态跳转到它

那就说明错了

这也表示我们加入这个状态

不会影响原有的DFA的串的识别

原有的C和D就不会再识别b 了

在这里 如果识别b 也会报告错误

也就是说

不改变原有有限状态自动机它的识别结果

那么在这里

我们只是把它没有的那条边

给它补上而已

接下来我们看整个化简的过程

首先通过整个图里

按照可接受状态和不可接受状态

把整个的状态划分成两个集合

就好像一个屋子里有男生有女生

那么通过性别先分成两个集合

这里就是我们看接受状态这里只有D

D自己一个集合

A, B, C都是非接受状态

划分成一个集合

进而我们在初始的划分的基础上

再看一看哪些是和别人不同的

也就是有点类似树形结构一样

在初始划分的基础上

一点一点再细分下去

直到不能再分为止

不能再分那个集合里面剩的状态

就应该合并到一起

我们看我们怎么来考察呢？

我们就看

我们在一个集合里的这样的几个状态

遇到字母表上输入

是不是跳转到同样的地方去

我们看A, B, C遇到a 都到b 都到b状态

也就是说

用字母表上的A是没法区分它们三个的

但是不要着急

它们不能马上合并

因为我们还没考查b

我们看 它们对b的输出的话

A和C遇到b 都到C

而B遇到b 到了状态D

如果看成目前初始状态

是两个阵营的话

那么这个状态B遇到b就跳到了

其他的阵营去了

因此在这里面

我要把A B C里面的b

和别人不同的这个b

给它拿出来

在这个基础上

我们就得到了一个新的集合的划分

也就是A C是一个集合

B和D是分别的两个集合

进而 我们还需要进一步考察A和C

我们看A和C

遇到a跳转到的地方一样

遇到b调转到的地方也相同

因此我们说

它们的功能是相同的

需要合并

那么合并之后

我们看

把这里面的

A和C之间的这条边给它省略掉

自身带有的这样的一个跳转给它保留

我们就可以得到

最简的DFA这样的形式

以上就是本节课讲的内容

谢谢大家