构造正规式最小DFA方法_第1页
构造正规式最小DFA方法_第2页
构造正规式最小DFA方法_第3页
构造正规式最小DFA方法_第4页
全文预览已结束

下载本文档

版权说明：本文档由用户提供并上传，收益归属内容提供方，若内容存在侵权，请进行举报或认领

文档简介

今天早上去图书馆，去看编译原理，想把这部分搞清楚，看着龙书+国产的某一本不知什么的习题与解析，猜过程。猜原理。终于是看懂了。整体的步骤是三步：一，先把正规式转换为NFA（非确定有穷自动机）,二，在把NFA通过“子集构造法”转化为DFA，三，在把DFA通过“分割法”进行最小化。一步很简单，就是反复运用下图的规则，图1这样就能转换到NFA了。给出一个例题，来自Google book。本文主要根据这个例题来讲，图2二.子集构造法。同样的例题，把转换好的NFA确定化，图3这个表是从NFA到DFA的时候必须要用到的。第一列第一行I的意思是从NFA的起始节点经过任意个所能到达的结点集合。Ia表示从该集合开始经过一个a所能到达的集合，经过一个a的意思是可以略过前后的。同样Ib也就是经过一个b，可以略过前后任意个。至于第二行以及后面的I是怎么确定的。我参考了一些题目才明白，原来就是看上面的Ia和Ib哪个还没出现在I列，就拿下来进行运算，该列对应的Ia和Ib就是前面我说的那样推导。如果还不太明白，看图就是了。你会发现I中的几个项目都在Ia和Ib中出现了。而且是完全出现这步做完以后，为了画出最后的DFA，那么肯定得标出一些号来，比如1.2.3.。或者A。 B。c，我一般标的方法是先把I列全部标上1.2.3.递增。然后看1表示的集合和Ia和Ib中的哪个集合一样，就把那个集合也表示为1.继续向下做。最后会得到这样一个表格。图4至此，就可以表示出DFA了。就对照上面那个表，从0节点开始经过a到1.经过b到2，就这样画就行了。最后的DFA如下图，图5双圈的表示终态，这个是怎么来的呢。去看看图4，会发现有些项之前有双圈标志，这个是因为在NFA图2中，9为终态，所以所有包含9的集合都被认为是终态集，改成1.2.3.。方便画节点后就需要把这些点作为终态了。三.最小化，分割法。FA的最小化就是寻求最小状态DFA最小状态DFA的含义:1.没有多余状态(死状态)2. 没有两个状态是互相等价（不可区别）两个状态s和t等价的条件：兼容性（一致性）条件同是终态或同是非终态传播性（蔓延性）条件从s出发读入某个a和从t出发经过某个a并且经过某个b到达的状态等价。就是相同。DFA的最小化例子，第一步都是固定的。分成终态和非终态将的状态分为两个子集一个由终态k1=，组成，一个由非终态k2=，组成，考察，是否可分因为经过a到达C属于k1.而S经过a到达A属于k2.B经过a到达A属于k2，所以K2继续划分为S，B,A,考察，是否可再分：B经过b到达D属于k1.S经过b到达B属于k2，所以S，B可以划分。划分为S,B考察，是否可再分：因为，经过a和b到达的状态都属于，=k1所以相同，所以不可再分：，以来代替则，因为CDEF相同，你也可以用C来代替。无所
人人文库> 全部分类> 行业资料 > 管理策划

温馨提示

  • 1. 本站所有资源如无特殊说明，都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等，如果需要附件，请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸，网页内容里面会有图纸预览，若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对用户上传分享的文档内容本身不做任何修改或编辑，并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容，请与我们联系，我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

最新文档

评论

0/150

提交评论