构造正规式相应的dfa

《构造正规式相应的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