第三章 詞法分析(2)(文件)
【正文】 orithm For Subset Construction initially, ?closure(s0) is only (unmarked) state in Dstates。 Dtran[T,a] := U end end 35 Fig 326 Computation of ?closure push all states in T onto stack。 push u onto stack end end 36 ? 如果 DFA的某個(gè)狀態(tài)至少包含 NFA的一個(gè)接受狀態(tài)，那么，這個(gè)狀態(tài)是 DFA的一個(gè)接受狀態(tài)。 輸出：接受 L(r)的 NFA 。 ? N(r)只有一個(gè)開始狀態(tài)和一個(gè)接受狀態(tài) ， 接受狀態(tài)沒有向外的轉(zhuǎn)換 。 55 r9 r7 r8 r4 r3 r5 r6 * ) ( r2 r1 a | b a b r7 = r5 r6 a 2 3 start b 4 5 1 ? 6 ? ? ? ? 0 7 ? ? ? a 8 56 1 9 start ? 0 a b ? a b 6 7 8 2 3 4 5 ? ? ? ? ? ? r9 r7 r8 r4 r3 r5 r6 * ) ( r2 r1 a | b a b 57 1 2 start a 0 a b b (a|b)*ab的兩個(gè) NFA的比較 1 9 start ? 0 a b ? a b 6 7 8 2 3 4 5 ? ? ? ? ? ? 手工構(gòu)造的 NFA 語法制導(dǎo)的算法構(gòu)造的 NFA 58 B D start a A a b b a b C b a 1 2 start a 0 a b b a b 識(shí)別語言 (a|b)*ab 的 自動(dòng)機(jī) DFA可以化簡(jiǎn) 1 2 start a 0 a b b 1 9 start ? 0 a b ? a b 6 7 8 2 3 4 5 ? ? ? ? ? ? 59 DFA的化簡(jiǎn) DFA Minimization ? 每個(gè)正規(guī)表達(dá)式都可以由唯一的狀態(tài)數(shù)最少的DFA識(shí)別 (minimal DFA)。 ? 重復(fù)劃分組的過程，直至不需要繼續(xù)劃分。 ) b. Replace G in ?new by the set of all these subgroups. Minimizing the Number of States of DFA 66 3. Compare ?new and ?. If equal, ?final:= ? then proceed to 4, else set ? := ?new and goto 2. 4. Aggregate states belonging in the groups of ?final 5. If M? has a dead state, that is, a state d that is not a accepting and that has transitions to itself on all input symbols, then remove d from M?. Also remove any states not reachable from the start state. Any transitions to d from other states bee undefined. Minimizing the Number of States of DFA 67 B start a A a b b a a E b D C b b a Current partition Split on a Split on b ?0 (ABCD) (E) No change (ABC)(D)(E) ?1 (ABC)(D) (E) No change (AC)(B)(D)(E) ?2 (AC)(B)(D) (E) No change No change 68 B start a A a b b a a E b D C b b a ?final : (AC) (B) (D) (E) B start a AC a b b a E b D b MinimumDFA 69 另一個(gè)例子： 從 a(b|c)*構(gòu)造 NFA 70 用子集構(gòu)造法從 NFA得到 DFA 71 構(gòu)造最小化 DFA 72 例：考慮正規(guī)表達(dá)式 (a|b)*(aa|bb)(a|b)* 0 start 1 2 a b 3 4 5 ? 6 final a b ? ? ? a a b b 73 用子集構(gòu)造法得到的 DFA： q1 start a a b b b a q2 q3 q4 q6 a b q5 q7 b b a b a 74 Current partition Split on a Split on b ?0 (123)(4567) (13)(2)(4567) (1)(2)(3)(4567) Final partition 構(gòu)造最小狀態(tài)的 DFA： 75 另一種等價(jià)的構(gòu)造方法： 填表算法 ? 狀態(tài)的等價(jià)性 – p和 q等價(jià)： ? 若兩個(gè)狀態(tài)不等價(jià)，則稱二者是可區(qū)分的。 symbol, … d(d,0) ?? d(a,0) d(d,1) ?? d(a,1) A E B F C G D H 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 80 f b c d e a g h g f e d c b d(e,0) ?? d(a,0) d(e,1) ?? d(a,1) 3. For each unmarked pair amp。 symbol, … A E B F C G D H 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 84 f b c d e a g h g f e d c b 4. Coalesce unmarked pairs of states. (a,e) a ? e b ? h d ? f A E B F C G D H 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 ae bh df c g 0 0 0 0 0 1 1 1 1 1 85 f b c d e a g h g f e d c b (a,e) None. A E B F C G D H 0 0 0
環(huán)評(píng)公示相關(guān)推薦
鄂ICP備17016276號(hào)-1