編譯原理課程設(shè)計--nfa轉(zhuǎn)化為dfa的轉(zhuǎn)換算法及實現(xiàn)-其他專業(yè)-閱讀頁
2025-02-08 02:55本頁面
【正文】 有限自動機 M為例。并以此為 I計算 Ia、 Ib 等，而 且在所計算出的 Ia、 Ib 等中若有新的狀態(tài)集產(chǎn)生，就重復(fù)以此新的集合為 I 再此計算 Ia、 Ib 等，直到在所得的 Ia、 Ib等中不再產(chǎn)生新的狀態(tài)集為止。 NFA的確定化是編譯過程中一個重要的部分，由于本程序的輸入很多，而且有多種格式的輸入，所以輸入時必須非常小心細致。對于轉(zhuǎn)化后的 DFA 表示， 3個數(shù)據(jù)分別表示為起始狀態(tài)、接受字符和到達狀態(tài)，例如（ 0,1,1）表示為新狀態(tài) 0 接受字符 1 到達新字符狀態(tài) 1。 ： 通過這次課程實踐設(shè)計，讓我對課堂上老師所講到的不確定和確定有限自動機有了更深的理解，理解了它們的構(gòu)造和怎樣相互轉(zhuǎn)化。經(jīng)過多次試驗，在正確輸入相關(guān)數(shù)據(jù)的情況下，程序能正常運行，當錯誤操作或輸入錯誤數(shù)據(jù)時，程序?qū)?yīng)錯誤自動關(guān)閉。書本只能教給我們基礎(chǔ)知識 ,要怎樣運用 ,將那些知識真正吸收 ,轉(zhuǎn)化為自己的智慧 ,只有通過實 踐才能達到。 同時我也發(fā)現(xiàn)自己對于有限自動機的知識掌握得還不是很多，在這次課程實踐中，我懂得了怎樣去和別人交流，更好地掌握和熟練了所學(xué)的知識。 string NODE。 //終結(jié)符集合 int N。 string change。 }。 string jihe[MAXS]。 void kong(int a) { int i。ia。 39。a) { 第 14 頁，共 22 頁 int i,j。 for(j=0。j++) for(i=0。i++) if((a[i])(a[i+1])) { b=a[i]。 a[i+1]=b。he,edge b[]) { int k。kN。 eclouse(b[k].last[0],he,b)。he,int m,edge b[]) { int i,j,k,l。 l=[m].length()。ik。jN。amp。 for(i=0。i++) for(j=0。j++) if((CHANGE[m]==b[j].change[0])amp。([m][i]==b[j].first[0])) if([m].find(b[j].last[0])[m].length()) [m]+=b[j].last[0]。 cout I 。ilen。I39。 coutendlendl。ih。 39。 m=t[i].()。jlen。 m=t[i].jihe[j].length()。 } coutendl。 int i,j,k,m,n,h,x,y,len。 string jh[MAXS],endnode,ednode,sta。 for(i=0。i++) { cinb[i].first。 cinb[i].changeb[i].last。 /*for(j=0。j++) coutb[j].firstb[j].changeb[j].lastendl。iN。 if((b[i].last)()) NODE+=b[i].last。amp。 } len=()。 第 17 頁，共 22 頁 cinendnode。i()。 return。 chan *t=new chan[MAXS]。 h=1。 //求 eclouse //coutt[0].ltabendl。ih。jt[i].()。mlen。 //求 eclouse for(k=0。k++) { //coutt[i].jihe[k]。 //求 move(I,a) //coutt[i].jihe[k]endl。jt[i].jihe[k].length()。 //求 eclouse } for(j=0。j++) { paixu(t[i].jihe[j])。kh。 if(flag) break。amp。 } } coutendl狀態(tài)轉(zhuǎn)換矩陣如下： endl。 //輸出狀態(tài)轉(zhuǎn)換矩陣 //狀態(tài)重新命名 string *d=new string[h]。 coutendl重命名： endl。ih。 t[i].()。A39。 NODE+=t[i].ltab。{39。 for(j=0。j++) if((endnode[j])()) d[1]=ednode+=t[i].ltab。kh。mlen。 } 第 19 頁，共 22 頁 for(i=0。i++) if((NODE[i])()) d[0]+=NODE[i]。 coutendlDFA 如下： endl。 //輸出 DFA cout其中終態(tài)為： endnodeendl。 ()。 for(i=0。i++) { //coutd[i]=d[i]endl。klen。 y=m。jd[i].length()。ny。 else x=n。 } else if(sta[0]!=x+48) { d[m]+=d[i][j]。 d[i].erase(j,1)。 j。 //跳出 n } }//n }//j if(flag) { m++。 } //coutsta=staendl。 }//k }//i coutendl集合劃分： 。im。 coutendl。 ()。 for(i=0。i++) { md[i].ltab=39。+i。 cout{d[i]}=md[i].ltabendl。im。klen。jh。nm。 else if(d[n].find(t[j].jihe[k])d[n].length()) { md[i].jihe[k]=md[n].ltab。 } } break。 for(i=0。i++) for(j=0。j++) if(d[i].find(endnode[j])d[i].length()amp。(md[i].ltab)) ednode+=md[i].ltab。 coutendl最小化 DFA如下： endl。 cout其中終態(tài)為： endnode
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1