实验一--利用子集法构造DFA

1实验一利用子集法构造DFA一、实验目的掌握将非确定有限自动机确定化的方法和过程二、实验要求及内容实验要求：1.输入一个NFA，输出一个接受同一正规集的DFA；2.采用C++语言，实现该算法；3.编制测试程序；4.调试程序。实验步骤：1.输入一个NFA关系图；2.通过一个转换算法将NFA转换为DFA；3.显示DFA关系图。三、实验环境计算机、Windows操作系统、VisualC++程序集成环境。四、程序代码#includestdafx.h#includeiostream#includealgorithm#includequeue#includestack#includestringusingnamespacestd;structedge{intstart,end;charc;}E[100],Ekong[100];//E保存所有的边，Ekong保存转换字符为空的边structState{intH[100];//状态集合intcount;//状态集合中的元素个数intflag;//是否是接受状态intmark;//状态编号};intn;//n:边数2intnk=0;//空字符转换的边数intfirst,accept;//开始状态，接受状态charalpha[100];//输入字母表,#代表空串intnumof_char=0;//字母表中的字符个数intuseof_char[256];//该转换字符是否用过intf[200];//状态属性标志：0表示始态，1表示接受态，-1表示中间态StateDFA[100];//DFA状态集intuseof_DFA[100];//标志构造出来的状态是否已存在intnumof_Dtran=0;//最后得到的DFA中的状态数charDtran[100][100];//DFA状态转换表voidinput(){inti,s,e;charch;cout请输入转换的有向边数n：endl;cinn;cout请输入NFA的开始状态：endl;cinfirst;cout请输入NFA的接受状态(输入-1结束)：endl;memset(f,-1,sizeof(f));memset(useof_char,0,sizeof(useof_char));f[first]=0;cinaccept;while(accept!=-1){f[accept]=1;cinaccept;}cout请输入NFA，起点，终点，转换字符('#'表示空字符)：endl;intk=0;for(i=0;in;i++){cinsech;E[i].start=s;E[i].end=e;E[i].c=ch;if(ch!='#'&&!useof_char[ch]){alpha[numof_char++]=ch;useof_char[ch]=1;}if(ch=='#'){Ekong[nk].start=s;3Ekong[nk].end=e;Ekong[nk].c=ch;nk++;}}}Statemove(StateT,chars)//c!='#'{Statetemp;temp.count=0;temp.mark=T.mark;inti,j=0,k=0;for(i=0;iT.count;i++){j=0;while(jn){if(E[j].start==T.H[i]&&E[j].c==s){temp.H[temp.count++]=E[j].end;}j++;}}returntemp;}voidarriveBynone(intt,intresult[],int&num)//搜索状态t通过一个或多个空字符到达的状态,结果存在result中{intk=0;intm=0;num=0;stackintS;S.push(t);intj;while(!S.empty()){j=S.top();S.pop();m=0;while(mnk){if(Ekong[m].start==j){result[num++]=Ekong[m].end;4S.push(Ekong[m].end);}m++;}}}boolcheck(inti,StateT)//判断状态i是否在T中{intj;for(j=0;jT.count;j++){if(T.H[j]==i)returntrue;}returnfalse;}Stateclosure(StateT)//求闭包{stackintSTACK;Statetemp;inti,j,k;for(i=0;iT.count;i++){STACK.push(T.H[i]);temp.H[i]=T.H[i];}temp.count=T.count;temp.mark=T.mark;while(!STACK.empty()){intt=STACK.top();STACK.pop();//搜索状态t通过一个或多个空字符到达的状态intsearch_result[100];intnum;arriveBynone(t,search_result,num);for(j=0;jnum;j++){if(!check(search_result[j],temp)){temp.H[temp.count++]=search_result[j];STACK.push(search_result[j]);}}5}for(k=0;ktemp.count;k++){if(f[temp.H[k]]==1){temp.flag=1;break;}if(f[temp.H[k]]==0){temp.flag=0;break;}}sort(temp.H,temp.H+temp.count);for(i=0;inumof_Dtran;i++){if(temp.count!=DFA[i].count)continue;sort(DFA[i].H,DFA[i].H+DFA[i].count);for(j=0;jDFA[i].count;j++){if(DFA[i].H[j]!=temp.H[j])break;}if(j=DFA[i].count)temp.mark=DFA[i].mark;}returntemp;}intcheck_inDFA()//检查DFA中是否存在未被标记的状态,有则返回标号，否则返回-1{inti;for(i=0;inumof_Dtran;i++){if(!useof_DFA[i])returni;}return-1;}boolcheck_whetherin_DFA(StateT){inti,j;sort(T.H,T.H+T.count);6for(i=0;inumof_Dtran;i++){if(T.count!=DFA[i].count)continue;sort(DFA[i].H,DFA[i].H+DFA[i].count);for(j=0;jDFA[i].count;j++){if(DFA[i].H[j]!=T.H[j])break;}if(j=DFA[i].count)returntrue;}if(i=numof_Dtran)returnfalse;elsereturntrue;}voidchild_method(){intm,n;for(m=0;m100;m++)for(n=0;n100;n++)Dtran[m][n]='#';for(m=0;m100;m++)DFA[m].flag=-1;StateS0,U;S0.flag=0;S0.count=1;S0.H[0]=first;StateT;T=closure(S0);T.mark=0;T.flag=0;DFA[numof_Dtran++]=T;memset(useof_DFA,0,sizeof(useof_DFA));intj=check_inDFA();intk;while(j!=-1){useof_DFA[j]=1;for(k=0;knumof_char;k++){U=closure(move(DFA[j],alpha[k]));7//ifU不在DFA中if(!check_whetherin_DFA(U)){U.mark=numof_Dtran;DFA[numof_Dtran++]=U;}Dtran[DFA[j].mark][U.mark]=alpha[k];}j=check_inDFA();}}voidprint(){inti,j;for(i=0;inumof_Dtran;i++){couti:;for(j=0;jDFA[i].count;j++)coutDFA[i].H[j];if(DFA[i].flag==1)cout此为DFA的接受状态;if(DFA[i].flag==0)cout此为DFA的开始状态;coutendl;}coutendl;for(i=0;inumof_Dtran;i++){for(j=0;jnumof_Dtran;j++){if(Dtran[i][j]!='#'){couti-jByDtran[i][j]endl;}}}}voidjudge(stringch){inti,j,k;intnum=ch.length();Statetemp;k=0;for(i=0;inum;i++){for(j=0;jnumof_Dtran;j++){8if(Dtran[k][j]==alpha[i]){temp=DFA[j];k=j;break;}}}if(temp.flag!=1)cout字符串ch无法由该DFA得到endl;elsecout字符串ch可以由该DFA得到endl;coutendl;}int_tmain(intargc,_TCHAR*argv[]){input();child_method();coutendl;print();strings;while(cins)judge(s);system(pause);return0;}五、实验结果9六、算法分析使用子集构造法对非确定有限自动机进行确定化的过程中存在大量重复计算的问题。为解决此问题,基于非确定有限自动机的特点并针对子集构造法的不足,提出了一种优化的非确定有限自动机确定化算法。首先定义了识别符的有效引出状态集概念并证明了ε-closure的并定理以保证算法的正确性,其次给出了用于避免重复计算的识别符的有效引出状态集的构造子算法和单状态集的ε-closure的求算子算法,基于这两个子算法给出了优化的非确定有限自动机确定化算法,最后将算法应用于实例,实验结果表明计算量远小于子集构造法的计算量。相比子集构造法,算法能更有效地对非确定有限自动机进行确定化。七、实验小结以前上课时有许多的问题并没有真正的认识到，但通过这次实验，使我掌握了许多更重要的知识点。通过实验，我们可以知道将NFA转换成接受同样语言的DFA的算法称为子集构造算法。NFA变换到DFA的基本思想是：让DFA的每个状态对应NFA的一个状态集。实验实现了NFA到DFA的转换。实验二THOMPSON算法的实现一、实验目的掌握将正规表达式转换为NFA的方法和过程三、实验要求及内容1.输入一个正规表达式，输出一个接受同一语言的NFA2.采用C++语言，实现该算法3.编制测试程序4.调试程序三、实验环境计算机、Windows操作系统、VisualC++程序集成环境。四、程序代码#includeThompson.hvoidmain(){10stringRegular_Expression=(a|b)*abb;cellNFA_Cell;input(Regular_Expression);//调试需要先屏蔽Regular_Expression=add_join_symbol(Regular_Expression);Regular_Express