不确定有穷自动机的确定化编译原理实验报告.docx

《不确定有穷自动机的确定化编译原理实验报告.docx》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、编译原理实验报告实验名称不确定有穷自动机的确定化实验时间_____2014年4月10日_______院系_______管理信息工程学院_______班级_______11计算机科学与技术____学号______201101020109____________姓名________姜高__________________1、实验目的不确定有穷自动机的确定化2、实验原理用子集构造算法构造子集加入子集族中直到收敛（所有构造的子集都已存在于子集族）为止。如原来不确定有穷自动机的五元组形式为：M=（K，&，F，S，Z），其中K为状态集，&为字母表

2、，F为转换函数，S为初始态，Z为终态集。用子集族S代替K，新的转换函数D代替F，形成新的五元组M=（S，&，D，S，Z）即将原不确定有穷自动机转换为确定有穷自动机。3、实验内容（1）闭包计算：closure(I)（2）转换函数：move(I,a)1、伪代码假定构造的子集族为S=（T1，T2。。。。。。），K为状态集：（1）开始，令closure(K0)为S中唯一成员，并且未被标记（2）WHILE（C中存在尚未被标记的子集T）DO{标记T;For每输入字母aDO{U:=closure(move(T,a));IfU不在S中then将U作为

3、未被标记的子集加在S中}}5.代码实现#include#include#defineMAXS100usingnamespacestd;stringNODE;//结点集合stringCHANGE;//终结符集合intN;//NFA边数structedge{stringfirst;stringchange;stringlast;};structchan{stringltab;stringjihe[MAXS];};voidkong(inta){inti;for(i=0;i

4、//排序voidpaixu(string&a){inti,j;charb;for(j=0;jNODE.find(a[i+1])){b=a[i];a[i]=a[i+1];a[i+1]=b;}}voideclouse(charc,string&he,edgeb[]){intk;for(k=0;k

5、.last)>he.length())he+=b[k].last;eclouse(b[k].last[0],he,b);}}}voidmove(chan&he,intm,edgeb[]){inti,j,k,l;k=he.ltab.length();l=he.jihe[m].length();for(i=0;i

6、>he.jihe[m].length())he.jihe[m]+=b[j].last[0];for(i=0;ihe.jihe[m].length())he.jihe[m]+=b[j].last[0];}//输出voidoutputfa(intlen,inth,chan*t){inti,j,m;cout

7、<<"I";for(i=0;i

8、;inti,j,k,m,n,h,x,y,len;boolflag;stringjh[MAXS],endnode,ednode,sta;cout<<"请输入NFA各边信息（起点条件[空为*]终点），以#结束："<