构造正规式相应的DFA346
![构造正规式相应的DFA346_第1页](https://file6.zhuangpeitu.com/fileroot6/2023-3/1/c94f8221-043c-4c01-b21c-117b4fdeb3f7/c94f8221-043c-4c01-b21c-117b4fdeb3f71.gif)
![构造正规式相应的DFA346_第2页](/images/s.gif)
![构造正规式相应的DFA346_第3页](/images/s.gif)
《构造正规式相应的DFA346》由会员分享,可在线阅读,更多相关《构造正规式相应的DFA346(3页珍藏版)》请在装配图网上搜索。
1、构造正规式相应的 DFA 构造正规式相应的 DFA:1(0|1)*101 按照以下三步:(1)由正规表达式构造转换系统(NFA)(2)由转换系统(NFA)构造确定的有穷自动机 DFA(3)DFA 的最小化 答:(1)首先构造与正规式 1(01)*101 相应的 NFA,然后再将 NFA 确定化。为正规式构造 NFA 的方法为“语法制导”法,即依据正规式的语法构造来构造.首先将正规式 r=1(01)101 分解成 r=r1,r2r3,其中:r1=1,r2=(01),r3=101.对于 r1,有:对于 r2,有:对于 r3,有:因此,与正规式 r=r1r2r3 相对应的 NFA 如图所示为:展开为
2、:X A 1 A 0,1 A 0,1 X 1 B C Y 1 1 0 X B C Y 1 1 0 构造正规式相应的 DFA (2)将 NFA 转换成 DFA 采用子集法,即 DFA 的每个状态对应 NFA 的一个状态集合.构造 DFA 的状态集 C,假定 C=T0,T1,Ti,集中T0=closure(X),对于任何 aTi=-closure(Move(Ti,a))。Ti Ti0 Ti1 A0 T0 A1,A2,A3=T1 A1,A2,A3 T1 A2,A3=T2 A2,A4,A3=T3 A2,A3 T2 A2,A3=T2 A2,A4,A3=T3 A2,A3,A4 T3 A2,A5,A3=T4
3、 A2,A4,A3=T3 A2,A3,A5 T4 A2,A3=T2 A2,A4,A6,A3=T6 A2,A3,A4,A6 T5 A2,A5,A3=T4 A2,A4,A3=T3 DFA 的状态转换图 (3)化简 DFA:分割法,把 DFA 的状态集分成一些不想交的子集,使得不同的两子集的状态是可区别的,同一子集的状态是等价的。首先,将状态分成两个子集:一个由终态组成,一个由非态组成:T0,T1,T2,T3,T4 T5 T0,T1,T2,T3 T4 T5 T0,T1,T2 T3 T4 T5 T0 T1,T2 T3 T4 T5 在等价状态子集T1,T2中选状态 T2 做代表,消去其他状态 T1,把从消去状态 T1 射出和射入的弧都引到代表状态 T2 上,得到化简后的 DFA:A3 0 X 1 B C Y 1 1 0 A2 A1 1 T0 T1 T2 T3 T4 T5 1 1 1 1 1 1 0 0 0 0 0 构造正规式相应的 DFA T0 T2 T3 T4 T5 1 1 1 1 1 0 0 0 0
- 温馨提示:
1: 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
2: 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
3.本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
5. 装配图网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。