c语言编程NFA确定化

NFA确定化为DFA1．实验目的设计并实现将NFA确定化为DFA的子集构造算法，从而更好地理解有限自动机之间的等价性，掌握词法分析器自动产生器的构造技术。该算法也是构造LR分析器的基础。2．实验要求设计并实现计算状态集合I的ε闭包的算法ε_Closure(I)和转换函数Move(I,a)，并在此基础上实现子集构造算法Subset_Construction。利用该从NFA到DFA的转换程序Subset_Construction，任意输入一个NFAN=（S,Σ,δ,s0,F），输出一个接收同一语言的DFAM=（S’,Σ,δ’,s0’,F’）。3．实验内容(1)令I是NFAN的状态集S的一个子集，I的ε闭包的ε_Closure(I)构造规则如下：(a)若s∈I，则s∈ε_Closure(I)；(b)若s∈ε_Closure(I)且δ(s,ε)=s’而s’∉ε_Closure(I)，则s’∈ε_Closure(I)根据上面的规则，下面给出了一个计算I的ε闭包的算法ε_Closure(I)。SETS;SETε_Closure(input)SET*input;{S=input;/*初始化*/push();/*把输入状态集中的全部状态压入栈中*/while(栈非空){Nfa_statei;pop();/*把栈顶元素弹出并送入i*/if(存在δ(i,ε)=j)if(j不在S中){把i加到S中;把j压入栈中;}}returnS;/*返回ε_Closure(input)集合*/}完成上述算法的设计。(2)令I是NFAN的状态集S的一个子集，a∈Σ,转换函数Move(I,a)定义为：Move(I,a)=ε_Closure(J)其中，J={s’|s∈I且δ(s,a)=s’}转换函数Move(I,a)的设计通过调用ε_Closure(input)实现，完成该函数的设计。(3)从NFAN构造一个与其等价的DFAM的子集构造算法，就是要为DFAM构造状态转换表Trans，表中的每个状态是NFAN状态的集合，DFAM将“并行”地模拟NFAN面对输入符号串所有可能的移动。下面给出了子集构造算法Subset_Construction的框架，请完成其设计过程。有关数据结构：States[]是一个M的数组，每个状态有两个域，set域存放N的状态集合，flg域为一标识。Trans[]是M的转移矩阵（输入字母表Σ元素个数×最大状态数），Trans[i][a]=下一状态。iM的当前状态号a输入符号，a∈ΣNstates[]M的下一新状态号S定义M的一个状态的N的状态集初始化：States[0].set=ε_Closure({N的初态})States[0].flg=FALSENstates=1i=0S=ФTrans初始化为无状态’-’while(States[i]的flg为FALSE){States[i].flg=TRUE;for(每个输入符号a∈Σ){S=ε_Closure(Move(States[i].set,a));if(S非空)if(States中没有set域等于S的状态){States[Nstates].set=S;States[Nstates].flg=FALSE;Trans[i][a]=Nstates++;}elseTrans[i][a]=States中一个set域为S的下标;}}此算法的输出M主要由Trans矩阵描述，其中省略了每个状态是否为终态的描述，应加以完善。4．实验程序;#includeiostream#includestring#defineMAXS100usingnamespacestd;stringNODE;//结点集合stringCHANGE;//终结符集合intN;//NFA边数structedge{stringfirst;stringchange;stringlast;};structchan{stringltab;stringjihe[MAXS];};voidkong(inta){inti;for(i=0;ia;i++)cout'';}//排序voidpaixu(string&a){inti,j;charb;for(j=0;ja.length();j++)for(i=0;ia.length();i++)if(NODE.find(a[i])NODE.find(a[i+1])){b=a[i];a[i]=a[i+1];a[i+1]=b;}}voideclouse(charc,string&he,edgeb[]){intk;for(k=0;kN;k++){if(c==b[k].first[0])if(b[k].change==*){if(he.find(b[k].last)he.length())he+=b[k].last;eclouse(b[k].last[0],he,b);}}}voidmove(chan&he,intm,edgeb[]){inti,j,k,l;k=he.ltab.length();l=he.jihe[m].length();for(i=0;ik;i++)for(j=0;jN;j++)if((CHANGE[m]==b[j].change[0])&&(he.ltab[i]==b[j].first[0]))if(he.jihe[m].find(b[j].last[0])he.jihe[m].length())he.jihe[m]+=b[j].last[0];for(i=0;il;i++)for(j=0;jN;j++)if((CHANGE[m]==b[j].change[0])&&(he.jihe[m][i]==b[j].first[0]))if(he.jihe[m].find(b[j].last[0])he.jihe[m].length())he.jihe[m]+=b[j].last[0];}//输出voidoutputfa(intlen,inth,chan*t){inti,j,m;coutI;for(i=0;ilen;i++)cout'I'CHANGE[i];coutendl-------------------------endl;for(i=0;ih;i++){cout''t[i].ltab;m=t[i].ltab.length();for(j=0;jlen;j++){kong(8-m);m=t[i].jihe[j].length();coutt[i].jihe[j];}coutendl;}}voidmain(){edge*b=newedge[MAXS];inti,j,k,m,n,h,x,y,len;boolflag;stringjh[MAXS],endnode,ednode,sta;cout请输入NFA各边信息（起点条件[空为*]终点），以#结束：endl;for(i=0;iMAXS;i++){cinb[i].first;if(b[i].first==#)break;cinb[i].changeb[i].last;}N=i;/*for(j=0;jN;j++)coutb[j].firstb[j].changeb[j].lastendl;*/for(i=0;iN;i++){if(NODE.find(b[i].first)NODE.length())NODE+=b[i].first;if(NODE.find(b[i].last)NODE.length())NODE+=b[i].last;if((CHANGE.find(b[i].change)CHANGE.length())&&(b[i].change!=*))CHANGE+=b[i].change;}len=CHANGE.length();cout结点中属于终态的是：endl;cinendnode;for(i=0;iendnode.length();i++)if(NODE.find(endnode[i])NODE.length()){cout所输终态不在集合中，错误！endl;return;}//coutendnode=endnodeendl;chan*t=newchan[MAXS];t[0].ltab=b[0].first;h=1;eclouse(b[0].first[0],t[0].ltab,b);//求e-clouse//coutt[0].ltabendl;for(i=0;ih;i++){for(j=0;jt[i].ltab.length();j++)for(m=0;mlen;m++)eclouse(t[i].ltab[j],t[i].jihe[m],b);//求e-clousefor(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);//求e-clouse}for(j=0;jlen;j++){paixu(t[i].jihe[j]);//对集合排序以便比较for(k=0;kh;k++){flag=operator==(t[k].ltab,t[i].jihe[j]);if(flag)break;}if(!flag&&t[i].jihe[j].length())t[h++].ltab=t[i].jihe[j];}}coutendl状态转换矩阵如下：endl;outputfa(len,h,t);//输出状态转换矩阵//状态重新命名string*d=newstring[h];NODE.erase();coutendl重命名：endl;for(i=0;ih;i++){sta=t[i].ltab;t[i].ltab.erase();t[i].ltab='A'+i;NODE+=t[i].ltab;cout'{'sta}=t[i].ltabendl;for(j=0;jendnode.length();j++)if(sta.find(endnode[j])sta.length())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;}for(i=0;iNODE.length();i++)if(ednode.find(NODE[i])ednode.length())d[0]+=NODE[i];endnode=ednode;coutendlDFA如下：endl;outputfa(len,h,t);//输出DFAcout其中终态为：endnodeendl;}5..实验截图：