构造正规式相应的DFA 构造正规式相应的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,有: 1 X A 对于r2,有: 0,1 A 对于r3,有: X 1 B 0 C 1 Y 因此,与正规式r=r1r2r3相对应的NFA如图所示为: 0,1 1 X A 1 B 0 C 1 Y 展开为: 构造正规式相应的DFA 0 1 X A1 ε A2 ε 1 A3 B 0 C 1 Y 1 (2)将NFA转换成DFA 采用子集法,即DFA的每个状态对应NFA的一个状态集合。构造DFA的状态集C,假定C={T0,T1,…Ti},集中T0=ε-closure(X),对于任何a∈∑Ti=ε-closure(Move(Ti,a))。 Ti {A0} T0 {A1,A2,A3} T1 {A2,A3} T2 {A2,A3,A4} T3 {A2,A3,A5} T4 {A2,A3,A4,A6} T5 DFA的状态转换图 0 1 1 T1 Ti0 {} {A2,A3}=T2 {A2,A3}=T2 {A2,A5,A3}=T4 {A2,A3}=T2 {A2,A5,A3}=T4 Ti1 {A1,A2,A3}=T1 {A2,A4,A3}=T3 {A2,A4,A3}=T3 {A2,A4,A3}=T3 {A2,A4,A6,A3}=T6 {A2,A4,A3}=T3 0 0 T0 0 T2 1 T3 T4 1 T5 0 1 1 (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射出与射入 本文来源：https://www.wddqw.com/doc/fa14c7acdf36a32d7375a417866fb84ae55cc369.html