正规式—>最小DFA详解

正规式—>最小DFA详解整体分三步:把正规式转换为NFA(非确定有穷自动机)将NFA通过“子集构造法”转换为DFA最后把DFA通过分割法进行最小化一、正规式转换为NFA反复运用图(1)转换规则,把正则表达式转换为有限自动机图(1)例如:图(2)二、子集构造法确定DFA将图(2)根据子集构造(详细方法见

大家好,欢迎来到IT知识分享网。

整体分三步:

  1. 把正规式转换为NFA(非确定有穷自动机)
  2. 将NFA通过“子集构造法”转换为DFA
  3. 最后把DFA通过分割法进行最小化

一、正规式转换为NFA

反复运用图(1)转换规则,把正则表达式转换为有限自动机

正规式—>最小DFA详解

                                               图(1)

 

例如:

正规式—>最小DFA详解

 

                                                                       图(2)

 

 二、子集构造法确定DFA

将图 (2)根据子集构造(详细方法见编译原理随笔)法转换为DFA,如图(3),

正规式—>最小DFA详解

 

                                                                               图(3)

  这个表是从NFA到DFA的时候必须要用到的。第一列第一行I的意思是从NFA的起始节点经过任意个ε所能到达的结点集合。

Ia表示从该集合中的每个结点开始经过一个a所能到达的集合,经过一个a的意思是可以略过前后的ε,同样Ib也就是经过一个b,

可以略过前后任意个ε。

  至于第二行以及后面的I是怎么确定的,可以根据上一行中Ia,Ib的值确定。第一行Ia{2,4,6,7,9},Ib{5,6,7,8,9,},故I的值可取{2,4,6,7,9},

{5,6,7,8,9,}。可以发现上面的Ia和Ib哪个还没出现在I列,就拿下来进行运算,该列对应的Ia和Ib的值可根据子集构造法推出。如果还不太明白,

仔细观察图(3)你会发现I中的几个值都在Ia和Ib中出现了,而且是完全出现。

  这步做完以后,为了画出最后的DFA,那么肯定得标出一些号来,比如1,2,3。或者A,B,C,我一般标的方法是先把I列全部标上 1,2,3 递增。

然后看1表示的集合和Ia和Ib中的哪个集合一样,就把那个集合也表示为1.继续向下做。最后会得到这样一个表格。如图(4),

正规式—>最小DFA详解

 

 

                                                                            图(4)

  至此,就可以表示出DFA了。就对照上面那个表,从0节点开始经过a到1经过b到2,就这样画就行了。最后的DFA如下图,见图(5),

正规式—>最小DFA详解

 

 

                                          图(5)

  双圈的表示终态,这个是怎么来的呢。去看看图4,会发现有些项之前有双圈标志,这个是因为在NFA图2中,9为终态,

所以所有包含9的集合都被认为是终态集,改成1.2.3.。方便画节点后就需要把这些点作为终态了。

三、最小化、分割

最小化就是寻求最小状态DFA 

最小状态DFA的含义:
1、没有多余状态(死状态)

正规式—>最小DFA详解

 

 

 

除多余状态

什么是多余状态?

从这个状态没有通路到达终态,即S1

从开始状态出发,任何输入串也不能到达的那个状态,即S2

如何消除多余状态?删除即可。

 

2、没有两个状态是互相等价(不可区别)

两个状态s和t等价的条件:

兼容性(一致性)条件——同是终态或同是非终态

传播性(蔓延性)条件——对于所有输入符号,状态s和状态t必须转换到等价的状态里。

假定s和t是M的两个不同状态,如果从状态s出发读出某个字w而终止于终态,同样,

从状态t出发读出某个字w而终止于终态,我们称s和t等价。

DFA的最小化—例子,第一步都是固定的。分成终态和非终态:

1.将M的状态分为两个子集一个由终态k1={C,D,E,F}组成,一个由非终态k2={S,A,B}组成。

2.考察{S,A,B}是否可分。

正规式—>最小DFA详解

 

因为A经过a到达C属于k1.而S经过a到达A属于k2。B经过a到达A属于k2,所以K2继续划分为{S,B},{A}。

3.考察{S,B}是否可再分:

B经过b到达D属于k1。S经过b到达B属于k2,所以S,B可以划分。划分为{S},{B}

4.考察{C,D,E,F}是否可再分:

因为C,D,E,F经过a和b到达的状态都属于{C,D,E,F}=k1所以相同,所以不可再分。

5.{C,D,E,F}以{D}来代替则,因为CDEF相同,你也可以用C来代替。无所谓的最小化的DFA如图:

正规式—>最小DFA详解

 

 注:本为为转载文章,本人略微修改,如果存在问题,请联系我删除。

 原文链接:https://www.cnblogs.com/cute/p/4021689.html

 

免责声明:本站所有文章内容,图片,视频等均是来源于用户投稿和互联网及文摘转载整编而成,不代表本站观点,不承担相关法律责任。其著作权各归其原作者或其出版社所有。如发现本站有涉嫌抄袭侵权/违法违规的内容,侵犯到您的权益,请在线联系站长,一经查实,本站将立刻删除。 本文来自网络,若有侵权,请联系删除,如若转载,请注明出处:https://yundeesoft.com/31565.html

(0)

相关推荐

发表回复

您的电子邮箱地址不会被公开。 必填项已用 * 标注

关注微信