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

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

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

2、include#include#includeusingnamespacestd;structedge{intstart,end;charc;}E[100],Ekong[100];//E保存所有的边，Ekong保存转换字符为空的边structState{intH[100];//状态集合intcount;//状态集合中的元素个数intflag;//是否是接受状态intmark;//状态编号};intn;//n:边数31intnk=0;//空字符转换的边数intfirst,acc

3、ept;//开始状态，接受状态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状态转换表voidi

4、nput(){inti,s,e;charch;cout<<"请输入转换的有向边数n："<>n;cout<<"请输入NFA的开始状态："<>first;cout<<"请输入NFA的接受状态(输入-1结束)："<>accept;while(accept!=-1){f[accept]=1;cin>>accept;}cou

5、t<<"请输入NFA，起点，终点，转换字符('#'表示空字符)："<>s>>e>>ch;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;31Ekong[nk].end=e;Ekong[nk].c=ch;nk++;}}}Statemove

6、(StateT,chars)//c!='#'{Statetemp;temp.count=0;temp.mark=T.mark;inti,j=0,k=0;for(i=0;i

7、结果存在result中{intk=0;intm=0;num=0;stackS;S.push(t);intj;while(!S.empty()){j=S.top();S.pop();m=0;while(m

8、]==i)returntrue;}returnfalse;}Stateclosure(StateT)//求闭包{stackSTACK;Statetemp;inti,j,k;for(i=0;i