将NFA确定化的源程序

Question

如题所述

Answer 1

具有ε动作的NFA的确定化——子集法由于现在的NFA中具有ε动作，故下面要介绍的构造相应DFA的方法和定理3�1中所给出的方法有所不同。
设已给具有ε动作的非确定的有限自动机
M=(K,Σ,f,S0,Z)
则构造相应的DFA
M′=(K′,Σ,f′,q0,Z′)
的基本思路是： 首先把从S0出发，仅经过任意条ε矢线所能到达的状态所组成的集合作为M′的初态q0，然后分别把从q0出发，经过对输入符号a∈Σ的状态转移所能到达的状态 (包括转移后再经ε矢线所能到达的状态)组成的集合作为M′的状态，如此等等，直到不再有新的状态出现为止。具体地说，构造K′及f′的步骤可递归地描述如下。
1�令K′={εCLOSURE(S0)}(给出M′的初态q0)。
2�对于K′中任一尚未标记的状态qi={Si1,Si2,…,Sim},Sik∈K，做：
(1) 标记qi；
(2) 对于每个a∈Σ，置
T=f({Si1,Si2,…,Sim},a)
qj=εCLOSURE(T)
(3) 若qj不在K′中，则将qj作为一个未加标记的状态添加到K′中，且把状态转移
f′(qi,a)=qj
添加到M′。
3�重复进行步骤2，直到K′中不再含有未标记的状态为止。对于由此构造的K′，我们把那些至少含有一个Z中的元素的qi作为M′的终态。
例3�4再考虑图310所示的NFA，对它应用上述算法进行确定化，我们有：
1�因为εCLOSURE(S0)={S0,S1,S2,S3}，故将q0={S0,S1,S2,S3}作为未标记的状态置于K′中。
2�此时K′中仅有惟一的未标记状态q0，故
(1) 标记q0；
(2) 作
f′(q0,a)=εCLOSURE(f({S0,S1,S2,S3},a))=
εCLOSURE(S0)=q0
f′(q0,b)=εCLOSURE(f({S0,S1,S2,S3},b))=
εCLOSURE({S1,S3})={S1,S3}
且把q1={S1,S3}作为未加标记的状态加入K′中，再作
f′(q0,c)=εCLOSURE(f({S0,S1,S2,S3},c))=
εCLOSURE({S2})={S2,S3}
且把q2={S2,S3}作为未加标记的状态加入K′中。
3�此时，K′={q0,q1,q2}，其中q1,q2均未加标记，故
(1) 标记q1；
(2) 作
f′(q1,a)=εCLOSURE(f({S1,S3},a))=
εCLOSURE(�)=�
f′(q1,b)=εCLOSURE(f({S1,S3},b))=
εCLOSURE({S1,S3})=q1
f′(q1,c)=εCLOSURE(f({S1,S3},c))=此时，K′未增大，但q2尚未标记，故
(1) 标记q2；(2) 类似地可求得f′(q2,a)=f′(q2,b)=� f′(q2,c)=q2；至此，K′中的状态q0,q1,q2已全部标记完毕，故确定化的过程结束。最后，容易看到，Z′={q0,q1,q2}，且所得的DFA M′如图312所示。
例3�5对于图311所示的NFA，利用上述算法所得的DFA如图313所示。其中，圆圈中的数字都是原NFA的状态编号，在图313中，q0={0,1,7,11,14,19,24,26,28,30,33,35,38,40}。标有“#”的状态意指在这些状态之下，当扫视到未在其射出弧上出现过的字母或数字字符时，将转移到状态25。显然，在按图313实现词法分析程序时，同样应采取某种策略，以区别源程序中的关键字和标识符。
图3－13M确定化后的DFA
最后，顺便提及，上面所给出的NFA确定化的算法，同样可应用于不含ε动作的NFA的确定化。