編譯原理課程設(shè)計--nfa轉(zhuǎn)化為dfa的轉(zhuǎn)換算法及實現(xiàn)-其他專業(yè)-資料下載頁
2025-01-19 02:55本頁面
【導(dǎo)讀】換，進(jìn)入唯一的一個狀態(tài)。不確定的有限自動機(jī)則相反，在某種狀態(tài)下，面臨一。個特定的符號是存在不止一個轉(zhuǎn)換，即是可以允許進(jìn)入一個狀態(tài)集合。狀態(tài)中進(jìn)行選擇，故一個NFA對符號串的識別就必然是一個試探的過程。確定性給識別過程帶來的反復(fù)，無疑會影響到FA的工作效率。本文主要是介紹如何將NFA轉(zhuǎn)換為與之等價的簡?；腄FA，通過具體實例，結(jié)合圖形，詳細(xì)說明轉(zhuǎn)換的算法原理。
【正文】 for(i=0。ih。i++) { for(j=0。jt[i].()。j++) for(m=0。mlen。m++) eclouse(t[i].ltab[j],t[i].jihe[m],b)。 //求 eclouse for(k=0。klen。k++) { //coutt[i].jihe[k]。 move(t[i],k,b)。 //求 move(I,a) //coutt[i].jihe[k]endl。 for(j=0。jt[i].jihe[k].length()。j++) eclouse(t[i].jihe[k][j],t[i].jihe[k],b)。 //求 eclouse } for(j=0。jlen。j++) { paixu(t[i].jihe[j])。 //對集合排序以便比較 for(k=0。kh。k++) 第 18 頁，共 22 頁 { flag=operator==(t[k].ltab,t[i].jihe[j])。 if(flag) break。 } if(!flagamp。amp。t[i].jihe[j].length()) t[h++].ltab=t[i].jihe[j]。 } } coutendl狀態(tài)轉(zhuǎn)換矩陣如下： endl。 outputfa(len,h,t)。 //輸出狀態(tài)轉(zhuǎn)換矩陣 //狀態(tài)重新命名 string *d=new string[h]。 ()。 coutendl重命名： endl。 for(i=0。ih。i++) { sta=t[i].ltab。 t[i].()。 t[i].ltab=39。A39。+i。 NODE+=t[i].ltab。 cout39。{39。sta}=t[i].ltabendl。 for(j=0。j()。j++) if((endnode[j])()) d[1]=ednode+=t[i].ltab。 for(k=0。kh。k++) for(m=0。mlen。m++) if(sta==t[k].jihe[m]) t[k].jihe[m]=t[i].ltab。 } 第 19 頁，共 22 頁 for(i=0。i()。i++) if((NODE[i])()) d[0]+=NODE[i]。 endnode=ednode。 coutendlDFA 如下： endl。 outputfa(len,h,t)。 //輸出 DFA cout其中終態(tài)為： endnodeendl。 //DFA 最小化 m=2。 ()。 flag=0。 for(i=0。im。i++) { //coutd[i]=d[i]endl。 for(k=0。klen。k++) { //coutICHANGE[k]endl。 y=m。 for(j=0。jd[i].length()。j++) { for(n=0。ny。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。 else x=n。 第 20 頁，共 22 頁 if(!()) { sta+=x+48。 } else if(sta[0]!=x+48) { d[m]+=d[i][j]。 flag=1。 d[i].erase(j,1)。 //coutd[i]endl。 j。 } break。 //跳出 n } }//n }//j if(flag) { m++。 flag=0。 } //coutsta=staendl。 ()。 }//k }//i coutendl集合劃分： 。 for(i=0。im。i++) cout{d[i]} 。 coutendl。 第 21 頁，共 22 頁 //狀態(tài)重新命名 chan *md=new chan[m]。 ()。 coutendl重命名： endl。 for(i=0。im。i++) { md[i].ltab=39。A39。+i。 NODE+=md[i].ltab。 cout{d[i]}=md[i].ltabendl。 } for(i=0。im。i++) for(k=0。klen。k++) for(j=0。jh。j++) { if(d[i][0]==t[j].ltab[0]) { for(n=0。nm。n++) { if(!t[j].jihe[k].length()) break。 else if(d[n].find(t[j].jihe[k])d[n].length()) { md[i].jihe[k]=md[n].ltab。 break。 } } break。 } } 第 22 頁，共 22 頁 ()。 for(i=0。im。i++) for(j=0。j()。j++) if(d[i].find(endnode[j])d[i].length()amp。amp。(md[i].ltab)) ednode+=md[i].ltab。 endnode=ednode。 coutendl最小化 DFA如下： endl。 outputfa(len,m,md)。 cout其中終態(tài)為： endnodeendl。 }
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1