构造正规式相应的dfa

构造正规式相应的dfa

ID:26204930

大小:79.03 KB

页数:3页

时间:2018-11-25

构造正规式相应的dfa_第1页
构造正规式相应的dfa_第2页
构造正规式相应的dfa_第3页
资源描述:

《构造正规式相应的dfa》由会员上传分享,免费在线阅读,更多相关内容在工程资料-天天文库

1、构造正规式相应的DFA:1(0

2、1)*101按照以下三步:(1)由正规表达式构造转换系统(NFA)(2)由转换系统(NFA)构造确定的有穷自动机DFA(3)DFA的最小化答:(1)首先构造与正规式1(0

3、1)*101相应的NFA,然后再将NFA确定化。为正规式构造NFA的方法为“语法制导”法,即依据正规式的语法构造来构造。首先将正规式r=1(0

4、1)*101分解成r=r1,r2r3,其中:r1=1,r2=(0

5、1)*,r3=101。对于r1,有:XA1对于r2,有:A0,1对于r3,有:XBCY110因此,与正规式r=r1r2r3相对应的NFA如图所示为

6、:A0,1X1BCY110展开为:A30X1BCY110A2A11εε(2)将NFA转换成DFA采用子集法,即DFA的每个状态对应NFA的一个状态集合。构造DFA的状态集C,假定C={T0,T1,…Ti},集中T0=ε-closure(X),对于任何a∈∑Ti=ε-closure(Move(Ti,a))。TiTi0Ti1{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{A2,A4

7、,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}=T3DFA的状态转换图T0T1T2T3T4T511111100000(3)化简DFA:分割法,把DFA的状态集分成一些不想交的子集,使得不同的两子集的状态是可区别的,同一子集的状态是等价的。首先,将状态分成两个子集:一个由终态组成,一个由非态组成:{T0,T1,T2,T3,T4}{T5}{T0,T1,T2,T3}{T4}{T5}{T0,T1,T2}{T3}{T4}{T5}{T0}{T1,T

8、2}{T3}{T4}{T5}在等价状态子集{T1,T2}中选状态T2做代表,消去其他状态T1,把从消去状态T1射出和射入的弧都引到代表状态T2上,得到化简后的DFA:T0T2T3T4T5111110000

当前文档最多预览五页,下载文档查看全文

此文档下载收益归作者所有

当前文档最多预览五页,下载文档查看全文
温馨提示:
1. 部分包含数学公式或PPT动画的文件,查看预览时可能会显示错乱或异常,文件下载后无此问题,请放心下载。
2. 本文档由用户上传,版权归属用户,天天文库负责整理代发布。如果您对本文档版权有争议请及时联系客服。
3. 下载前请仔细阅读文档内容,确认文档内容符合您的需求后进行下载,若出现内容与标题不符可向本站投诉处理。
4. 下载文档时可能由于网络波动等原因无法下载或下载错误,付费完成后未能成功下载的用户请联系客服处理。