【正文】 ..................................................... 12 8. 附錄 ............................................................ 13 第 1 頁，共 22 頁 ： 背景 有限自動機作為一種識別裝置，它能準確地識別正規(guī)集，即識別正規(guī)文法所定義的語言和正規(guī)式所表示的集合，引入有窮自動機這個理論，正是為詞法分析程序的自動構造尋找特殊的方法和工具。 編譯原理課程實踐報告 設計名稱： NFA轉化為 DFA的轉換算法及實現 二級學院： 數學與計算機科學學院 專 業(yè)： 計算機科學與技術 班 級： 計科本 091班 姓 名： 林玉蘭 學 號： 0904402102 指導老師： 梁德塞 日 期： 2021年 6月 摘要 確定有限自動機確定的含義是在某種狀態(tài)，面臨一個特定的符號只有一個轉換，進入唯一的一個狀態(tài)。 關鍵詞： 有限自動機；確定有限自動機（ 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)沿著某個標記為 a1a2a3? an的路徑可以到達的那些狀態(tài)。并以此為 I計算 Ia、 Ib 等，而 且在所計算出的 Ia、 Ib 等中若有新的狀態(tài)集產生，就重復以此新的集合為 I 再此計算 Ia、 Ib 等，直到在所得的 Ia、 Ib等中不再產生新的狀態(tài)集為止。經過多次試驗，在正確輸入相關數據的情況下，程序能正常運行，當錯誤操作或輸入錯誤數據時，程序將應錯誤自動關閉。 //終結符集合 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)轉換矩陣 //狀態(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(