具有ε动作的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的确定化。
温馨提示:答案为网友推荐,仅供参考