編譯原理課程設(shè)計(jì)--nfa轉(zhuǎn)化為dfa的轉(zhuǎn)換算法及實(shí)現(xiàn)-其他專(zhuān)業(yè)-免費(fèi)閱讀
【正文】 coutendl最小化 DFA如下： endl。 for(i=0。jh。+i。 coutendl。 //跳出 n } }//n }//j if(flag) { m++。 else x=n。klen。 //輸出 DFA cout其中終態(tài)為： endnodeendl。mlen。{39。ih。amp。 //求 eclouse } for(j=0。 //求 eclouse for(k=0。 //求 eclouse //coutt[0].ltabendl。i()。 if((b[i].last)()) NODE+=b[i].last。 cinb[i].changeb[i].last。 int i,j,k,m,n,h,x,y,len。 m=t[i].()。I39。j++) if((CHANGE[m]==b[j].change[0])amp。jN。 eclouse(b[k].last[0],he,b)。i++) if((a[i])(a[i+1])) { b=a[i]。 39。 }。 同時(shí)我也發(fā)現(xiàn)自己對(duì)于有限自動(dòng)機(jī)的知識(shí)掌握得還不是很多，在這次課程實(shí)踐中，我懂得了怎樣去和別人交流，更好地掌握和熟練了所學(xué)的知識(shí)。對(duì)于轉(zhuǎn)化后的 DFA 表示， 3個(gè)數(shù)據(jù)分別表示為起始狀態(tài)、接受字符和到達(dá)狀態(tài)，例如（ 0,1,1）表示為新?tīng)顟B(tài) 0 接受字符 1 到達(dá)新字符狀態(tài) 1。 第 6 頁(yè)，共 22 頁(yè) s 表示 NFA 的狀態(tài)， T 表示 NFA 的狀態(tài)集合， a表 示一個(gè) input symbol ε transition(ε轉(zhuǎn)換 )就是說(shuō) input symbol 為ε時(shí)的 transition(轉(zhuǎn)換 ) 操作(operation) 描述 (description) εclosure(s) 從 NFA 的狀態(tài) s出發(fā)，只通過(guò)ε transition 到達(dá)的 NFA 的狀態(tài)集合 εclosure(T) NFA的集合 T中的狀態(tài) p，只通過(guò)ε transition 到達(dá)的 NFA的狀態(tài)集合，再求這些集合的交集。 課程實(shí)踐的意義 通過(guò)本課程設(shè)計(jì)教學(xué)所可以使我們充分理解和掌握 NFA， DFA 以及 NFA 確定化過(guò)程的相關(guān)概念和知識(shí)，理解和掌握子集法的相關(guān)知識(shí)和應(yīng)用，編程實(shí)現(xiàn)對(duì)輸入 NFA 轉(zhuǎn)換成 DFA 輸出的功能。這種不確定性給識(shí)別過(guò)程帶來(lái)的反復(fù)，無(wú)疑會(huì)影響到 FA 的工作效率。而 DFA 則是確定的 ,將 NFA轉(zhuǎn)化為 DFA將大大提高工作效率 ,因此將 NFA轉(zhuǎn)化為 DFA是有其一定必要的。 第 2 頁(yè)，共 22 頁(yè) 和 DFA 的概念 不確定有限自動(dòng)機(jī) NFA NFA(nondeterministic finitestate automata)即非確定有限自動(dòng)機(jī) , 一個(gè)非確定的有限自動(dòng)機(jī) NFA M’是一個(gè)五元式 : NFA M’ =(S, Σ∪ {ε }, δ , S0, F) 其中 S— 有限狀態(tài)集，Σ∪ {ε }— 輸入符號(hào)加上ε ,即自動(dòng)機(jī)的每個(gè)結(jié)點(diǎn)所射出的弧可以是Σ中一個(gè)字符或是ε . S0— 初態(tài)集 F— 終態(tài)集 δ — 轉(zhuǎn)換函數(shù) SΣ ∪ {ε } → 2S (2S S的冪集 — S的子集構(gòu)成的集合） 例 1： NFA M=({S,P,Z},{0,1},f,{s,p},{z}) 其中 f(s,0)={p} f(z,0)={p} f(p,1)={z} f(z,1)={p} f(s,1)={s,z} ① NFA的狀態(tài)圖表示如下： 第 3 頁(yè)，共 22 頁(yè) ② NFA矩陣表示： 狀態(tài) 字符 0 1 S P S,Z 0 P {} Z 0 Z P P 1 確定有限自動(dòng)機(jī) DFA DFA(deterministic finitestate automata)即確定有限自動(dòng)機(jī)，一個(gè)確定的有限自動(dòng)機(jī) DFA M 是一個(gè)五元式 : M=(S, Σ，δ , S0, Z) 其中 : S — 有限狀態(tài)集 Σ — 輸入字母表 δ — 映射函數(shù) (也稱(chēng)狀態(tài)轉(zhuǎn)換函數(shù) ) SΣ→ S S P Z 1 0,1 1 0 1 第 4 頁(yè)，共 22 頁(yè) δ (s,a)=S’ , S, S’ ∈ S, a∈Σ S0 — 初始狀態(tài) S0 ∈ S Z— 終止?fàn)顟B(tài)集 Z?S 例 2： DFA M=({S,U,V,Q},{a,b},f,s,{Q}) 其中 f的定義為： f(S,a)=U f(S,b)=V f(U,a)=Q f(U,b)=V f(V,a)=U f(V,b)=Q f(Q,a)=Q f(Q,b)=Q ① DFA 的狀態(tài)圖表示： 假如 DFA M 含有 m 個(gè)狀態(tài)， n個(gè)輸入符，那么這個(gè)狀態(tài)含有 m個(gè)節(jié)點(diǎn)，每個(gè)節(jié)點(diǎn)最多有 n 個(gè)弧射出，整個(gè)圖整個(gè)圖含有唯一一個(gè)初態(tài)結(jié)點(diǎn)和若干個(gè)終態(tài)結(jié)點(diǎn)，初態(tài)結(jié)點(diǎn)冠以雙箭頭“ =”或標(biāo)以“ ”，終態(tài)結(jié)點(diǎn)用雙圈表示或標(biāo)以“ +”，若 f(ki ,a)=kj，則從狀態(tài)結(jié)點(diǎn) ki 到狀結(jié)點(diǎn) kj畫(huà)標(biāo)記為 a 的弧： ② DFA 矩陣表示： 一個(gè) DFA 還可以用一個(gè)矩陣表示，該矩陣的行表示狀態(tài)，列表示輸入字符，矩陣元素表示相應(yīng)狀態(tài)行和輸入字符列下的新?tīng)顟B(tài)，即 k行 a列為 f(k,a)的值。用數(shù)學(xué)表達(dá)就是 {p|p 屬于 εclosure(t) , t屬于 T} move(T,a) NFA的集合，這個(gè)集合在 input symbol 為 a，狀態(tài)為 T中任意狀態(tài)情況下，通過(guò)一個(gè)轉(zhuǎn)換得到的集合 例如： 對(duì)于以下?tīng)顟B(tài)圖中： ε closure({0})={0,1,2,4,7} 在這里設(shè) I={0,1,2,4,7}，則 因?yàn)橛?move(I,a)={3,8}=J,所以 Ia= ε closure(J)= ε closure({3,8})={1,2,3,4,6,7,8} 0 1 2 3 5 7 6 8 9 4 9 100 ε ε
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1