实验一 利用子集法构造DFA

《实验一 利用子集法构造DFA》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

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

2、eusingnamespacestd;structedge{intstart,end;charc;}E[100],Ekong[100];//E保存所有的边，Ekong保存转换字符为空的边structState{intH[100];//状态集合intcount;//状态集合中的元素个数intflag;//是否是接受状态intmark;//状态编号};intn;//n:边数31intnk=0;//空字符转换的边数intfirst,accept;//开始状态，接受状态charalpha[100];//输入字母表,#代表空串intnumof_char=0;//字母表中的字符个数in

3、tuseof_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："<>n;cout<<"请输入NFA的开始状态："<>first;cout<<"请输入NFA

4、的接受状态(输入-1结束)："<>accept;while(accept!=-1){f[accept]=1;cin>>accept;}cout<<"请输入NFA，起点，终点，转换字符('#'表示空字符)："<>s>>e>>ch;E[i].start=s;E[i].end=e;E[i].c=ch;if(ch!='#'&&!useof_char[ch]){alp

5、ha[numof_char++]=ch;useof_char[ch]=1;}if(ch=='#'){Ekong[nk].start=s;31Ekong[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;i

6、++;}}returntemp;}voidarriveBynone(intt,intresult[],int&num)//搜索状态t通过一个或多个空字符到达的状态,结果存在result中{intk=0;intm=0;num=0;stackS;S.push(t);intj;while(!S.empty()){j=S.top();S.pop();m=0;while(m

7、断状态i是否在T中{intj;for(j=0;jSTACK;Statetemp;inti,j,k;for(i=0;i