編譯原理課程設(shè)計(jì)--nfa轉(zhuǎn)化為dfa的轉(zhuǎn)換算法及實(shí)現(xiàn)-其他專業(yè)(存儲(chǔ)版)
【正文】 第 7 頁，共 22 頁 子集構(gòu)造法 確定化每個(gè) 多重轉(zhuǎn)移，即拆分多值函數(shù)為單位函數(shù) ,具體轉(zhuǎn)換，采用子集構(gòu)造法。運(yùn)行結(jié)果因?yàn)檗D(zhuǎn)換字符輸入順序的不同，得出的結(jié)果有可能與筆算得出的順序有所不同，但是結(jié)果依然是正確。 考 文 獻(xiàn) （ 1）楊路明、郭浩志 .C 語言程序設(shè)計(jì)教程 .2021 年 12 月第 1版 . 北京 :北京郵電大學(xué)出版社 .2021 （ 2）陳火旺 .程序設(shè)計(jì)語言編譯原理 .2021 年 1 月第 3 版 . 北京 :國防工業(yè)出版社 . （ 3） 嚴(yán)蔚敏、吳偉民 .數(shù) 據(jù)結(jié)構(gòu)（ C 語言版） .1997 年 4 月第 1版 .北京 :清華大學(xué)出版社 .2021 （ 4） 王曉東編著 .計(jì)算機(jī)算法設(shè)計(jì)與分析 .電子工業(yè)出版社 .2021 第 13 頁，共 22 頁 8. 附錄 NFA 轉(zhuǎn)換為 DFA 采用 C++編程實(shí)現(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)不在集合中，錯(cuò)誤！ 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。編譯原理是一門實(shí)用性很強(qiáng)，對我們的專業(yè)很有幫助的科目 ,我將會(huì)繼續(xù)努力 ,不斷增加自己的知識(shí)面 ,把編譯原理學(xué)習(xí)的更好。對于狀態(tài)轉(zhuǎn)換矩陣的表示，冒號(hào)前的是新狀態(tài)名，冒號(hào)后的是舊狀態(tài)名?？梢詫懽鳎? Ia= ε closure(J)， J=move(I,a),其中， J是從 I 中任一狀態(tài)出發(fā)經(jīng)過一條 a 弧到達(dá)的狀態(tài)集合，記為 move(I,a)。 （ 2）掌握 NFA 確定化的過程。 在非確定的有限自動(dòng)機(jī) NFA 中 ,由于某些狀態(tài)的轉(zhuǎn)移需從若干個(gè)可能的后續(xù)狀態(tài)中進(jìn)行選擇，故一個(gè) NFA 對符號(hào)串的識(shí)別就必然是一個(gè)試探的過程。 對于任意的一個(gè)不確定有限自動(dòng)機(jī)（ NFA）都會(huì)存在一個(gè)等價(jià)的確定的有限自動(dòng)機(jī)（ DFA），即 L(N)=L(M)。用雙箭頭 =標(biāo)明初態(tài)；否則第一行即是初態(tài)，相應(yīng)終態(tài)行在表的右端標(biāo)以 1，非終態(tài)標(biāo)以 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 的等價(jià)變化步驟 事 實(shí)已經(jīng)證明了不管是非確定的有限自動(dòng)機(jī) M 還是具有ε 轉(zhuǎn)移的非確定的有限自動(dòng)機(jī)，都可以找到一個(gè)與之等價(jià)的確定有限自動(dòng)機(jī)，使得 L（ M） =L（ M’）。 以下面的基于字母表 Σ ={a,b}上的具有ε 轉(zhuǎn)移的非確定有限自動(dòng)機(jī) M為例。 ： 通過這次課程實(shí)踐設(shè)計(jì)，讓我對課堂上老師所講到的不確定和確定有限自動(dòng)機(jī)有了更深的理解，理解了它們的構(gòu)造和怎樣相互轉(zhuǎn)化。 string NODE。 string jihe[MAXS]。a) { 第 1
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1