《构造正规式相应的DFA346.pdf》由会员分享，可在线阅读，更多相关《构造正规式相应的DFA346.pdf（3页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
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