正規(guī)式與有限自動機的等價

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

2、接X及M的所有初態(tài); 用?弧連接Y及M的所有終態(tài) (II) 消去M’中所有結(jié)點直至剩下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弧能到達的狀態(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 計算 依Ib 計算 選取未出現(xiàn)在第一列者填入第一列下行 位置作為I, 重新計算 Ia 和 Ib,,,,例: 為正規(guī)式 (a|b)* (aa|bb)(a|b)*設(shè)計DFA,(1) 對應的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)換矩陣進行確定化(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} … 最后對表項進行編號,以新編號重新繪圖.含原初態(tài)的編號為初態(tài),含原終態(tài)的編號為終態(tài). (參見P51圖3.8),,,,,8 DFA 的化簡,A. 等價 DFA M中兩個狀態(tài) s, t

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

13、些不相交的子集,使得任何兩個不同的子集的狀態(tài)是可分的; 同一子集中的任何兩個狀態(tài)都是等價的. 最后從每個子集選出一個代表,同時消區(qū)其它等價狀態(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??和某個Si , 使得Sia 分別落在?中 p 個不同的子集, 則將Si 分為 p 個更小的狀態(tài)子集Si1, Si2, …, Sip, 使得對每個Sij 而言, Sija全部包含在 ? 中的同一子集中. (注意: Si 中一切遇a 無定義的狀態(tài)歸為一類(一個子集)) 如此, 每細分一次得一個 ?newIII) 若 ?n

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