第三章-有限狀態(tài)自動(dòng)機(jī)20xx-圖文ppt-資料下載頁
2025-08-15 23:52本頁面
【正文】 Pq??εCLOSURE(q0)={q0,q1,q2} εCLOSURE(q1)={q1,q2}。 )w,q(?r ???擴(kuò)充轉(zhuǎn)移函數(shù) 對于一個(gè)具有 ε 轉(zhuǎn)移的有限窮自動(dòng)機(jī)，它的擴(kuò)充轉(zhuǎn)移函數(shù) δ ’定義如下： δ ’ (q,ε)=ε CLOSURE(q), δ ’ (q,wa)=ε CLOSURE(P),P = δ(r,a) 。 其中 q∈Q, a∈∑, w∈∑ *。 注意，擴(kuò)充轉(zhuǎn)移函數(shù) δ ’已經(jīng)不是 δ 的簡單擴(kuò)充，與 δ 完全不相同。 帶空移動(dòng)的自動(dòng)機(jī)轉(zhuǎn)為不確定自動(dòng)機(jī) 0 0 q0 0 q1 q2 δ’(q0,0)=εCLOSURE(δ(δ’ (q0,ε),0)) =εCLOSURE(δ({q0,q1,q2},0)) =εCLOSURE({q0}) ={q0,q1,q2} 與 δ(q0,0)= q0不同 δ’(q0,1)=εCLOSURE(δ(δ’ (q0,ε),1)) =εCLOSURE(δ({q0,q1,q2},1)) =εCLOSURE({q1}) ={q1,q2} 0,1 0,1 q0 0 q1 q2 δ’(q0,2)=εCLOSURE(δ(δ’ (q0,ε),2)) =εCLOSURE(δ({q0,q1,q2},2)) =εCLOSURE({q2}) ={q2} 0,1 0,1,2 q0 0 q1 q2 δ’(q1,0)=εCLOSURE(δ(δ’ (q1,ε),0)) =εCLOSURE(δ({q1,q2},0)) 無定義 δ’(q1,1)=εCLOSURE(δ(δ’ (q1,ε),1)) =εCLOSURE(δ({q1,q2},1)) =εCLOSURE({q1}) ={q1,q2} δ’(q1,2)=εCLOSURE(δ(δ’ (q1,ε),2)) =εCLOSURE(δ({q1,q2},2)) =εCLOSURE({q2}) ={q2} δ’(q2,0)=εCLOSURE(δ(δ’ (q2,ε),0)) =εCLOSURE(δ({q2},0)) 無定義 δ’(q2,1)=εCLOSURE(δ(δ’ (q2,ε),1)) =εCLOSURE(δ({q2},1)) 無定義 δ’(q2,2)=εCLOSURE(δ(δ’ (q2,ε),2)) =εCLOSURE(δ({q2},2)) =εCLOSURE({q2}) ={q2} 2022/8/27 63 帶輸出的 FA ? Moore機(jī) M=(Q， ∑ ， Δ ， δ ， λ ， q0) Q、 ∑ 、 q0、 δ 的意義同 DFA。 Δ——輸出字母表 (output alphabet)。 λ ： Q?Δ 為輸出函數(shù)。對 ?q∈ Q， λ (q)=a表示 M在狀態(tài) q時(shí)輸出 a。 ? 輸入的字符同時(shí)輸出： λ ： λ (q0)=ε， λ (q1)=0， λ (q2)=1 λ (q3)=0， λ (q4)=1， λ ： λ (q0)=0|1， λ (q1)=0|1， λ (q2)=0|1 λ (q3)= ε ， λ (q4)= ε q0 S q1 q3 0 0 q2 q4 1 1 1 0 ? 例 設(shè)計(jì)一個(gè) Moore機(jī)， ∑={0， 1}，若將輸入串看成一個(gè)二進(jìn)制數(shù)，要求在讀入過程中，能輸出它已讀過子串的模 3余數(shù)。 ? 因?yàn)槟?3余數(shù)只能有 0， 1， 2三個(gè)值，因此取Δ={0， 1， 2}，并且只設(shè)三個(gè)狀態(tài) q0,q1,q2，分別對應(yīng)這三種余數(shù)。 qs S 1 0 q0 q1 1 q2 0 1 1 0 0 2022/8/27 68 ? Mealy機(jī) M=(Q， ∑ ， Δ ， δ ， λ ， q0) Δ——輸出字母表。 λ ： Q ∑ ?Δ 為輸出函數(shù)。對 ?(q，a)∈ Q ∑ ， λ (q， a)=d表示 M在狀態(tài) q讀入字符 a時(shí)輸出 d。 ? 輸入的字符同時(shí)輸出： λ ： λ (q0， 0)=0， λ (q0， 1)=1， λ (q1， 0)=0， λ (q1， 1)=1， λ (q2， 0)=0， λ (q2， 1)=1， q0 S q1 q3 0 0 q2 q4 1 1 1 0 ? 例 給出一個(gè) 0， 1串的集合 S，該集合中的串都以 00或 11結(jié)尾。要求設(shè)計(jì)一個(gè)只有兩個(gè)輸出符號（ Δ={y,n}）的 Mealy機(jī)，當(dāng)它讀過屬于集合S的串時(shí)，輸出 y，表示接受；當(dāng)它讀過不屬于集合 S的串時(shí)，輸出 n，表示不接受。 電子標(biāo)簽 文章編輯： pptnnchdfr 2022/8/27 74 ? Moore機(jī)處理該串時(shí)每經(jīng)過一個(gè)狀態(tài) ， 就輸出一個(gè)字符：輸出字符和狀態(tài)一一對應(yīng)； ? Mealy機(jī)處理該串時(shí)的每一個(gè)移動(dòng)輸出一個(gè)字符：輸出字符和移動(dòng)一一對應(yīng)。 轉(zhuǎn)為 Mealy機(jī)
法律信息相關(guān)推薦
鄂ICP備17016276號-1