PPT《*》

0 1

0 1

0 1 正规式与有限自动机 引入新的开始状态x和新的接收状态y;

消除状态s2;

消除状态s1;

消除状态s0;

最终得到一个R:(0|1(01*0)*1)* * 《编译原理与技术》讲义 * * 《编译原理与技术》讲义 * NFA的确定化(转换到DFA) 子集构造法对NFA进行模拟.NFA的转换表中每个条目是状态子集,而在DFA中则为单一的状态.NFA到DFA的转换的一般想法是,让DFA中的每个状态代表NFA中的状态子集.DFA用它的状态去记住NFA在读入每个输入符号后能到达的所有状态的集合,即在DFA在读了符号a1a2…an后到达代表NFA状态子集T的状态,而这个子集T是从NFA开始状态沿着标记有a1a2…an的路径所能到达的所有状态的集合. * 《编译原理与技术》讲义 * NFA的确定化(转换到DFA) 子集构造法DFA的 状态 Sd是NFA的非空状态子集,Sd?2SDFA的初态Sd0-包括原NFA初态S0及其经?转换能到达的所有状态,即Sd0 = { S0,u | S0 ??* u }= ?-closure({S0}) ?-closure(T) = { 从状态集合T的每一个状态t出发,经过若干空转换( ?转换)所能到达的所有状态} * 《编译原理与技术》讲义 * NFA的确定化(转换到DFA) 子集构造法DFA状态转换函数?d : Sd1 ?a Sd2 , Sd2 = { t,u | s ?a t , s∈Sd1 , t ??* u ?-closure( { t | s ?a t , s∈Sd1 } )DFA的终态F-{ 含有原NFA终态的Sd } * 《编译原理与技术》讲义 * 初始时,DFA的状态集合Dstates中只有初态Sd0且未标记. while ( Dstates中有未标记的状态 T ) do{ 标记 T;

for 每个输入符号 a do { U = ?-closure( { s | NFA状态转换函数?(t,a)=s, t?T} ) if U 不在 Dstates中 则将其加入Dstates且未加标记;

记下DFA状态转换函数?d(T,a)= U * 《编译原理与技术》讲义 * NFA的确定化 e.g.14 确定化以下NFA M. X ?

1 3 ? b a

2 ? y

6 ? b a

4 5 a a b b * 《编译原理与技术》讲义 * e.g.14 确定化以下NFA M.(续1) ?状态Sd a b ?d : Sd1 ?a Sd2 ?d : Sd1 ?b Sd2 Sd0={ x,3,1} {3,4,1} {3,5,1} {3,4,1} {3,2,4,1,6,y} {3,5,1} {3,5,1} {3,4,1} {3,2,5,1,6,y} {3,2,4,1,6,y} {3,2,4,6,1,y} {3,5,6,1,y} {3,2,5,1,6,y} {3,4,6,1,y} {3,2,5,6,1,y} * 《编译原理与技术》讲义 * e.g.14 确定化以下NFA M.(续2) ?状态Sd a b ?d : Sd1 ?a Sd2 ?d : Sd1 ?b Sd2 {3,5,6,1,y} {3,6,4,1,y} {3,2,6,5,1,y} {3,4,6,1,y} {3,2,6,4,1,y} {3,6,5,1,y} * 《编译原理与技术》讲义 * e.g.14 确定化以下NFA M.(续3) { x,3,1} { 3,4,1} { 3,5,1} {3,2,4,1,6,y} {3,2,5,1,6,y} {3,5,6,1,y} {3,4,6,1,y} a b a a b a b a b b a b a b * 《编译原理与技术》讲义 * e.g.14 确定化以下NFA M.(续4)

0 1

2 3

4 5

6 a b a a b a b a b b a b a b * 《编译原理与技术》讲义 * D........