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

《实验一--利用子集法构造DFA.docx》由会员分享，可在线阅读，更多相关《实验一--利用子集法构造DFA.docx（33页珍藏版）》请在第一文库网上搜索。

1、实验一利用子集法构造DFA一、实验目的掌握将非确定有限自动机确定化的方法和过程二、实验要求及内容实验要求：1.输入一个NFA,输出一个接受同一正规集的DFA；2,采用C+语言，实现该算法；3 ,编制测试程序；4 .调试程序。实验步骤：1 .输入一个NFA关系图；2 .通过一个转换算法将NFA转换为DFA；3 .显TKDFA关系图。三、实验环境计算机、Windows操作系统、Visua1C+程序集成环境。四、程序代码ttinc1ude,stdafx.hftinc1udeftinc1udeftinc1udettinc1udeftinc1udeusingnamespacestd;structedge

2、(intstart,end;charc;)E100,Ekong100;E保存所有的边，EkOng保存转换字符为空的边structStateintH100;状态集合intCoUnt;状态集合中的元素个数intf1ag;是否是接受状态intmark;状态编号)；intn;n:边数intnk=0;空字符转换的边数intfirst,accept;开始状态，接受状态chara1pha100;输入字母表,#代表空串intnumof_char=0;字母表中的字符个数intUSeof1ehar256;该转换字符是否用过intf200;状态属性标志：0表示始态，1表示接受态，T表示中间态StateDFA100;

3、DFA状态集intUSeOf1DFA100;标志构造出来的状态是否已存在intnumof_Dtran=0;最后得到的DFA中的状态数charDtran100100;DFA状态转换表voidinput()inti,s,e;charch;CoIrt请输入转换的有向边数n：“n;COUt请输入NFA的开始状态：first;COUt请输入NFA的接受状态(输入-1结束)：zzaccept;whi1e(accept!=-1)(faccept=1;cinaccept;)COUt请输入NFA,起点，终点，转换字符(#表示空字符)：end1;intk=0;for(i=0;isech;Ei.start=s;Ei

4、.end=e;Ei.c-ch;if(ch!=,#&!useof_charch)(a1phanumof_char+-ch;useof_charch=1;Ekongnk.start-s;Ekongnk.end-e;Ekongnk.c-ch;nk+;Statemove(StateT,chars)c!,ft,Statetemp;temp,count=0;temp.mark=T.mark;inti,j=0,k=0;for(i=0;iT.count;i+)J-O；whi1e(jn)if(Ej.start=T.Hi&Ej.C=S)temp.Htemp,count+=Ej.end;)j+；)returntem

5、p;voidarriveBynone(intt,intresu1t,int&num)搜索状态t通过一个或多个空字符到达的状态,结果存在resu1t中intk=0;intm=0;num=0;stackS;S.push(t);intj;whi1e(!S.empty()j=S.top();S.pop();m=0;whi1e(mnk)if(Ekongm.Start=j)resu1tnum+=Ekongm.end;S. push(Ekongm.end);m+;boo1check(inti,StateT)判断状态i是否在T中intj;for(j=0;jT.count;j+)if(T.Hj=i)return

6、true;returnfa1se;)Statec1osure(StateT)求闭包(stackSTACK;Statetemp;inti,j,k；for(i=0;iT.count;i+)(STACK.push(T.Hi);temp.Hi=T.Hi;)temp.count=T.count;temp.mark=T.mark;whi1e(!STACK,empty()intt=STACK.top();STACK,pop();搜索状态t通过一个或多个空字符到达的状态intsearch_resu1t100;intnum;arriveBynone(t,search_resu1t,num);for(j=0;jn

7、um;j+)if(!check(searchresu1tj,temp)temp.Htemp,count+=search_resu1tj;STACK,push(searchresu1tj);for(k=0;ktemp.count;k+)if(ftemp.Hk=1)temp,fIag=I;break;if(ftemp.Hk=0)temp,fIag=O;break;)sort(temp.H,temp.H+temp.count);for(i=0;inumof_Dtran;i+)if(temp,count!=DFAi.count)continue;sort(DFAi.H,DFAi.H+DFAi.coun

8、t);for(j=0;j=DFAi.count)temp.mark=DFAi.mark;)returntemp;)intCheCk_inDFA()检查DFA中是否存在未被标记的状态,有则返回标号，否则返回-1inti;for(i=0;inumof_Dtran;i+)(if(!useof_DFAi)returni;)return-1;)boo1check_whetherin_DFA(StateT)inti,j;sort(T.H,T.H+T.count);for(i=0;inumofDtran;i+)if(T.count!=DFAi.count)continue;sort(DFAi.H,DFAi.

9、H+DFAi.count);for(j=0;j=DFAi.count)returntrue;)if(i=numof_Dtran)returnfa1se;e1sereturntrue;voidchi1dmethod()intm,n;for(m=0;m100;m+)for(n=0;n100;n+)Dtranmn,;for(m=0;m100;m+)DFAm.fIag=-I;StateSO,U;SO.fIag=O;SO.count=1;SO.HO=first;StateT;T=c1osure(SO);T. mark=0;U. f1ag=O;DFAnumof_Dtran+=T;memset(useof_

10、DFA,O,sizeof(useof_DFA);intj=check_inDFA();intk;whi1e(j!=-1)useof_DFAj=1;for(k=0;knumof_char;k+)U=c1osure(move(DFAj,a1phak);/ifU不在DFA中if(!CheckwhetherinDFA(U)U.mark=numof_Dtran;DFAnumof_Dtran+=U;DtranDFAj.markU.mark=a1phak;)j=check_inDFA();voidprint()inti,j;for(i=0;inumof_Dtran;i+)(coutizz:；for(j=0;

11、jDFAi.count;j+)coutDFAi.Hjr,;if(DFAi.f1ag=1)CoUt此为DFA的接受状态；if(DFAi.fIag=O)CoUt此为DFA的开始状态；coutend1;)coutend1;for(i=0;inumof_Dtran;i+)for(j=0;jnumof_Dtran;j+)if(Dtranij!=#)couti,zj,zByzzDtranijend1;)voidjudge(stringch)(inti,j,k;intnum=ch.1ength();Statetemp;k=0;for(i=0;inum;i+)for(j=0;jnumof_Dtran;j+)i

12、f(Dtrankj-a1phai)temp=DFAj;k=j；break;)if(temp,f1ag!=1)COUt字符串ch无法由该DFA得到end1;e1seCoUt字符串可以由该DFA得到end1;coutend1;int_tmain(intargc,TCHAR*argv)input();chi1d_method();couts)judge(s);system(,zpause,z);return0;五、实验结果0101247此为DFA的开始怵态1=1234678此为DFA的接受状态2:124567HJI_JJ六、算法分析使用子集构造法对非确定有限自动机进行确定化的过程中存在大量重复计算的问题。为解决此问题,基于非确定有限自动机的特点并针对子集构造法的不足,提出了一种优化的非确定有限自动机确定化算法。首先定义了识别符的有效引出状态集概念并证明了-c1osure的并定理以保证算法的正确性,其次给出了用于避免重复计算的识别符的有效引出状态集的构造子算法和单状态集的-c1osure的求算子