編譯原理-第6講(第四章)(編輯修改稿)
2024-09-01 20:28 本頁(yè)面
【文章內(nèi)容簡(jiǎn)介】 另一種定義 ∑ *上的符號(hào)串 t被 DFA M接受 符號(hào)串 被 DFA M接受證明 b S U V Q a b b a , b a a 例 ： 證明 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)。 得證。 與第一個(gè)方法本質(zhì)一樣，只不過(guò)這個(gè)方法更適合書寫。 結(jié)論： DFA M所能接受的符號(hào)串的全體記為 L(M) 結(jié)論： ?上一個(gè)符 號(hào) 串集 V???是正規(guī)的，當(dāng)且僅當(dāng)存在一個(gè) ?上的確定有窮自動(dòng)機(jī) M， 使得V=L(M) 另一個(gè) DFA的例子 Σ = {digit,not digit} DFA的程序模擬 設(shè)置為初試狀態(tài)，此處的 K和上面五元組里的 K不是一樣的含義 取第一個(gè)字符 如果不是子串尾部 依據(jù)轉(zhuǎn)換函數(shù)，進(jìn)入下一個(gè)狀態(tài) 取下一個(gè)字符 已知 DFA，寫一個(gè)識(shí)別程序很簡(jiǎn)單的，主要工作是把轉(zhuǎn)換函數(shù)保存起來(lái) DFA M =（ K， Σ， f， S， Z） 的行為的模擬程序 K:=S； c:=getchar。 while ceof do { K:=f(K,c)。 c:=getchar。 }。 if K is in Z then return (‘ye
畢業(yè)設(shè)計(jì)相關(guān)推薦
鄂ICP備17016276號(hào)-1