豆丁微信公众号
君，已阅读到文档的结尾了呢~~
扫扫二维码，随身浏览文档
手机或平板扫扫即可继续访问
编译原理及其习题解答(武汉大学出版社)课件chap3
举报该文档为侵权文档。
举报该文档含有违规或不良信息。
反馈该文档无法正常浏览。
举报该文档为重复文档。
推荐理由：
将文档分享至：
分享完整地址
文档地址：
粘贴到BBS或博客
flash地址：
支持嵌入FLASH地址的网站使用
html代码：
&embed src='http://www.docin.com/DocinViewer-4.swf' width='100%' height='600' type=application/x-shockwave-flash ALLOWFULLSCREEN='true' ALLOWSCRIPTACCESS='always'&&/embed&
450px*300px480px*400px650px*490px
支持嵌入HTML代码的网站使用
您的内容已经提交成功
您所提交的内容需要审核后才能发布，请您等待！
3秒自动关闭窗口 上传我的文档
 下载
 收藏
粉丝量：649
该文档贡献者很忙，什么也没留下。
 下载此文档
正在努力加载中...
编译原理词法分析-正则表达式与有穷状态自动机
下载积分：1000
内容提示：编译原理词法分析-正则表达式与有穷状态自动机
文档格式：PPT|
浏览次数：144|
上传日期： 14:39:30|
文档星级：
全文阅读已结束，如果下载本文需要使用
 1000 积分
