1、构造正规式相应的 DFA：1(0|1)*101按照以下三步：（1）由正规表达式构造转换系统（NFA）（2）由转换系统（NFA）构造确定的有穷自动机 DFA（3）DFA 的最小化答：（1）首先构造与正规式 1（0|1）*101 相应的 NFA，然后再将 NFA 确定化。为正规式构造 NFA 的方法为“语法制导”法，即依据正规式的语法构造来构造。首先将正规式r=1（ 0|1）*101 分解成 r=r1,r2r3，其中：r1=1，r2=（0|1 ）*，r3=101。对于 r1，有：X A1对于 r2，有：A0,1对于 r3，有：X B C Y1 10因此，与正规式 r=r1r2r3 相对应的 NFA
2、 如图所示为：A0,1X1B C Y1 10展开为：A30X1B C Y1 10A2A11 （2）将 NFA 转换成 DFA采用子集法，即 DFA 的每个状态对应 NFA 的一个状态集合。构造 DFA 的状态集 C，假定C=T0， T1，Ti，集中 T0=-closure（X ） ，对于任何 aTi= -closure（Move（Ti，a ） ） 。Ti Ti0 Ti1A0 T0 A1，A2，A3=T1A1，A2，A3 T1 A2，A3=T2 A2，A4，A3=T3A2，A3 T2 A2，A3=T2 A2，A4，A3=T3A2，A3，A4 T3 A2，A5，A3=T4 A2，A4，A3=T3A
3、2，A3，A5 T4 A2，A3=T2 A2，A4，A6，A3=T6A2，A3，A4，A6 T5 A2，A5，A3=T4 A2，A4，A3=T3DFA 的状态转换图T0 T1 T2 T3 T4 T511 1111 00 000（3）化简 DFA：分割法，把 DFA 的状态集分成一些不想交的子集，使得不同的两子集的状态是可区别的，同一子集的状态是等价的。首先，将状态分成两个子集：一个由终态组成，一个由非态组成：T0， T1，T2，T3，T4 T5T0，T1 ，T2，T3 T4 T5 T0，T1 ，T2 T3 T4 T5T0 T1，T2 T3 T4 T5在等价状态子集T1，T2 中选状态 T2 做代表，消去其他状态 T1，把从消去状态 T1 射出和射入的弧都引到代表状态 T2 上，得到化简后的 DFA：T0 T2 T3 T4 T511 111 0000
