形式語言與自動機(jī)_有窮自動機(jī)(編輯修改稿)
2025-02-14 19:55 本頁面
【文章內(nèi)容簡介】 2 NFA: DFA: {q0, q1} {q0, q2} {q0, q1, q2} {q1, q2} {q0} {q1} {q2} ? 0 1 0 1 0 1 0 1 0 1 0 1 0, 1 DFA中包含 NFA接受狀態(tài)的子集狀態(tài)設(shè)為 accepting 2022年 2月 15日星期二 南京航空航天大學(xué)計算機(jī)學(xué)院 胡軍 31 NFA → DFA: 消除無用的狀態(tài) 1 0 0, 1 q0 q1 q2 NFA: DFA: {q0, q1} {q0, q2} {q0} 0 1 0 1 0 1 {q0, q1, q2} 0 1 {q1, q2} {q1} {q2} ? 0 1 0 1 0, 1 將 DFA中不可達(dá)的狀態(tài)消除掉。 2022年 2月 15日星期二 南京航空航天大學(xué)計算機(jī)學(xué)院 胡軍 32 子集構(gòu)造法的一般步驟 NFA DFA 狀態(tài) q0, q1, …, q n ? ? ?q0}, {q1}, {q0,q1}, …, {q 0,…,q n} 每個狀態(tài)都是 NFA的一個子集 。 初始狀態(tài) q0 ?q0} 轉(zhuǎn)換 d d’ ({qi1,…,q ik}, a) = d(qi1, a) ∪ … ∪ d(qik, a) 接受狀態(tài) F ? Q F’ = {S: S 包含 F中至少一個狀態(tài) } 2022年 2月 15日星期二 南京航空航天大學(xué)計算機(jī)學(xué)院 胡軍 33 NFADFA等價性的形式化證明 ? 定理 設(shè) L是被一個非確定的有窮自動機(jī)接受的語言，則存在一個確定的有窮自動機(jī)也接受這個語言 L。 證明 設(shè) M=(Q,∑,δ,q0 , F)是一個接受 L的 NFA，現(xiàn)在構(gòu)造一個 DFA M180。=(Q180。,∑,δ180。,q0180。,F180。)，其中： ① Q180。=2Q, 即 Q的每一個子集作為 Q180。的一個狀態(tài)，若子集為{q1,q2,…,qk}，則 Q180。中狀態(tài)記為 [q1,q2,…,qk]； ② q0180。={q0}； ③ F180。 2Q:F180。的每個元素至少包含 F中的一個狀態(tài)； ④ δ180。的定義為： δ180。([q1,q2,…,qi],a)= [p1,p2,…,pj] 當(dāng)且僅當(dāng) δ（ {q1,q2,…,qi},a） = {p1,p2,…,pj} (a∈ ∑)。 ?2022年 2月 15日星期二 南京航空航天大學(xué)計算機(jī)學(xué)院 胡軍 34 NFADFA等價性的形式化證明 ? 證明 L(M180。)=L(M)=L。先證一個更一般的命題： δ180。(q0’,x)=[q1,q2,…,qk] iff δ(q0,x)={q1,q2,…,qk} （ x∈ ∑*）。 (31) 對 x的長度 ∣ x∣ 用歸納來證明 。 歸納基礎(chǔ) ∣ x∣ =0，即 x=ε。因為 δ180。(q0180。,ε)= q0180。=[q0], δ(q0,ε)={q0}。 根據(jù) δ180。的定義。所以（ 31）式成立。 歸納步驟 設(shè)對于 |x|≤m的輸入串（ 31）式成立，現(xiàn)在考慮長度為 m+1的輸入串 xa(x∈ ∑*， a∈ ∑)。因為一方面 δ180。(q0180。,xa)=δ180。(δ180。(q0180。,x),a)， （ 1） 另一方面 δ(q0,xa)=δ(δ(q0,x),a) 。 （ 2） 2022年 2月 15日星期二 南京航空航天大學(xué)計算機(jī)學(xué)院 胡軍 35 NFADFA等價性的形式化證明 ? 由歸納法假設(shè)，因為 x長度為 m，以下（ 3）式成立，即δ180。(q0180。,x)=[p1,p2,…,pj]當(dāng)且僅當(dāng) δ(q0,x)={p1,p2,…,pj}。 （ 3） 再由 δ180。的定義： δ180。([p1,p2,…,pj],a)=[r1,r2,…,rs] 當(dāng)且僅當(dāng) δ({p1,p2,…,pj},a)={r1,r2,…,rs} （ 4） 將（ 3），（ 4）代入（ 1），（ 2）兩式，即得出 δ180。(q0180。,xa)= [r1,r2,…,rs] 當(dāng)且僅當(dāng) δ(q0,xa) ={r1,r2,…,rs}。 從而（ 31）式得到證明。 有了（ 31）式之后，若 [q1,q2,…,qk]∈ F180。,則 q1,q2,…,qk 至少有一個在 F 中；反之，若 {q1,q2,…,qk}中有一個狀態(tài)在 F中，則 [q1,q2,…,qk]∈ F180。這就 是說， M和 M180。接受的語言是相同的，即 L(M180。)=L(M)=L。定理證畢。 ? 這個定理不僅證明了 NFA和 DFA兩類自動機(jī)的等價性，而且還 給出了從一 個 NFA構(gòu)造與它等價的 DFA的具體步驟，這種證明稱為構(gòu)造性的證明方法。 2022年 2月 15日星期二 南京航空航天大學(xué)計算機(jī)學(xué)院 胡軍 36 NFADFA等價構(gòu)造的例子 ? 例 設(shè) M=({q0,q1},{0,1},δ,q0,{q1})是一個 NFA，其中： δ（ q0,0） ={q0,q1}, δ（ q0,1） ={q1}, δ（ q1,0） =Φ , δ（ q1,1） ={q0,q1}。 ? 根據(jù)定理 ，我們能構(gòu)造出等價的 DFA: M180。=( Q, {0,1},δ180。,[q0], F ) 其中： Q={[q0],[q1],[q0,q1],Ф}, F={[q1],[q0,q1]}, δ180。([q0],0)=[q0,q1], δ180。([q0],1)=[q1], δ180。([q1],0)=Φ, δ180。([q1],1)=[q0,q1], δ180。([q0,q1],0)=[q0,q1], δ180。([q0,q1],1)=[q0,q1], δ180。(Φ,0)=Φ, δ180。(Φ,1)=Φ。 2022年 2月 15日星期二 南京航空航天大學(xué)計算機(jī)學(xué)院 胡軍 37 子集構(gòu)造法的實際實現(xiàn) ? 從狀態(tài) [q0]出發(fā)，通過狀態(tài)轉(zhuǎn)移函數(shù) δ180。，逐步擴(kuò)充狀態(tài)集； 每一步僅對狀態(tài)集中新增加的狀態(tài)，才寫出狀態(tài)轉(zhuǎn)移函數(shù) ；此過程一直繼續(xù)下去 ，直到不再增加新的狀態(tài)為止 ，最后就得到了 DFA。 ? 例 將例 NFA化為等價的 DFA，可按下述步驟構(gòu)造： 第一步 從 [q0]開始： δ180。([q0],0)=[q0,q3], δ180。([q0],1)=[q0,q1]。 第二步 處理兩個新狀態(tài) [q0,q3]和 [q0,q1] ： δ180。( [q0,q3],0)=[q0,q3,q4]， δ180。( [q0,q3],1)=[q0,q1]； δ180。( [q0,
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1