下载此文档
该用户还上传了这些文档
编译原理词法分析-正则表达式与有穷状态自动机
关注微信公众号2151人阅读
编译原理（4）
非确定有限自动机的定义：
非确定有限自动机是一NFA是一个五元组（∑，
S, S0, f, Z）,其中
∑是一个有穷字母表，它的每个元素称为一个输入字符
S是状态集合
S0是初始状态的集合，是非确定有限自动机的初始状态集合
f：是一个从S
∪{e}）到S的子集的映射，S×(?∪{e})→2s
是一个终止状态集合。又称为接收状态集合
DFA与NFA的区别：
一个状态的不同输出便可以标有相同的符号
允许有多个开始状态
允许有空边
NFA所能接受的串定义与DFA保持一致。
e&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&
1&&&&&&&&&&&&&&&&&&&&&& a
很明显，在如果我们使用NFA来表述问题，因为我们引入了空边，并且能够有多个开始状态，这使得我们在描述问题时非常方便，可这又引入了另外的问题，那就是实现的问题。因为对于一个状态，之前我们在学习DFA的时候可以很方便的实现是因为，一个状态输入一个输入字符，可以确定的进入另一个状态，而NFA不然，对于一个状态，你进入一个输入字符，你无法确定下一个状态是什么，而且初始状态有多个，我们对问题的初始状态应该赋值为哪一个，我们都没法确定。因此，NFA在表述问题方面，很方便，但在实现方面远远没有DFA便捷。
自动机等价问题：
对于任何一个非确定有限自动机，存在一个确定自动机与之对应，两者接收的符号串一致，系两者等价。
NFA到DFA的转换
M状态集和的自己，定义I的空闭包e
-CLOSURE(I)为：
若q属于I，则q属于这个空闭包
若q属于I，那么从q出发经任意条空弧而能到达的任何状态q‘都属于这个空闭包。
状态集I的a转换：若I
= {S1, S2, S3, ……, Sm}是NFA的状态集的一个自己，a属于字母表∑，则定义：
-CLOSURE(J)
其中J为f(S1,
a) ∪f(S2, a)∪f(S3,
a)∪……∪f(sm,
也就是从I集合S1, S2, S3,
……, Sm接收一个a所能达到的状态总和为J
已知A：NFA，构造A‘：DFA
令A'的初始状态为
-CLOSURE({S1, S2, S3,
……, Sk})，其中S1,……，Sk是A的全部初始状态
若I={S1, S2, S3,
……, Sm}是A'的一个状态，a属于字母表∑，则定义f‘（I,
a） = Ia，将Ia加入S’，重复该过程，直到S‘不产生新的状态
=& {S1, S2, S3, ……, Sn}是A’的一个状态，且存在一个Si是A的终止状态，则令I'为A‘的终止状态。
根据构造算法：
确定DFA的初始状态A'
在上图中，只有一个初始状态1，（箭头指向为初始状态）
计算初始状态集合的空闭包，因为初始状态集合只有一个元素，1，
DFA的初始状态也就是NFA初始状态集合的空闭包。
空闭包的定义为包含当前元素q，也包括从当前元素到达的元素。也就是说对应的DFA中的初始状态为{1， 2}（其中2为1经过空边所到的状态）
2，也就是说第一个DFA的状态我们已经确定，I
= {1， 2}，又因为上图中只有两个输入符号{a,
b}（空不算）（字母表中的所有元素）下面分别计算Ia和Ib就能确定从DFA初始状态所能到达的两个状态了。
J = f(S1, a)
∪f(S2, a)∪f(S3,
a)∪……∪f(sm,
a)。也就是I中所有状态这里为{1，
2}中的1状态和2状态，经过字符a所能到达的状态的并集。这样的话J就能确定为J
之后确定{4， 5}的空闭包（也就是Ia），就确定了一个DFA中的状态。
{4， 5}的空闭包首先包括4，
5，然后包括从4， 5出发经过空边到达的状态从4经过空边到达7，5经过空边到达6，7没有空边的输出边，6经过输出空边到2状态。2没有输出空边。也就是我们已经确定了Ia
= {4， 5，7，&
}，这便是DFA的另外一个状态。
同理：可确定Ib
Ib = {3, 8};
因为字母表只有两个字符，所以最多确定两个状态集合。也就是说现在DFA中的状态我们已经确定了三个。
{4， 5， 6，
7， 8}， {3，
接下来依次类推即可。
画出DFA时只需要做出对应即可。
另一种消除空边的方式：
0&&&&&&&&&&&&&&&&&&&
空&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&1&&&&&&&&&&
a&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&2
0&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&1&&&&&&&&&&&&&&&&&&&&&
a&&&&&&&&&&&&&&&&&&&&
空边出现环路的时候，就把这几个状态合为一个。
自动机的最小化
等价状态：
设DFA的两个状态S1，S2，如果对任意输入的符号串x，从S1和S2出发，总是同时到达接收状态或者拒绝状态中，则称两者等价。
无关状态：
&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&2
&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&0
&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&1
0&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&2
两个1都是无关状态
自动机的最小化：
最小自动机：
如果DFA M中没有无关状态，也没有等价状态，则称M为最小自动机
结论：任意一个DFA都可以化为最小自动机，并且两者接收相同的符号串。
自动机的化简
状态分离法：
终止状态为1组，非终止状态为1组
对每一组进行分离，若每一组中的元素映射到不同的组，则表示他们不等价，就可以划分出来
重复2，直到没有新组产生，此时每组中的状态都为等价状态。
屏幕剪辑的捕获时间:
自动机的最简化，是针对DFA的，不要弄混乱了
显然，第一步是把组分开分为两组{1，2，
3， 5}， {4，
6， 7， 8}
分离第一组{1， 2，
1经过a到自身，经过b自身
2经过a没有了，经过b到另外一组（{4，
6， 7， 8}）
经过a到自身，经过b到自身
5经过a到没有了，经过b到另外一组（{4，
6， 7， 8}）
这样的话也就分离开了，1和3一组，2和5一组也就是
3， 5}经过这一步分离为{1，
3}和{2， 5}
分离第二组{4，
6， 7， 8}
4经过a到{2，
5}，经过b到自身
6经过a到{2，
经过b到自身
7经过a到{2，
经过b到自身
8经过a到{2，
经过b到自身
因为四个状态对于任意的输入符号总是同时到达一样的状态，因此我们现在说这个{4，6，&
7， 8}暂时不
现在一共有3组，{1，
3}， {2， 5}，
{4， 6， 7，
分离第一组{1，
1经过a到{2，
经过b到自身
3经过a到{2，
经过b到自身
因为第一组中所有状态对于字母表中任意输入符号串总是到达一样的状态，因此他们等价，不划分
分离第二组{2，
第二组不用划分
分离第三组{4，
6， 7， 8}
第三组不用划分，已经等价。
因为这一次没有新组产生，则我们可以得出结论，此时每一组中的状态都为等价状态。相应的画出DFG即可。
&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&
访问：104556次
积分：2499
排名：第17300名
原创：146篇
评论：12条
(1)(3)(5)(2)(9)(3)(7)(3)(4)(4)(2)(31)(70)(3)(2)您所在位置： &
&nbsp&&nbsp&nbsp&&nbsp
编译原理第三章自动机基础_习题讲义.ppt 7页
本文档一共被下载：
次 ,您可全文免费在线阅读后下载本文档。
下载提示
1.本站不保证该用户上传的文档完整性，不预览、不比对内容而直接下载产生的反悔问题本站不予受理。
2.该文档所得收入(下载+内容+预览三)归上传者、原创者。
3.登录后可充值，立即自动返金币，充值渠道很便利
你可能关注的文档：
··········
··········
习题解答： 第3章
习题解答： 第3章
习题解答： 【习题3.5】 把下述 NFA 转换为 DFA: 第3章
习题解答4： 第3章
习题解答： 第3章
习题解答： 谢谢收看！ * * 【习题3.2】P64_7(1) 构造确定自动机 DFA: ⑴ e=1(0|1)*101
① + 0 1 1 - ② 1 ③ ④ ⑤ 0 1 ⑵ e=(a|b)*(aa|bb)(a|b)* ① + a b - ② ③ ④ a a b b a b A{1} b
变换表 DFA
状态图 A B C D E + - - a a a b b b b a b a E{1,3,4} D{1,2,4} E{1,3,4} D{1,2,4} E{1,3,4} B{1,2} C{1,3} D{1,2,4} C{1,3} B{1,2} D{1,2,4} E{1,3,4} C{1,3} B{1,2} - - 确
化 【习题】构造一个 DFA,它接收∑={0,1}上所有满足如下条件的字符串： 每一个1都有0直接跟在右边。 【解】 ① + 0 1 - ② 0 ③ 1 - 0 ① + - ② 0 1 0 或 【习题3.4】给定正规语言，构造有限自动机：
A= { an,ban |n≥0 } 【解】 ① + - ② b a a - ① + - ② b a a - ① ② ③ a b a b + - FA1: ① ② ③ a b a b + - FA2: a b + - DFA2: A B A{1} b a + B{2,3} B{2,3} B{2,3} - a a b + - DFA1: A B C b C{2,3} B{2} C{2,3} B{2} C{2,3} B{2} - A{1} b a + 【习题3.5】 消除 ?NFA 的 ?边： ② ③ ① + a - ? ? a b ③ ④ - ① + ② b a ? b ? a FA3: FA4: 【算法】 ⑶
逆序删? 边,并补充新边。 ⑴
?闭路合而为一； ⑵
标记隐含初态和终态； ② ① + - a b a DFA1 ③ ④ - ① + ② b a b ? a a b ③ - ① + ② a a b b a DFA2 无用状态 【习题3.8】已知符号串集合，构造正规式、自动机和正规文法： A={ ?,an,ban|n≥1 } 【解】
正规式: e=?|a+|ba+ 或 e=a*|ba+
自动机 DFA:
a a + - 1 2 b - 3 a
S A B S -& aA|bB|? A -& aA|? B -& aA 【习题3.9】已知自动机DFA: ② a b ③ ⑤ b c c ① ④ b b - + - ⑴ 扩展DFA(加入结束标记#),构造压缩变换表； ⑵ 根据实现算法，写出识别 abbc#的过程。 ⑵ 输入串 abbc# 识别过程： 【解】 ⑴ 扩展DFA: 压缩变换表 ④ ⑤ ③ ② ① ? no ④ b ② a ? no ④ b 索引表 ? no ⑤ c ③ b ? no ⑤ c ③ b ? no ok # 1 备注 变换 剩余 ch state ② a b ③ ⑤ b c c ① ④ b b + - - ≮ - ≮ 2 bbc# a 接受 ok # 5 # c 3 c# b 3 bc# b 5 3 3 2
正在加载中，请稍后...编译原理（14）
1，属性文法中文法符号的两种属性分别成为 继承属性 和 综合属性
2，符号表的每一项是由 名字栏 + 地址分配 两个栏目 组成
3，一个大题：
有穷自动机M接受字母表＝{0,1}上所有满足下述条件的串：每个1都有0直接跟在右边。构造一个最小的DFA M及和M等价的正规式。
等价的正规式真的写的好，还要注意0是可以无限循环的，这里规则很多，估计要考虑很多情况才能完全掌握 - -
访问：584053次
积分：12367
排名：第1379名
原创：646篇
转载：180篇
评论：50条
欢迎大家访问哈~欢迎提出指导意见
文章：23篇
阅读：46903
文章：16篇
阅读：13609
文章：54篇
阅读：22074
文章：38篇
阅读：42081
(16)(2)(2)(29)(19)(21)(14)(7)(10)(6)(22)(1)(2)(8)(22)(7)(40)(43)(89)(118)(48)(2)(24)(54)(59)(66)(83)(12)