【正文】 個(gè)為 x結(jié) 點(diǎn)，一個(gè)為 y結(jié)點(diǎn)。 ? closure(move(T3,b))={1,2,4,5,6,7,10},令其為 T4，在入 C中， T4未被標(biāo)記 T4： ?closure(move(T4,a))={1,2,3,4,6,7,8}，即 T1。 T3=?closure(move(T1,b))={1,2,4,5,6,7,9}，將 T3加 入 C中， T3未被標(biāo)記 49 盛威網(wǎng)：專業(yè)的計(jì)算機(jī)學(xué)習(xí)網(wǎng)站 T2： ?closure(move(T2,a))={1,2,3,4,6,7,8}，即 T1， T1已 在 C中。} ?構(gòu)造 NFA N的狀態(tài) K的子集的算法，見圖 ： ?假定所構(gòu)造的子集族為 C，即 C= (T1, T2,... Ti),其中 T1, T2,... Ti為狀態(tài) K的子集 47 盛威網(wǎng)：專業(yè)的計(jì)算機(jī)學(xué)習(xí)網(wǎng)站 48 盛威網(wǎng)：專業(yè)的計(jì)算機(jī)學(xué)習(xí)網(wǎng)站 ?例 應(yīng)用圖 NFA N構(gòu)造子集 步驟如下： ?closure(0)：令 T0=?closure(0)={0,1,2,4,7}， T0未 被標(biāo)記，它現(xiàn)在是子集族 C的唯一成員 T0：令 T1=?closure(move(T0,a))={1,2,3,4,6,7,8}，將 T1 加入 C中， T1未被標(biāo)記。用 [S1 S2... Sj]表示 S 的元素，其中 S1, S2,... Sj是 K的狀態(tài)。用 標(biāo)明初態(tài)；否則第一行即是初態(tài)，相應(yīng)終態(tài)行在表的右 端標(biāo)以 1，非終態(tài)標(biāo)以 0 33 盛威網(wǎng)：專業(yè)的計(jì)算機(jī)學(xué)習(xí)網(wǎng)站 圖 矩陣表示 ?例 DFA的矩陣表示如圖 ： 34 盛威網(wǎng)：專業(yè)的計(jì)算機(jī)學(xué)習(xí)網(wǎng)站 ?若 t? ∑*， f(S， t)=P，其中 S為 M的開始狀態(tài)， P ? Z， Z為終態(tài)集，則稱 t為 DFA M所接受 （識(shí)別） ?設(shè) Q∈ K，函數(shù) f(Q,ε)=Q，一個(gè)輸入符號(hào)串 t（ t1tx， t1 ∈ ∑,tx ∈ ∑*），在 DFA M上運(yùn)行的定義為： f(Q,t1tx)=f(f(Q,t1),tx) 35 盛威網(wǎng)：專業(yè)的計(jì)算機(jī)學(xué)習(xí)網(wǎng)站 ?例如，證明 t=baab被例 DFA所接受 ?f（ S， baab） =f（ f（ S， b）， aab） =f（ V， aab） =f（ f （ V， a）， ab） =f（ U， ab） =f（ f（ U， a）， b） =f（ Q， b） =Q ?Q屬于終態(tài) ?得證 36 盛威網(wǎng)：專業(yè)的計(jì)算機(jī)學(xué)習(xí)網(wǎng)站 ?DFA M所能接受的符 號(hào) 串的全體記為 L(M) ?結(jié)論： ?上一個(gè)符 號(hào) 串集 V???是正規(guī)的，當(dāng)且僅當(dāng)存 在一個(gè) ?上的確定有窮自動(dòng)機(jī) M，使得 V=L(M) ?DFA的確定性表現(xiàn)在轉(zhuǎn)換函數(shù) f:K ∑→K 是一個(gè)單值 函數(shù)，也就是說 ,對(duì)任何狀態(tài) k∈ K和輸入符號(hào) a ∈ ∑， f(k,a)唯一地確定了下一個(gè)狀態(tài) 37 盛威網(wǎng)：專業(yè)的計(jì)算機(jī)學(xué)習(xí)網(wǎng)站 二 .丌確定的有窮自動(dòng)機(jī) NFA ?一個(gè) NFA： M=（ K， ?， f， S， Z） ?K是一個(gè)有窮集，它的每個(gè)元素稱為一個(gè)狀態(tài) ??是一個(gè)有窮字母表，它的每個(gè)元素稱為一個(gè)輸入符號(hào) ?f是一個(gè)從 K? ?* 到 K的子集的映像，即： K* ?* → 2 K ?S?K是一個(gè)非空初態(tài)集 ?Z?K是一個(gè)終態(tài)集 38 盛威網(wǎng)：專業(yè)的計(jì)算機(jī)學(xué)習(xí)網(wǎng)站 ?例 ：一個(gè) NFA M=（ {0， 1， 2， 3， 4}， {a， b}， f， {0}， {2,4}）其中 ?f(0,a)={0,3} f(2,b)={2} ?f(0,b)={0,1} f(3,a)={4} ?f(1,b)={2} f(4,a)={4} ?f(2,a)={2} f(4,b)={4} ?它的狀態(tài)圖表示如圖 ： 39 盛威網(wǎng)：專業(yè)的計(jì)算機(jī)學(xué)習(xí)網(wǎng)站 40 盛威網(wǎng)：專業(yè)的計(jì)算機(jī)學(xué)習(xí)網(wǎng)站 ?一個(gè) NFA也可以用一個(gè)矩陣表示 ... ?∑*上的符 號(hào) 串 t在 NFA N上運(yùn)行 ... ?∑*上的符 號(hào) 串 t被 NFA N識(shí)別（讀出、接受） ... ?DFA是 NFA的特例 ?對(duì)每個(gè) NFA N存在一個(gè) DFA Ｍ ,使得 L(M)=L(N) ?對(duì)于任何兩個(gè)有窮自動(dòng)機(jī) M和 N，如果 L(M)=L(N)，則稱 M與 N是等價(jià)的 41 盛威網(wǎng)：專業(yè)的計(jì)算機(jī)學(xué)習(xí)網(wǎng)站 三 .NFA轉(zhuǎn)換為等價(jià)的 DFA ?定理： 設(shè) L為一個(gè)由不確定的有窮自動(dòng)機(jī)接受的集合，則 存在一個(gè)接受 L的確定的有窮自動(dòng)機(jī) ?將 NFA轉(zhuǎn)換成接受同樣語(yǔ)言的 DFA，這種算法稱為 子集法 42 盛威網(wǎng)：專業(yè)的計(jì)算機(jī)學(xué)習(xí)網(wǎng)站 ?定義對(duì)狀態(tài)集合 I的幾個(gè)有關(guān)運(yùn)算： ? I的 ?閉包，表示為 ?closure(I)，定義為一狀態(tài) 集，是狀態(tài)集 I中的任何狀態(tài) S經(jīng)任意條 ?弧而能到達(dá)的狀 態(tài)的集合。若 x和 y都是正規(guī)式 ， B?VN ，則： (R1) 對(duì)形如 A xy的 正規(guī)產(chǎn)生式 ，重寫為 ： A xB， B y (R2)對(duì)形如 A x*y的 正規(guī)產(chǎn)生式 ，重寫為： A xB， A y， B xB， B y (R3)對(duì)形如 A x?y的 正規(guī)產(chǎn)生式 ，重寫為 : A x， A y 不斷應(yīng)用 R做變換，直到每個(gè)產(chǎn)生式右端只含一個(gè) VN 24 盛威網(wǎng)：專業(yè)的計(jì)算機(jī)學(xué)習(xí)網(wǎng)站 例 將 r=a(a|d)*轉(zhuǎn)換成相應(yīng)的正規(guī)文法 令 S是文法的開始符號(hào)，形成 S a(a|d)*： R1 S aA A (a|d)* R2 S aA A (a|d)B A ? B (a|d)B B ? R3 S aA A ? A aB A dB B aB B dB B ? 25 盛威網(wǎng)：專業(yè)的計(jì)算機(jī)學(xué)習(xí)網(wǎng)站 ： 基本上是上述過程的逆過程，最后只剩下一個(gè)開始符 號(hào)定義的正規(guī)式，其轉(zhuǎn)換規(guī)則如表 ： 26 盛威網(wǎng)：專業(yè)的計(jì)算機(jī)學(xué)習(xí)網(wǎng)站 ?例 G[s]: S aA S a A aA A dA A a A d ① S aA|a A aA|a|dA|d (a|d)A|(a|d) (a|d)*(a|d) ② s=a(a|d)*(a|d)|a=a((a|d)*(a|d)|ε)=a((a|d)*|ε) ③ r=a(a|d)* 27