【正文】 的 b組成的串 } 19 盛威網：專業(yè)的計算機學習網站 ?例 ?={d， ?， e， +， },則 ?上的正規(guī)式 d?(?dd ?? ? )(e(+? ??)dd? ??) 其中 d為 0~9的數字 表示的是： 無符號數的集合 20 盛威網：專業(yè)的計算機學習網站 ?若兩個正規(guī)式 e1和 e2所表示的正規(guī)集相同 ,則說 e1和 e2等價 ,寫 作 e1=e2 ?例如： e1= (a?b)， e2 = b?a ?又如： e1= b(ab)? , e2 =(ba)?b e1= (a?b)? , e2 =(a??b?)? 21 盛威網：專業(yè)的計算機學習網站 ?設 r,s,t為正規(guī)式，正規(guī)式服從的代數規(guī)律有： ?r?s=s?r “或”服從交換律 ?r?(s?t)=(r?s)?t “或”的可結合律 ?(rs)t=r(st) “連接”的可結合律 ?r(s?t)=rs?rt (s?t)r=sr?tr 分配律 ??r=r r?=r ?是“連接”的恒等元素（零一律） ?r?r=r r?=??r?rr?… “或”的抽取律 22 盛威網：專業(yè)的計算機學習網站 三 .正規(guī)文法和正規(guī)式的等價性 ?上的一個正規(guī)式 r轉換成文法 G=(VN,VT,P,S)： 令 VT＝ ∑，確定產生式和 VN的元素用如下辦法 ： 23 盛威網：專業(yè)的計算機學習網站 ?選擇一個非終結符 S生成產生式 S r，并將 S定為 G的 識別符號。 有窮自動機 一 .確定的有窮自動機（ DFA）（有限自動機） ?DFA：能準確地識別正規(guī)集 ?一個確定的 DFA： M=（ K， Σ， f， S， Z） ?K是一個有窮集，它的每個元素稱為一個狀態(tài) ?Σ 是一個有窮字母表，它的每個元素稱為一個輸入符 號，所以也稱 Σ 為輸入符號字母表 28 盛威網：專業(yè)的計算機學習網站 ?f是轉換函數，是在 K Σ→K 上的映射，即，如 f（ ki， a） =kj，（ ki∈ K， kj∈ K） 就意味著，當前狀 態(tài)為 ki，輸入符為 a時，將轉換為下一個狀態(tài) kj，我們 把 kj稱作 ki的一個后繼狀態(tài) ?S∈ K是唯一的一個初態(tài) ?Z? K是一個終態(tài)集，終態(tài)也稱可接受狀態(tài)或結束狀態(tài) 29 盛威網：專業(yè)的計算機學習網站 ?例 ： DFA M=（ {S， U,V， Q}， {a， b}， f， S， {Q}） 其中 f定義為： ?f（ S， a） =U f（ V， a） =U ?f（ S， b） =V f（ v， b） =Q ?f（ U， a） =Q f（ Q， a） =Q ?f（ U， b） =V f（ Q， b） =Q 30 盛威網：專業(yè)的計算機學習網站 ?一個 DFA可以表示成一個 狀態(tài)圖 （狀態(tài)轉換圖） ?假定 DFA M含有 m個狀態(tài)， n個輸入符號，那么這個 狀態(tài)圖含有 m個結點，每個結點最多有 n個弧射出，整 個圖含有唯一一個初態(tài)結點 ( 、－ )和若干個終態(tài)結 點 (雙圈、 +)，若 f(ki,a)=kj，則從狀態(tài)結點 ki到狀態(tài)結點 kj畫標記為 a的弧 31 盛威網：專業(yè)的計算機學習網站 圖 狀態(tài)圖表示 ?例 DFA的狀態(tài)圖表示如圖 ： 32 盛威網：專業(yè)的計算機學習網站 ?一個 DFA可以表示成一個 矩陣表示 ，該矩陣的行表示狀 態(tài)，列表示輸入符號，矩陣元素表示相應狀態(tài)和輸入符 號將轉換成的新狀態(tài)，即 k行 a列為 f(k,a)的值。 狀態(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的一些子集組成。并且約定，狀態(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。令 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中。 ?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(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} ?T