NFA与DFA的等价性(下)在线视频

同学们 在上一节讨论当中

我们发现NFA的确定化

它的基本思路就是

构造这样的一个相应的DFA

这个DFA的每一个状态

对应于这个NFA的一组状态

也就是说

在读入字符串a1 a2...an之后

等价的DFA处于这样的一个状态

这个状态是NFA的状态子集T

T是NFA的初态沿着某个标记为

a1 a2...an的路径

可能到达的那些状态的集合

这个方法就是我们说到的“子集法”

接下来我们用状态转化矩阵

来描述NFA确定化的过程

首先 构造一张转换表

第一列 记为状态子集I

对于不同的输入符号a

在表当中单设一列Ia

第二步 表的首行首列置为

初态s0的ε闭包

第三步 根据首行首列的I

为每一个a求得它的Ia

并且记入对应的Ia列当中去

如果Ia不同于第一列

已经存在的所有状态的子集I

那么则将其顺序的列入到

空行当中的第一列

重复第三步

直到每一个状态集合I

以及a均已经求得了Ia

并且没有新的状态子集 Ia

加入到第一列为止

第五步 我们就可以重新的命名

第一列当中的每一个状态子集

从而形成新的状态转换矩阵

这样的话我们就得到了

与NFA等价的DFA

接下来我们来看一下

怎样将这个NFA转换成对应的DFA

首先我们构造状态转换表

输入有a和b

也就是说除了状态I之外

还需要计算Ia和Ib

确定了首行首列是

ε_CLOSURE(s0)

得到的结果是{x,1,2}

接下来就来计算Ia和Ib

并且将其更新到

第二行和第三行的首列

重复第三步

直到没有新的状态加入到首列为止

接下来就是对每一个状态集

进行重新的命名

这样的话我们就得到了

新的状态转换矩阵

需要注意的是

包含NFA初态的集合

对应于DFA的初态

包含原来NFA终态的集合

对应于等价的DFA的终态

根据新的状态转换矩阵

我们也可以绘制

等价的DFA的状态转化图

理论上有一个非常重要的结论是

每一个正规语言都可以

由一个状态数最少的DFA来识别

所谓的最小化的有限自动机

指的是它没有多余的状态

并且它的状态当中没有两个状态

是相互等价的

值得注意的是

在同构意义下

最小态的DFA是唯一的

因状态名不同的

这种同构情况除外

那么接下来我们来看一下

有穷状态自动机的多余状态指的是什么

从自动机的开始状态出发

任何输入串都不能够到达的状态

就是多余状态

在我们这个例子当中

大家可以看到s4和s5

就是这样的多余状态

那么有限状态自动机当中

两个状态等价的原则是什么

首先 遵循兼容性

譬如说状态s和状态t

它们必须同时为可接收状态

或者是同时为不可接收状态

其次 满足传播性

对于所有的输入符号

状态s和t必须转换到等价的状态里去

我们来判断两个状态s1和s2是否等价

只需要找出一个字符串w

假设s1和s2是M当中的

两个不同的状态

如果从s1出发能够识别字符串W

而停于终态

而从s2出发也能识别W

也停止在终态

那么就说明s1和s2

这两个状态是等价的

否则的话说明

这两个状态是可以区别的

那么W就称为判别序列

大家再来看

在这个DFA当中

C和F同为终态

C和F读入a都可以到达C状态

读入b都可以到达E状态

因此C和F是等价

是不可区分的

E和D同为终态

读入a之后均到达F态

读入b之后均到达状态D

那么说明状态E和状态D也是等价的

是不可区分的

而A和B是可区分的

这是因为A和B可以由输入字符

a来区别

对于输入a之后

A走到了接受状态C

而B则走到了非接受状态A

所以说A和B是可区分的

DFA最小化的算法核心

就是把DFA的状态分成

一些不相干的子集

使得任何的不同两个子集它的状态

是可区分的

而同一个子集当中的任何两个状态

都是等价的

我们来看一下DFA它的化简过程

第一步

首先将DFA的状态集按照终态

和非终态分为两个子集

形成初始的划分H

第二步 对于每一个子集G

进行下面的变换

把G划分成新的子集

使得G当中的两个状态s1和s2

同属于同一个子集

当且仅当任何的输入a

状态s1和s2它的后继状态

都属于同一子集式

那么用G划分出的

所有的子集来代替G

形成了新的划分Hnew

如果新的划分就是初始划分的话

那么去执行第四步

否则的话就用新的划分

来代替初始划分

去重复执行第二步

第四步 在我们划分结束之后

一个子集只对应一个状态

所以说我们会选出代表状态

删除掉其它一切的等价状态

并将对应的弧射向这个代表的状态

接下来我们对刚才NFA

确定化之后的这个DFA进行化简

首先根据终态和非终态

我们获得了初始划分

非终态集合1 ={S,A,B}

终态集合2={C,D,E,F}

首先我们来考察一下非终态集合1

从S射出a弧

射出b弧

从A状态射出b弧

从B状态射出a弧

去到的状态都在集合1当中

但是从A状态射出a弧

从B状态射出b弧

去到的状态落在了集合2当中

那么因此我们可以

把这个集合划分成三个子集

{S}{A}和{B}

接下来我们再来考察一下终态集合{C,D,E,F}

从这些状态射出a弧

去到的状态留在了集合2当中

射出b弧也在集合2当中

所以我们说{C,D,E,F}

是不可区分的

它们是等价的状态

我们不需要再做划分了

这就是划分之后最终的结果

将DFA的状态集合分作四个子集

S A B

还有就是C D E F作为的一个集合

那么接下来我们对它进行

重新的命名

其实也就选出了

它的一些代表的状态

S是初态

C是终态

于是我们就得到了状态转换矩阵

以及化简之后的DFA

它的状态转换图

在这一节当中

我们讨论的是

NFA与DFA的等价性

NFA它的优点是方便构建

DFA则在编程当中更容易实现

因此 我们又探讨了NFA

转化成DFA的方法

以及DFA的最小化的方法

这节课就到这里

谢谢大家