构造正规式相应的.doc

文档介绍：构造正规式相应的DFA： 1(0|1)*101
按照以下三步：
由正规表达式构造转换系统(NFA)
由转换系统(NFA)构造确定的有穷自动机DFA
DFA的最小化
答：(1)首先构造与正规式1(0|1)*101相应的NFA,然后再构造正规式相应的DFA： 1(0|1)*101
按照以下三步：
由正规表达式构造转换系统(NFA)
由转换系统(NFA)构造确定的有穷自动机DFA
DFA的最小化
答：(1)首先构造与正规式1(0|1)*101相应的NFA,然后再将NFA确定化。为正规 式构造NFA的方法为“语法制导”法，即依据正规式的语法构造来构造。首先将正规式r=l (0|1) *101 分解成 r=rl,r2r3,其中：
rl = l, r2= (0|1) *, r3=101o
对于rl,有：
对于r2,有:
对于r3,有:
因此，与正规式r=rlr2r3相对应的NFA如图所示为:
展开为:
(2)将NFA转换成DFA
采用子集法，即DFA的每个状态对应NFA的一个状态集合。构造DFA的状态集C,假定
C={TO, Tl, ...Ti},集中 T0= e -closure (X),对于任何 a£ ETi= e -closure (Move (Ti, a))。
Ti
TiO
Til
(AO} TO
(}
(Al, A2, A3}=T1
{Al, A2, A3} Tl
(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, A3}=T3
(A2, A3, A5} T4
(A2, A3}=T2
{A2, A4, A6, A3}=T6
(A2, A