編譯原理課程設(shè)計(jì)--nfa轉(zhuǎn)化為dfa的轉(zhuǎn)換算法及實(shí)現(xiàn)-其他專業(yè)-預(yù)覽頁
【正文】 automata NFA, because of some state are transferred from a number of possible followup state are chosen, so a NFA symbol string recognition must be a trial process. This uncertainty to the recognition process brought about by repeated, will undoubtedly affect the efficiency of the FA. While the DFA is determined, converting NFA to DFA will greatly improve the working efficiency, thus converting NFA to DFA is its necessary. For any a nondeterministic finite automaton ( NFA ) can be an equivalent deterministic finite automaton ( DFA ), L ( N ) =L ( M ). This paper mainly introduces how to convert NFA to equivalent simplified DFA, through concrete examples, bined with graphics, a detailed description of the algorithm principle of conversion. Keywords: ： finite automata。 課程實(shí)踐的意義 通過本課程設(shè)計(jì)教學(xué)所可以使我們充分理解和掌握 NFA， DFA 以及 NFA 確定化過程的相關(guān)概念和知識，理解和掌握子集法的相關(guān)知識和應(yīng)用，編程實(shí)現(xiàn)對輸入 NFA 轉(zhuǎn)換成 DFA 輸出的功能。該 DFA 使用它的狀態(tài)去記錄在 NFA 讀入一個(gè)輸入符號后可能到達(dá)的所有狀態(tài)，也就是說，在讀入符號串 a1a2a3? an 之后，該 DFA 處在這樣一個(gè)狀態(tài)，該狀態(tài)表示這個(gè) NFA 的狀態(tài)的一個(gè) 子集 T，而 T是從 NFA 的開始狀態(tài)沿著某個(gè)標(biāo)記為 a1a2a3? an的路徑可以到達(dá)的那些狀態(tài)。 第 6 頁，共 22 頁 s 表示 NFA 的狀態(tài)， T 表示 NFA 的狀態(tài)集合， a表 示一個(gè) input symbol ε transition(ε轉(zhuǎn)換 )就是說 input symbol 為ε時(shí)的 transition(轉(zhuǎn)換 ) 操作(operation) 描述 (description) εclosure(s) 從 NFA 的狀態(tài) s出發(fā)，只通過ε transition 到達(dá)的 NFA 的狀態(tài)集合 εclosure(T) NFA的集合 T中的狀態(tài) p，只通過ε transition 到達(dá)的 NFA的狀態(tài)集合，再求這些集合的交集。并以此為 I計(jì)算 Ia、 Ib 等，而 且在所計(jì)算出的 Ia、 Ib 等中若有新的狀態(tài)集產(chǎn)生，就重復(fù)以此新的集合為 I 再此計(jì)算 Ia、 Ib 等，直到在所得的 Ia、 Ib等中不再產(chǎn)生新的狀態(tài)集為止。對于轉(zhuǎn)化后的 DFA 表示， 3個(gè)數(shù)據(jù)分別表示為起始狀態(tài)、接受字符和到達(dá)狀態(tài)，例如（ 0,1,1）表示為新狀態(tài) 0 接受字符 1 到達(dá)新字符狀態(tài) 1。經(jīng)過多次試驗(yàn)，在正確輸入相關(guān)數(shù)據(jù)的情況下，程序能正常運(yùn)行，當(dāng)錯(cuò)誤操作或輸入錯(cuò)誤數(shù)據(jù)時(shí)，程序?qū)?yīng)錯(cuò)誤自動關(guān)閉。 同時(shí)我也發(fā)現(xiàn)自己對于有限自動機(jī)的知識掌握得還不是很多，在這次課程實(shí)踐中，我懂得了怎樣去和別人交流，更好地掌握和熟練了所學(xué)的知識。 //終結(jié)符集合 int N。 }。 void kong(int a) { int i。 39。 for(j=0。i++) if((a[i])(a[i+1])) { b=a[i]。he,edge b[]) { int k。 eclouse(b[k].last[0],he,b)。 l=[m].length()。jN。 for(i=0。j++) if((CHANGE[m]==b[j].change[0])amp。 cout I 。I39。ih。 m=t[i].()。 m=t[i].jihe[j].length()。 int i,j,k,m,n,h,x,y,len。 for(i=0。 cinb[i].changeb[i].last。j++) coutb[j].firstb[j].changeb[j].lastendl。 if((b[i].last)()) NODE+=b[i].last。 } len=()。i()。 chan *t=new chan[MAXS]。 //求 eclouse //coutt[0].ltabendl。jt[i].()。 //求 eclouse for(k=0。 //求 move(I,a) //coutt[i].jihe[k]endl。 //求 eclouse } for(j=0。kh。amp。 //輸出狀態(tài)轉(zhuǎn)換矩陣 //狀態(tài)重新命名 string *d=new string[h]。ih。A39。{39。j++) if((endnode[j])()) d[1]=ednode+=t[i].ltab。mlen。i++) if((NODE[i])()) d[0]+=NODE[i]。 //輸出 DFA cout其中終態(tài)為： endnodeendl。 for(i=0。klen。jd[i].length()。 else x=n。 d[i].erase(j,1)。 //跳出 n } }//n }//j if(flag) { m++。 }//k }//i coutendl集合劃分： 。 coutendl。 for(i=0。+i。im。jh。 else if(d[n].find(t[j].jihe[k])d[n].length()) { md[i].jihe[k]=md[n].ltab。 for(i=0。j++) if(d[i].find(endnode[j])d[i].length()amp。 coutendl最小化 DFA如下：
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1