【正文】 ..................................................... 12 8. 附錄 ............................................................ 13 第 1 頁，共 22 頁 ： 背景 有限自動機作為一種識別裝置，它能準確地識別正規(guī)集，即識別正規(guī)文法所定義的語言和正規(guī)式所表示的集合，引入有窮自動機這個理論，正是為詞法分析程序的自動構(gòu)造尋找特殊的方法和工具。 編譯原理課程實踐報告 設(shè)計名稱： NFA轉(zhuǎn)化為 DFA的轉(zhuǎn)換算法及實現(xiàn) 二級學(xué)院： 數(shù)學(xué)與計算機科學(xué)學(xué)院 專 業(yè)： 計算機科學(xué)與技術(shù) 班 級： 計科本 091班 姓 名： 林玉蘭 學(xué) 號： 0904402102 指導(dǎo)老師： 梁德塞 日 期： 2021年 6月 摘要 確定有限自動機確定的含義是在某種狀態(tài)，面臨一個特定的符號只有一個轉(zhuǎn)換，進入唯一的一個狀態(tài)。 關(guān)鍵詞： 有限自動機；確定有限自動機（ DFA），不確定有限自動機（ NFA） Abstract Finite automata is determinate and indeterminate two class. Determine the meaning is in a certain state, faces a particular symbol only one conversion, enter only one state. Not deterministic finite automata is the opposite, in a certain state, faces a particular symbol is the presence of more than one conversion, that is to be allowed to enter a state set. Non deterministic finite state 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。該 DFA 使用它的狀態(tài)去記錄在 NFA 讀入一個輸入符號后可能到達的所有狀態(tài)，也就是說，在讀入符號串 a1a2a3? an 之后，該 DFA 處在這樣一個狀態(tài)，該狀態(tài)表示這個 NFA 的狀態(tài)的一個 子集 T，而 T是從 NFA 的開始狀態(tài)沿著某個標(biāo)記為 a1a2a3? an的路徑可以到達的那些狀態(tài)。并以此為 I計算 Ia、 Ib 等，而 且在所計算出的 Ia、 Ib 等中若有新的狀態(tài)集產(chǎn)生，就重復(fù)以此新的集合為 I 再此計算 Ia、 Ib 等，直到在所得的 Ia、 Ib等中不再產(chǎn)生新的狀態(tài)集為止。經(jīng)過多次試驗，在正確輸入相關(guān)數(shù)據(jù)的情況下，程序能正常運行，當(dāng)錯誤操作或輸入錯誤數(shù)據(jù)時，程序?qū)?yīng)錯誤自動關(guān)閉。 //終結(jié)符集合 int N。 void kong(int a) { int i。 for(j=0。he,edge b[]) { int k。 l=[m].length()。 for(i=0。 cout I 。ih。 m=t[i].jihe[j].length()。 for(i=0。j++) coutb[j].firstb[j].changeb[j].lastendl。 } len=()。 chan *t=new chan[MAXS]。jt[i].()。 //求 move(I,a) //coutt[i].jihe[k]endl。kh。 //輸出狀態(tài)轉(zhuǎn)換矩陣 //狀態(tài)重新命名 string *d=new string[h]。A39。j++) if((endnode[j])()) d[1]=ednode+=t[i].ltab。i++) if((NODE[i])()) d[0]+=NODE[i]。 for(i=0。jd[i].length()。 d[i].erase(j,1)。 }//k }//i coutendl集合劃分： 。 for(i=0。im。 else if(d[n].find(t[j].jihe[k])d[n].length()) { md[i].jihe[k]=md[n].ltab。j++) if(d[i].find(endnode[j])d[i].length(