編譯原理課程設(shè)計--nfa轉(zhuǎn)化為dfa的轉(zhuǎn)換算法及實現(xiàn)-其他專業(yè)(存儲版)
【正文】 第 7 頁，共 22 頁 子集構(gòu)造法 確定化每個 多重轉(zhuǎn)移，即拆分多值函數(shù)為單位函數(shù) ,具體轉(zhuǎn)換，采用子集構(gòu)造法。運行結(jié)果因為轉(zhuǎn)換字符輸入順序的不同，得出的結(jié)果有可能與筆算得出的順序有所不同，但是結(jié)果依然是正確。 考 文 獻 （ 1）楊路明、郭浩志 .C 語言程序設(shè)計教程 .2021 年 12 月第 1版 . 北京 :北京郵電大學(xué)出版社 .2021 （ 2）陳火旺 .程序設(shè)計語言編譯原理 .2021 年 1 月第 3 版 . 北京 :國防工業(yè)出版社 . （ 3） 嚴蔚敏、吳偉民 .數(shù) 據(jù)結(jié)構(gòu)（ C 語言版） .1997 年 4 月第 1版 .北京 :清華大學(xué)出版社 .2021 （ 4） 王曉東編著 .計算機算法設(shè)計與分析 .電子工業(yè)出版社 .2021 第 13 頁，共 22 頁 8. 附錄 NFA 轉(zhuǎn)換為 DFA 采用 C++編程實現(xiàn)代碼如下 includeiostream includestring define MAXS 100 using namespace std。 struct chan{ string ltab。 } //排序 void paixu(string amp。 a[i]=a[i+1]。 } } } void move(chan amp。j++) if((CHANGE[m]==b[j].change[0])amp。amp。CHANGE[i] 。 for(j=0。 bool flag。 } N=i。 if(((b[i].change)())amp。i++) if((endnode[i])()) { cout所輸終態(tài)不在集合中，錯誤！ endl。 for(i=0。klen。jlen。t[i].jihe[j].length()) t[h++].ltab=t[i].jihe[j]。i++) { sta=t[i].ltab。sta}=t[i].ltabendl。m++) if(sta==t[k].jihe[m]) t[k].jihe[m]=t[i].ltab。 //DFA 最小化 m=2。k++) { //coutICHANGE[k]endl。 第 20 頁，共 22 頁 if(!()) { sta+=x+48。 flag=0。 第 21 頁，共 22 頁 //狀態(tài)重新命名 chan *md=new chan[m]。 NODE+=md[i].ltab。j++) { if(d[i][0]==t[j].ltab[0]) { for(n=0。im。 outputfa(len,m,md)。 endnode=ednode。 } } 第 22 頁，共 22 頁 ()。k++) for(j=0。A39。i++) cout{d[i]} 。 } break。n++) { if(d[n].find(t[(d[i][j])].jihe[k])d[n].length()||t[d(d[i][j])].jihe[k].length()==0) { if(t[(d[i][j])].jihe[k].length()==0) x=m。 for(k=0。 outputfa(len,h,t)。k++) for(m=0。 cout39。 for(i=0。 } if(!flagamp。j++) eclouse(t[i].jihe[k][j],t[i].jihe[k],b)。m++) eclouse(t[i].ltab[j],t[i].jihe[m],b)。 eclouse(b[0].first[0],t[0].ltab,b)。 for(i=0。i++) { if((b[i].first)()) NODE+=b[i].first。 if(b[i].first==) break。 第 16 頁，共 22 頁 } } void main() { edge *b=new edge[MAXS]。t[i].ltab。i++) cout39。jN。i++) for(j=0。k++) { if(c==b[k].first[0]) if(b[k].change==*) { if((b[k].last)()) he+=b[k].last。i()。i++) cout39。 string last。編譯原理是一門實用性很強，對我們的專業(yè)很有幫助的科目 ,我將會繼續(xù)努力 ,不斷增加自己的知識面 ,把編譯原理學(xué)習的更好。對于狀態(tài)轉(zhuǎn)換矩陣的表示，冒號前的是新狀態(tài)名，冒號后的是舊狀態(tài)名?？梢詫懽鳎? Ia= ε closure(J)， J=move(I,a),其中， J是從 I 中任一狀態(tài)出發(fā)經(jīng)過一條 a 弧到達的狀態(tài)集合，記為 move(I,a)。 （ 2）掌握 NFA 確定化的過程。 在非確定的有限自動機 NFA 中 ,由于某些狀態(tài)的轉(zhuǎn)移需從若干個可能的后續(xù)狀態(tài)中進行選擇，故一個 NFA 對符號串的識別就必然是一個試探的過程。 對于任意的一個不確定有限自動機（ NFA）都會存在一個等價的確定的有限自動機（ DFA），即 L(N)=L(M)。用雙箭頭 =標明初態(tài)；否則第一行即是初態(tài)，相應(yīng)終態(tài)行在表的右端標以 1，非終態(tài)標以 0. U S V Q a b a a a,b b b 第 5 頁，共 22 頁 狀態(tài) 字符 a b S U V 0 U Q V 0 V U Q 0 Q Q Q 1 3．從 NDF 到 DFA 的等價變化步驟 事 實已經(jīng)證明了不管是非確定的有限自動機 M 還是具有ε 轉(zhuǎn)移的非確定的有限自動機，都可以找到一個與之等價的確定有限自動機，使得 L（ M） =L（ M’）。 以下面的基于字母表 Σ ={a,b}上的具有ε 轉(zhuǎn)移的非確定有限自動機 M為例。 ： 通過這次課程實踐設(shè)計，讓我對課堂上老師所講到的不確定和確定有限自動機有了更深的理解，理解了它們的構(gòu)造和怎樣相互轉(zhuǎn)化。 string NODE。 string jihe[MAXS]。a) { 第 1
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1