NFA确定化

编译原理上机实验报告（一）一、实验题目对任意NFA确定化二、实验环境介绍Codeblacksc++Windows三、实验目的与要求把nfs转换成dfs并且确定化想法：确定每个状态之间的关系，用数组存储nfs，根据二维数组表格把状态确定化，然后根据新状态得出确定的dfs、对无用的状态进行消除。四、实验结果（附源代码）#includeiostream#includecstdio#includealgorithm#includefstream#includequeue#includevector#includestring#includecstring#includeset#defineMAX500#defineM1000007#ifdefWIN32#pragmawarning(disable:45144786)#endifusingnamespacestd;structSet{setintelements;intstate;}I[MAX];vectorinte[MAX];vectorintedge[MAX];vectorintval1[MAX];vectorintval2[MAX];vectorinthash[M];vectorinttypes;intvis[MAX][MAX];intcntp,cnts,start,finish,used[MAX];void_clear();voidclear();void_add(intu,intv,intx);voidadd(intu,intv,intx);voiddfs(setint&elements,intu,intd,intflag);voidensure();voidminimize();intget_hash(setint&item);intmain(){intm;puts(给出NFA的边的条数:);while(~scanf(%d,&m)){_clear();clear();puts(给出NFA的始态和终态:);scanf(%d%d,&start,&finish);puts(给出所有的边，每行一条:);for(inti=0;im;i++){intu,v,x;scanf(%d%d%d,&u,&v,&x);_add(u,v,x);}#ifdefDEBUGsetinttemp;intnum[]={2,3,6,7,8};for(inti=0;i5;i++)dfs(temp,num[i],0,1);setint::iteratorit=temp.begin();for(;it!=temp.end();it++)printf(%d,*it);puts();#elseensure();puts(计算结果如下:);printf(%d\n,cnts);for(inti=0;icnts;i++)for(intj=0;jedge[i].size();j++)printf(edges:%d%d%d\n,i,edge[i][j],val2[i][j]);puts(\n给出DFA的边的条数:);#endif}return0;}void_clear(){for(inti=0;iMAX;i++){e[i].clear();val1[i].clear();}types.clear();memset(used,0,sizeof(used));}voidclear(){for(inti=0;iMAX;i++){edge[i].clear();val2[i].clear();}}void_add(intu,intv,intx){e[u].push_back(v);val1[u].push_back(x);if(!used[x]){types.push_back(x);used[x]=types.size();}}intget_hash(setint&item){intsum=0;setint::iteratorit=item.begin(),it1,it2;for(;it!=item.end();it++){sum+=(*it)*(*it)%M;sum%=M;}for(inti=0;ihash[sum].size();i++){intx=hash[sum][i];setint&temp=I[x].elements;it=temp.begin();boolflag=true;if(temp.size()!=item.size())continue;for(it1=temp.begin(),it2=item.begin();it2!=item.end();it1++,it2++)if(*it1!=*it2){flag=false;break;}if(flag)returnx;}return-1;}intmake_hash(setint&item){intsum=0;setint::iteratorit=item.begin();for(;it!=item.end();it++){sum+=(*it)*(*it)%M;sum%=M;}hash[sum].push_back(cnts);returncnts++;}voidadd(intu,intv,intx){edge[u].push_back(v);val2[u].push_back(x);}voiddfs(setint&elements,intu,intd,intflag){if(vis[u][d])return;vis[u][d]=1;if(d==1)elements.insert(u);if(d==2)return;intlen=e[u].size();for(inti=0;ilen;i++){intv=e[u][i],dd;intx=val1[u][i];if(x==flag)dd=d+1;elseif(x==0)dd=d;elsecontinue;dfs(elements,v,dd,flag);}}voidensure(){I[0].elements.insert(start);cnts=1;for(inti=0;icnts;i++){setint&cur=I[i].elements;for(intj=0;jtypes.size();j++){if(types[j]==0)continue;memset(vis,0,sizeof(vis));setint&temp=I[cnts].elements;temp.clear();setint::iteratorit=cur.begin();for(;it!=cur.end();it++)dfs(temp,*it,0,types[j]);if(temp.empty())continue;intx=get_hash(temp);if(x==-1)x=make_hash(temp);add(i,x,types[j]);}setint::iteratorit=cur.begin();printf(I%d:,i);for(;it!=cur.end();it++)printf(%d,*it);puts();}}