【正文】 習網(wǎng)站 ?例 ?={d， ?， e， +， },則 ?上的正規(guī)式 d?(?dd ?? ? )(e(+? ??)dd? ??) 其中 d為 0~9的數(shù)字 表示的是： 無符號數(shù)的集合 20 盛威網(wǎng)：專業(yè)的計算機學習網(wǎng)站 ?若兩個正規(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 盛威網(wǎng)：專業(yè)的計算機學習網(wǎng)站 ?設 r,s,t為正規(guī)式，正規(guī)式服從的代數(shù)規(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 盛威網(wǎng)：專業(yè)的計算機學習網(wǎng)站 三 .正規(guī)文法和正規(guī)式的等價性 ?上的一個正規(guī)式 r轉換成文法 G=(VN,VT,P,S)： 令 VT＝ ∑，確定產(chǎn)生式和 VN的元素用如下辦法 ： 23 盛威網(wǎng)：專業(yè)的計算機學習網(wǎng)站 ?選擇一個非終結符 S生成產(chǎn)生式 S r，并將 S定為 G的 識別符號。若 x和 y都是正規(guī)式 ， B?VN ，則： (R1) 對形如 A xy的 正規(guī)產(chǎn)生式 ，重寫為 ： A xB， B y (R2)對形如 A x*y的 正規(guī)產(chǎn)生式 ，重寫為： A xB， A y， B xB， B y (R3)對形如 A x?y的 正規(guī)產(chǎn)生式 ，重寫為 : A x， A y 不斷應用 R做變換，直到每個產(chǎn)生式右端只含一個 VN 24 盛威網(wǎng)：專業(yè)的計算機學習網(wǎng)站 例 將 r=a(a|d)*轉換成相應的正規(guī)文法 令 S是文法的開始符號，形成 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è)的計算機學習網(wǎng)站 ： 基本上是上述過程的逆過程，最后只剩下一個開始符 號定義的正規(guī)式，其轉換規(guī)則如表 ： 26 盛威網(wǎng)：專業(yè)的計算機學習網(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 盛威網(wǎng)：專業(yè)的計算機學習網(wǎng)站 167。 有窮自動機 一 .確定的有窮自動機（ DFA）（有限自動機） ?DFA：能準確地識別正規(guī)集 ?一個確定的 DFA： M=（ K， Σ， f， S， Z） ?K是一個有窮集，它的每個元素稱為一個狀態(tài) ?Σ 是一個有窮字母表，它的每個元素稱為一個輸入符 號，所以也稱 Σ 為輸入符號字母表 28 盛威網(wǎng)：專業(yè)的計算機學習網(wǎng)站 ?f是轉換函數(shù)，是在 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 盛威網(wǎng)：專業(yè)的計算機學習網(wǎng)站 ?例 ： 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 盛威網(wǎng)：專業(yè)的計算機學習網(wǎng)站 ?一個 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 盛威網(wǎng)：專業(yè)的計算機學習網(wǎng)站 圖 狀態(tài)圖表示 ?例 DFA的狀態(tài)圖表示如圖 ： 32 盛威網(wǎng)：專業(yè)的計算機學習網(wǎng)站 ?一個 DFA可以表示成一個 矩陣表示 ，該矩陣的行表示狀 態(tài)，列表示輸入符號，矩陣元素表示相應狀態(tài)和輸入符 號將轉換成的新狀態(tài)，即 k行 a列為 f(k,a)的值。用 標明初態(tài)；否則第一行即是初態(tài)，相應終態(tài)行在表的右 端標以 1，非終態(tài)標以 0 33 盛威網(wǎng)：專業(yè)的計算機學習網(wǎng)站 圖 矩陣表示 ?例 DFA的矩陣表示如圖 ： 34 盛威網(wǎng)：專業(yè)的計算機學習網(wǎng)站 ?若 t? ∑*， f(S， t)=P，其中 S為 M的開始狀態(tài)， P ? Z， Z為終態(tài)集，則稱 t為 DFA M所接受 （識別） ?設 Q∈ K，函數(shù) f(Q,ε)=Q，一個輸入符號串 t（ t1tx， t1 ∈ ∑,tx ∈ ∑*），在 DFA M上運行的定義為： f(Q,t1tx)=f(f(Q,t1),tx) 35 盛威網(wǎng)：專業(yè)的計算機學習網(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è)的計算機學習網(wǎng)站 ?DFA M所能接受的符 號 串的全體記為 L(M) ?結論： ?上一個符 號 串集 V???是正規(guī)的，當且僅當存 在一個 ?上的確定有窮自動機 M，使得 V=L(M) ?DFA的確定性表現(xiàn)在轉換函數(shù) f:K ∑→K 是一個單值 函數(shù)，也就是說 ,對任何狀態(tài) k∈ K