编译原理实验有穷自动机.docx

#include#include#includeusingnamespacestd;#definemax100structedge stringfirst;/边的初始结点stringchange;/边的条件stringlast;/边的终点; intN;/NFA的边数vectorvalue;/求状态集合I的&-闭包，用&代替“空“stringclosure(stringa,edge*b)inti,j; for(i=0;ia.length();i+)for(j=0;jN;j+)if(bj.first0=ai&bj.change=&)a=a+bj.last0; returna; /状态集合I的a弧转换 stringmove(stringjihe,charch,edge*b)inti,j;strings=; for(i=0;ijihe.length();i+)for(j=0;jN;j+)if(bj.first0=jihei&bj.change0=ch)s=s+bj.last; returns; stringsort(stringt)intk,i,j;chartt; for(i=0;it.length()-1;i+)k=i; for(j=i+1;jt.length();j+)if(tjtk)k=j; tt=tk;tk=ti;ti=tt; returnt;voidmain() inti,j,x=0,h,length,m,d=0;stringChange;/输入符号stringFirst,Last;/初态，终态，stringTmax,ss;edge*b=newedgemax; cout请输入各边信息：起点条件（空用&表示）终点，以输入#结束。endl;for(i=0;ibi.first;if(bi.first=#)break;elsecinbi.changebi.last;N=i; cout请输入该NFA的初态及终态：FirstLast; cout请输入此NFA状态中的输入符号即边上的条件:Change; Tx=closure(First,b);Tx=sort(Tx);value.push_back(0);i=0; while(valuei=0&value.size()valuei=1; for(j=0;jChange.length();j+)ss=; ss=move(Ti,Changej,b);length=value.size();for(h=0;hlength;h+) if(Th=sort(closure(ss,b)break; if(h=length)T+x=sort(closure(ss,b);value.push_back(0); i+; edge*DFA=newedgemax; for(i=0;i=x;i+)/构造DFA的各边for(j=0;jChange.length();j+)DFAd.first=Ti;DFAd.change=Changej;ss=; ss=sort(closure(move(Ti,Changej,b),b);for(m=0;m=x;m+)if(ss=Tm)DFAd+.last=Tm; cout此NFA构造的DFA的各边信息如下：endl起点条件终点endl;for(i=0;id;i+)for(m=0;m=x;m+)if(DFAi.first=Tm)coutmDFAi.change; for(m=0;m=x;m+) if(DFAi.last=Tm)coutmendl; cout该DFA的初态为：;for(m=0;m=x;m+)for(j=0;jTm.length();j+)ss=Tm; if(ssj=First0)coutmendl; cout该DFA的终态为：;for(m=0;