1、第六講 正規(guī)式與有限自動(dòng)機(jī)的等價(jià),,7 正規(guī)式與有限自動(dòng)機(jī)等價(jià),A. ?上的NFA M能識(shí)別的字的全體L(M)是?上的正規(guī)式B. 對(duì)?上任何正規(guī)式V,存在一個(gè)?上的確定的有限自動(dòng) 機(jī)M,使得L(V) = L(M)證A. 將NFA M化為正規(guī)式 要點(diǎn): (I) 引入兩個(gè)結(jié)點(diǎn) X, Y; 按以下方式得等價(jià)的M’ 用?弧連

2、接X及M的所有初態(tài); 用?弧連接Y及M的所有終態(tài) (II) 消去M’中所有結(jié)點(diǎn)直至剩下X和Y為止. 轉(zhuǎn)換法則（ P54圖3.10 ） V1 V2 V1

3、 V2 V2 V1 V3 V1 V2 V1|V2 V1（V2）* V3,,,,,,,,,,,,,,,,,,,,,,,,,,,,,證B

4、. 就正規(guī)式V,引入初態(tài)X和終態(tài)Y. 先構(gòu)造NFA V 法則(P50圖3.7): 確定化: 給定 I為M的狀態(tài)子集, a為 ?中字符. 引入概念

5、 I的?閉包,記為 ?_closure(I): (a) I中元在閉包中 (b)一切 I中元通過?弧能到的狀態(tài) Ia= ?_closure(J): J是所有那些由I中元經(jīng)a弧能到達(dá)的狀態(tài)全體,X,,Y,例子,I= ?_closure({1}) = {1,2} Ia = ?_closure(J)

6、= ?_closure({3,4,5}) = {2,3,4,5,6,7,8} ? a ? ? a ?

7、 a ?,1,5,2,6,3,8,4,7,,,,,,,,,轉(zhuǎn)換矩陣構(gòu)造過程(確定化) 設(shè) ?={a, b}, NFA M 初態(tài)集為 X,I Ia Ib ?_closure(X)

8、 依Ia 計(jì)算 依Ib 計(jì)算 選取未出現(xiàn)在第一列者填入第一列下行 位置作為I, 重新計(jì)算 Ia 和 Ib,,,,例: 為正規(guī)式 (a|b)* (aa|bb)(a|b)*設(shè)計(jì)DFA,(1) 對(duì)應(yīng)的NFA (a|b)* (aa

9、|bb)(a|b)* a a a a ? ? ? ? b

10、 b b b,X,,Y,,X,5,1,3,4,2,6,Y,,,,,,,,,,,,,,,,,,構(gòu)造轉(zhuǎn)換矩陣進(jìn)行確定化(P50表3.3) I Ia Ib {X,5,1} {5,3,1}

11、 {5,4,1} {5,3,1} {5,1,3,2,6,Y} {5,1,4} … 最后對(duì)表項(xiàng)進(jìn)行編號(hào),以新編號(hào)重新繪圖.含原初態(tài)的編號(hào)為初態(tài),含原終態(tài)的編號(hào)為終態(tài). (參見P51圖3.8),,,,,8 DFA 的化簡(jiǎn),A. 等價(jià) DFA M中兩個(gè)狀態(tài) s, t

12、等價(jià), 如果L(s)=L(t). (即從s出發(fā)識(shí)別的字集等于從t出發(fā)讀出的字集)B. 可區(qū)分 L(s) ? L(t). 如終態(tài) ----- 可讀? 非終態(tài) ----- 不識(shí)別? 所以二者不等價(jià) 例 P51的圖3.8中狀態(tài)1 和2可以區(qū)分C. DFA M狀態(tài)最少化算法原理 把M的狀態(tài)集分為一

13、些不相交的子集,使得任何兩個(gè)不同的子集的狀態(tài)是可分的; 同一子集中的任何兩個(gè)狀態(tài)都是等價(jià)的. 最后從每個(gè)子集選出一個(gè)代表,同時(shí)消區(qū)其它等價(jià)狀態(tài).,D. 最少化算法(P56-58) 例子3.6 (P51圖3.8),I) 令 ? = {S1, S2} S1為非終態(tài)集; S2為終態(tài)集. 可區(qū)分II) 設(shè) ? = {S1, S2, …, Sn }

14、 (Si , Sj 可區(qū)分, 各Si 待區(qū)分) 如果存在 a??和某個(gè)Si , 使得Sia 分別落在?中 p 個(gè)不同的子集, 則將Si 分為 p 個(gè)更小的狀態(tài)子集Si1, Si2, …, Sip, 使得對(duì)每個(gè)Sij 而言, Sija全部包含在 ? 中的同一子集中. (注意: Si 中一切遇a 無定義的狀態(tài)歸為一類(一個(gè)子集)) 如此, 每細(xì)分一次得一個(gè) ?newIII) 若 ?n

15、ew ? ?, 則將 ?new 作為 ?重復(fù) II)IV) 對(duì)?中任意子集Si = {Si1, Si2, …, Sik}選一個(gè)代表狀態(tài)如Si1. 將原來導(dǎo)入 Si2, …, Sik的弧改為導(dǎo)入Si1. 然后刪除Si2, …, Sik. Si1為新的初態(tài) ? Si 中有原初態(tài); Si1為新的終態(tài) ? Si 中有原終態(tài)V) 在IV步結(jié)果基礎(chǔ)上,刪除所有無用狀態(tài). 即從初態(tài)永遠(yuǎn)到達(dá)不了