【文章內容簡介】 和輸入符號 a ∈ ∑， f(k,a)唯一地確定了下一個狀態(tài) 37 盛威網：專業(yè)的計算機學習網站 二 .丌確定的有窮自動機 NFA ?一個 NFA： M=（ K， ?， f， S， Z） ?K是一個有窮集，它的每個元素稱為一個狀態(tài) ??是一個有窮字母表，它的每個元素稱為一個輸入符號 ?f是一個從 K? ?* 到 K的子集的映像，即： K* ?* → 2 K ?S?K是一個非空初態(tài)集 ?Z?K是一個終態(tài)集 38 盛威網：專業(yè)的計算機學習網站 ?例 ：一個 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 盛威網：專業(yè)的計算機學習網站 40 盛威網：專業(yè)的計算機學習網站 ?一個 NFA也可以用一個矩陣表示 ... ?∑*上的符 號 串 t在 NFA N上運行 ... ?∑*上的符 號 串 t被 NFA N識別（讀出、接受） ... ?DFA是 NFA的特例 ?對每個 NFA N存在一個 DFA Ｍ ,使得 L(M)=L(N) ?對于任何兩個有窮自動機 M和 N，如果 L(M)=L(N)，則稱 M與 N是等價的 41 盛威網：專業(yè)的計算機學習網站 三 .NFA轉換為等價的 DFA ?定理： 設 L為一個由不確定的有窮自動機接受的集合，則 存在一個接受 L的確定的有窮自動機 ?將 NFA轉換成接受同樣語言的 DFA，這種算法稱為 子集法 42 盛威網：專業(yè)的計算機學習網站 ?定義對狀態(tài)集合 I的幾個有關運算： ? I的 ?閉包，表示為 ?closure(I)，定義為一狀態(tài) 集，是狀態(tài)集 I中的任何狀態(tài) S經任意條 ?弧而能到達的狀 態(tài)的集合。 狀態(tài)集合 I的任何狀態(tài) S都屬于 ?closure(I) ? I的 a弧轉換，表示為 move(I,a)定義為狀態(tài)集合 J ，其中 J是所有那些可從 I的某一狀態(tài)經過一條 a弧而到達 的狀態(tài)的全體 43 盛威網：專業(yè)的計算機學習網站 ?使用圖 NFA N的狀態(tài)集合來理解上述兩個運算： ??closure(0)={0,1,2,4,7} ?令 A={0,1,2,4,7}, move(A,a)={3,8} ??closure({3,8})={1,2,3,4,6,7,8} 圖 NFA N 44 盛威網：專業(yè)的計算機學習網站 ?對于一個 NFA N=（ K， ?， f， K0， Kt）來說，若 I是 K 的一個子集，設 I＝ {s1,s2,?,s j}， a是 ∑中的一個元素，則 move(I,a)=f(s1,a) ∪ f(s2,a) ∪ ? ∪ f(sj,a) 45 盛威網：專業(yè)的計算機學習網站 ?假設 NFA N=(K, ?,f,K0,Kt)按如下辦法構造一個 DFA M=(S, ?,d,S0,St)，使得 L(M)=L(N)： ? M的狀態(tài)集 S由 K的一些子集組成。用 [S1 S2... Sj]表示 S 的元素，其中 S1, S2,... Sj是 K的狀態(tài)。并且約定，狀態(tài) S1, S2,... Sj是按某種規(guī)則排列的，即對于子集 {S1, S2}={ S2, S1,}來說， S的狀態(tài)就是 [S1 S2] ?M和 N的輸入字母表是相同的，即是 ? ?轉換函數是這樣定義的： D([S1 S2,... Sj],a)= [R1R2... Ri] 其中 {R1,R2,... , Ri} = ?closure(move({S1, S2,... Sj},a)) 46 盛威網：專業(yè)的計算機學習網站 ? S0=?closure(K0)為 M的開始狀態(tài) ? St={[Sj Sk... Se]，其中 [Sj Sk... Se]?S且 {Sj , Sk,... Se} ∩Kt?216。} ?構造 NFA N的狀態(tài) K的子集的算法，見圖 ： ?假定所構造的子集族為 C，即 C= (T1, T2,... Ti),其中 T1, T2,... Ti為狀態(tài) K的子集 47 盛威網：專業(yè)的計算機學習網站 48 盛威網：專業(yè)的計算機學習網站 ?例 應用圖 NFA N構造子集 步驟如下： ?closure(0)：令 T0=?closure(0)={0,1,2,4,7}， T0未 被標記，它現在是子集族 C的唯一成員 T0：令 T1=?closure(move(T0,a))={1,2,3,4,6,7,8}，將 T1 加入 C中， T1未被標記。令 T2=?closure(move(T0,b)) ={1,2,4,5,6,7}，將 T2加入 C中， T2未被標記 T1： ?closure(move(T1,a))={1,2,3,4,6,7,8}，即 T1， T1已 在 C中。 T3=?closure(move(T1,b))={1,2,4,5,6,7,9}，將 T3加 入 C中， T3未被標記 49 盛威網：專業(yè)的計算機學習網站 T2： ?closure(move(T2,a))={1,2,3,4,6,7,8}，即 T1， T1已 在 C中。 ?closure(move(T2,b))={1,2,4,5,6,7}，即 T2， T2已在 C中 T3： ?closure(move(T3,a))={1,2,3,4,6,7,8}，即 T1。 ? closure(move(T3,b))={1,2,4,5,6,7,10},令其為 T4，在入 C中， T4未被標記 T4： ?closure(move(T4,a))={1,2,3,4,6,7,8}，即 T1。 ?closure(move(T4,b))={1,2,4,5,6,7}，即 T2 50 盛威網：專業(yè)的計算機學習網站 ? a b 0 01247 T0=01247 38 5 38 1234678 5 124567 T1=1234678 38 59 59 1245679 T2=124567 38 5 T3=1245679 38 5 10 5 10 12456710 T4=12456710 38 5 51 盛威網：專業(yè)的計算機學習網站 ?至此，算法終止共構造了 5個子集： ?T0={0,1,2,4,7} ?T1={1,2,3,4,6,7,8} ?T2={1,2,4,5,6,7} ?T3={1,2,4,5,6,7,9} ?T4={1,2,4,5,6,7,10} ?那么