用状态子集构造法构造（a|b)*(aa|b...

来源：蜘蛛抓取(WebSpider) 时间：2011-10-07 03:58 标签： 子集构造
利用子集构造法实现NFA到DFA的转-1
利用子集法构造 DFA 指导老师 学号 赵智超 ...实验实现了 NFA 到 DFA 的转 换。
今日推荐 ...淘宝提升转化率秘诀 淘宝刷信誉互刷注意事项 淘宝客...
(一)NFA?DFA 一、实验目的 学会编程实现子集构造法 二、实验任务 存储 NFA 与 DFA,编程实现子集构造法将 NFA 转换成 DFA 三、实验内容 (1)确定 NFA 与 ...
(0|1)*101 首先构造 NFA: 0 X 1 ε A B 1 NFA 化为 DFA: 状态转换...首先构造 NFA 为 0 εε 1 0 ε 0 0 ε Y X 0 1 3 2 用子集法...
第4 章 词法分析 1.构造下列正规式相应的DFA. (...答案: 1) 根据题中映射,得如下 NFA 转换矩阵: ...
a a 图 2-2 习题 2.3 的 NFA M X 用子集法构造状态转换矩阵,如表 2...的状态转换矩阵 { 3 ,4 ,Y } 图 2-20 所对应的 DFA 如图 2-21 所示...
(由 NFA 构造 DFA 得到这一答案) : 二、 正则...中标明它对应的原 , DFA 状态的子集 状态的子集...) 最终答案: 最终答案:34 以下文法定义了二进制...
练习2. 词法分析 1. 利用子集构造法把以下 NFA 转换成 DFA。 0 0 z x 0 1 0 y 0 2.利用子集构造法把以下 NFA 转换成 DFA。 1 v 0 1 0 0 0...
理解和掌握子集法的相关知识和应用,编程 实现对输入 NFA 转换成 DFA 输出的...程序总框图如图 1 所示: NFA 图结构 状态转换表 机构 总控模块 图操作 初始...
实验一:利用子集法构造DFA 实验二:THOMPSON 算法的实现实验三:词法分析与语法分析...NFA 让 实验实现了 NFA 到 DFA 的转换。 10 实验二: 实验二:THOMPSON 算法...
法分析题 - 2 - 1、构造下面正规式相应的 DFA ...转化为 NFA,再将 NFA 确定化,最小化) 2、构造...DFA 为:开始状态为 0 ,终态集为{3} ,状态集为...3162人阅读
编译原理（14）
整体的步骤是三步：&
一，先把正规式转换为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.没有多余状态(死状态)
除多余状态&
什么是多余状态？&
从这个状态没有通路到达终态；S1&
从开始状态出发，任何输入串也不能到达的那个状态。S2&
如何消除多余状态？&
2. 没有两个状态是互相等价（不可区别）&
两个状态s和t等价的条件：&
兼容性（一致性）条件——同是终态或同是非终态&
传播性（蔓延性）条件——对于所有输入符号，状态s和状态t必须转换到等价的状态里。。
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来代替。无所谓的最小化的ＤＦＡ如图，：&
参考知识库
* 以上用户言论只代表其个人观点，不代表CSDN网站的观点或立场
访问：193092次
积分：7545
积分：7545
排名：第2275名
原创：553篇
转载：116篇
评论：19条
文章：23篇
阅读：17598
文章：16篇
阅读：5929
文章：54篇
阅读：11261
文章：38篇
阅读：14589
(1)(1)(2)(8)(22)(7)(40)(43)(89)(118)(48)(2)(25)(55)(60)(66)(83)(12)郑州大学编译原理试卷及答案(往年试题整合)_百度文库
两大类热门资源免费畅读
续费一年阅读会员，立省24元！
郑州大学编译原理试卷及答案(往年试题整合)
上传于|0|0|暂无简介
阅读已结束，如果下载本文需要使用1下载券
想免费下载本文？
定制HR最喜欢的简历
下载文档到电脑，查找使用更方便
还剩7页未读，继续阅读
定制HR最喜欢的简历
你可能喜欢编译原理习题解答_百度文库
两大类热门资源免费畅读
续费一年阅读会员，立省24元！
编译原理习题解答
上传于|0|0|暂无简介
阅读已结束，如果下载本文需要使用0下载券
想免费下载更多文档？
定制HR最喜欢的简历
下载文档到电脑，查找使用更方便
还剩27页未读，继续阅读
定制HR最喜欢的简历
你可能喜欢

我要回帖

更多关于 子集构造 的文章

 

随机推荐