3.3.5具有ε动作的NFA的确定化 ·设已给具有ε动作的NFAM=(K,Σ，f,S0,Z),构造相应的DFAM=(K', ,f',q,Z)的方法是，先令q0=[8-CLOSURE(S小，然后对每个a∈Σ， 令[ε-CLOSURE(f(qo,a]为新状态，如此反复，直到无新状态 产生： 1.K'=([e-CLOSURE(So)]);f=; 2.对K中尚未被标记的状态qi=[Sih,S,…,Sim: (1)标记q; (2)对于每个ae2,令Ta=fSi,Sz,,Sim},a;q=[g-CLOSURE(Ta; (3)若qK,则令K=KUq； (4)令fP=fU{f(q,a=q； 3.重复2，直到K中无未标记的状态； 4.令Z'={q|q∩Z≠}（这里把q视为集合）
3.3.5具有 动作的NFA的确定化 • 设已给具有动作的NFA M=(K,,f,S0,Z),构造相应的DFA M’=(K’, ,f’,q0,Z’)的方法是，先令q0=[-CLOSURE(S0)], 然后对每个a， 令 [-CLOSURE(f’(q0,a))]为新状态，如此反复，直到无新状态 产生： 1. 令 K’={[-CLOSURE(S0)]}; f’= ; 2. 对K’中尚未被标记的状态qi=[Si1,Si2,…,Sim]: (1)标记qi; (2)对于每个a,令Ta=f({Si1,Si2,…,Sim},a); qj= [-CLOSURE(Ta)]; (3)若qjK’,则令K’=K’{qj }; (4)令f’=f’ {f’(qj ,a)= qj }; 3. 重复2.,直到K’中无未标记的状态; 4. 令Z’={qj | qj Z} (这里把qj 视为集合)
确定化具有ε动作的NFA的例子 例3.4考虑前面引入的具有ε动作的NFA的例子(P63图3- 10) 1.q0=[0,1,2,3]==>K; 2.q0未标记，故(1)标记q0; (2)f(qo,a)=[8-CLOSURE(f(qo,a))]=q0; f(q0,b)=[8-CL0SURE(f(q,b)]=[1,3]=q1;q1==>K; f(q0,c)=[2,3]=q2;q2==>K'; 3.此时，K'={q0,q1,a2,q1,q2 are not marked..so,(1)mark q1; (2)letf(q1,a)=[e-CLOSURE(f(q1,a)]=☑； f(q1,b)=..=q1;f(q1,c)=.=; 4.q2 is not marked,so(1)mark q2; (2)f(q2,a=f'(q2,b)=0; f(q2,c)=q2;K'is not increased and all states are marked.Z'={q0,q1,q2)
确定化具有动作的NFA的例子 例3.4 考虑前面引入的具有动作的NFA的例子(P63图3- 10) 1.q0=[0,1,2,3]==>K’; 2.q0未标记,故(1)标记q0; (2)令f”(q0,a)= [-CLOSURE(f’(q0,a))] =q0; f”(q0,b)= [-CLOSURE(f’(q0,b))]=[1,3]=q1;q1==>K’; f”(q0,c)=[2,3]=q2; q2==>K’; 3. 此时,K’={q0,q1,a2},q1,q2 are not marked.so,(1) mark q1; (2) let f”(q1,a)= [-CLOSURE(f’(q1,a))]= ; f”(q1,b)=…=q1; f”(q1,c)=…= ; 4. q2 is not marked, so (1) mark q2; (2)f”(q2,a)= f”(q2,b)=; f”(q2,c)=q2; K’ is not increased and all states are marked. Z’={q0,q1,q2} q1 q0 q2 a b b c c
手工计算确定北的夯法 ·在人工进行NFA确定化时，可按下述的构造矩阵的方法实现： a b c q0:[0123] [0123] [13] [23] q1:[131 [131 [1 q2:[231 L[1 [1 [231 需要说明的是，本算法也适合于不含ε产生式的NFA的确定化. ·例3.5对于书中图3-13所示的NFA利用上述算法所得的DFA如P67图 3-13所示.其中，圆圈中的数字是原NFA的状态编号，在图3-13中， q0={0,1,7,11,14,19,24,26,28,30,33,35,40} ● 标有“#的状态为特殊状态，在该状态下，若遇非弧线上出现的字符，则 转到状态25
手工计算确定化的方法 • 在人工进行NFA确定化时,可按下述的构造矩阵的方法实现: _____________| a b c_ q0: [0123] | [0123] [13] [23] q1: [13] | [ ] [13] [ ] q2: [23] | [ ] [ ] [23] 需要说明的是,本算法也适合于不含产生式的NFA的确定化. • 例3.5 对于书中图3-13所示的NFA利用上述算法所得的DFA如 P67图 3-13所示.其中,圆圈中的数字是原NFA的状态编号,在图3-13中, q0={0,1,7,11,14,19,24,26,28,30,33,35,40}. • 标有“#”的状态为特殊状态,在该状态下,若遇非弧线上出现的字符,则 转到状态25
3.3.6DFA状态数的最小化 ·对于一DFA来说，其状态数可能并不是最小的.原因是DFA 中有些状态是“等价”的为得到效率高的DFA,需将这些 “等价”状态合并，这就是DFA的最小化. ·DFAM的最小化：构造等价的DFAM其状态数达到最小 ·可区分状态：设s,teK,s,t由某we*所区分if f(s,w)EZAf(t,w)gZ v(f(s,w)gZAf(t,w)EZ) 若w∈*，fs,w)∈Z台ft,wW∈Z,则称s与t等价不可区分 ·在一DFA中，等价状态可合并
3.3.6 DFA状态数的最小化 • 对于一DFA来说,其状态数可能并不是最小的.原因是DFA 中有些状态是“等价”的.为得到效率高的DFA,需将这些 “等价”状态合并,这就是DFA的最小化. • DFA M的最小化: 构造等价的DFA M’其状态数达到最小. • 可区分状态: 设s,tK, s,t由某w*所区分 iff ( f(s,w)Z f(t,w)Z ) ( f(s,w)Z f(t,w)Z ) 若w*, f(s,w)Z f(t,w)Z,则称 s与 t等价(不可区分) • 在一DFA中,等价状态可合并
DFA最小化算法 基本思想：将M的状态集K透步地进行划分加细，以期将K划分为满 足等价关弟的等价类，使得在同一类中的状态不可区分：在不同类 中的状态可区分.算法如下 1.先将状态集K划分为两个子集Z和K-Z,显然分属于这两个集合的状 态是可（被ε区分的.记π=亿，K-Z☑. 2.设当前的划分π中已含有m个子集：π=I1,I2,.,Im},其中，属于不同子 集的状态是可区分的，而属于同一子集中的状态则待区分现对每 个子集Ii=Si,S,,Sin中的各状态Sir(SirEK,l≤r≤n)进行考查， 看其是否可区分.若存在a∈∑，使得Su=f(Sip,aeI,Sv=f(Sia,a)∈Ik 则由假设，Su和Sv被子某个w所区分，进一步，Sip和Sia可被aw区 分：f(Sip,aw=f(Su,w)属于Zf(Sia,aw=f(Sv,w)不属于Z或反之 即S,与S可区分.细分，使其落入不同的更小的子集中.得到 新划分πnew.（细分1i的方法见下页)。 3.若πnew.不等于兀，则令元-兀new.转2. 4.对于最终的π，从每个划分块中任选一状态为代表，构成K,So的 代表为初态。若i⌒Z+,则1的代表∈Z;将引入（出）非代表的 矢线引向代表
DFA最小化算法 • 基本思想: 将M的状态集K逐步地进行划分加细,以期将K划分为满 足等价关系的等价类,使得在同一类中的状态不可区分;在不同类 中的状态可区分.算法如下: 1.先将状态集K划分为两个子集Z和K-Z,显然分属于这两个集合的状 态是可(被)区分的.记={Z,K-Z}. 2.设当前的划分中已含有m个子集:={I1,I2,…,Im},其中,属于不同子 集的状态是可区分的,而属于同一子集中的状态则待区分.现对每 个子集Ii={Si1,Si2,…,Sin}中的各状态Sir(SirK,1 r n )进行考查, 看其是否可区分.若存在a,使得Su=f(Sip,a) Ij, Sv=f(Siq,a) Ik 则由假设, Su和Sv被子某个w所区分,进一步, Sip 和Siq 可被aw 区 分: f(Sip,aw)=f(Su ,w)属于Z而f(Siq,aw)=f(Sv ,w)不属于Z(或反之), 即 Siq 与Sip 可区分.将Ii细分,使其落入不同的更小的子集中.得到 新划分new. （细分Ii的方法见下页）。 3.若new. 不等于,则令 =new. 转2. 4.对于最终的，从每个划分块中任选一状态为代表，构成K‘ ，S0的 代表为初态。若Ii Z，则Ii 的代表Z’；将引入(出)非代表的 矢线引向代表
细分划分块的方法 对每个子集[，a∈∑，令I=f(L,a)=Uf(S,a) SEl 若“的状态分别落入π中印个不同的子集，刚将 1,分个更小的于集虹，1，…，1。，使(L,） 落入同一子集 若某状态p∈I,使得(p,a)无意义，p与其 它任何使(q,a)有意义的状态∈I可区分
细分划分块的方法 . , , , , ( , ) , , , ( , ) ( , ) 1 2 落入同一子集 分为 个更小的子集 使得 若 的状态分别落入 中 个不同的子集 则将 对每个子集 令 I p I I I f I a I p I a I f I a f S a p j i i i i i i a i S I i a i i = = ( , ) . , ( , ) , 它任何使 有意义的状态 可区分 若某状态 使得 无意义 则 与其 i i f q a q I p I f p a p
DFA最小化的例子 1.π={0,1,2,3}，{4} {0,1,2,3}a={1}未区分； {0,1,2b={2,3},3}b={4,所以3与 0,1,2可区分；元={0,1,2，{3}，{4} 2.{0,1,2}a={1,未区分； {0,2}b={2,{1b={3},1与0,2可区分； π={0,2，{1,3}，{4 3.{0,2}a={1},{0,2}b={2不可区分， 元new=元.结束. 定理3.2最小状态数的DFA在同构意义下是唯一的
DFA最小化的例子 1.={{0,1,2,3},{4}} {0,1,2,3}a={1}未区分; {0,1,2}b={2,3}, {3}b={4}, 所以3 与 0,1,2 可区分; ={{0,1,2}, {3},{4}} 2.{0,1,2}a={1}, 未区分; {0,2}b={2},{1}b={3}, 1 与0,2可区分; ={{0,2},{1},{3},{4}}; 3. {0,2}a={1},{0,2}b={2}不可区分, new=.结束. 0 1 2 3 a a a b a b b b 定理3.2 最小状态数的DFA在同构意义下是唯一的. 0 1 3 2 4 a a a a a b b b b b b