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

1、不确定有穷自动机确定化编译原理实验报告编译原理实验报告实验名称不确定有穷自动机的确定化实验时间20_年4月10日院系 管理信息工程学院班级 11计算机科学与技术学号 202020219姓1、实验目的 不确定有穷自动机的确定化2、实验原理用子集构造算法构造子集加入子集族中直 到收敛(所有构造的子集都已存在于子集族)为止。如原来不确 定有穷自动机的五元组形式为：M=(K, ；, F, S, Z),其中K 为状态集，；为字母表，F为转换函数，S为初始态，Z为终态 集。用子集族S代替K,新的转换函数D代替F,形成新的五元 组M= (S, ；, D, S, Z)即将原不确定有穷自动机转换为确定有 穷自动

2、机。3、实验内容(1)闭包计算：closure(I) (2)转换函数:moved,a)4、伪伪代码假定构造的子集族为S= (Tl, T2O O O O O O ),K为状态集：(1)开始，令closure(KO)为S中唯一成员，并且未被标记(2)WHILE (C中存在尚未被标记的子集T)DO 标记T； For每输入字母aDO U：= closure (move (T, a) ； If U 不在 S 中 then将U作为未被标记的子集加在S中 5.代码实现 #include<iostream>#include<string>ttdefine MA_S 100using n

3、amespace std；string NODE； 结点集合string CHANGE； 终结符集合 int N； /NFA 边数 struct edge( string first； string change；string last； );struct chan(string Itab； string jiheMA_S； );void kong(int a) ( int i；for(i=0；i<a；i+) cout<<n "； )排序void pai_u(string ； a) (int i,j；char b；for(j=0；j<a. length； j+

4、)for (i=0；i<a. length；i+)if(NODE, find>NODE. find(ai+l)b=ai；ai=ai + l；ai + l=b；)void eclouse (char c,string ；he,edge b口) (int k；for(k=0；k<N；k+)(if(c=bk. first0)if (bk. change= )(if (he. find(bk. last) >he. length)he+=bk. last；eclouse(bk. last0,he,b)；)void move(chan ；he,int m,edge b)int i

5、,j,k,1；k=he. Itab. length；l=he. jihem. length；for (i=0；i<k； i+)for(j=0；j<N； j+)if(CHANGEm=bj. change0)；(he. ltabi=bj. firif(he. jihem. find(bj. last0)>he. jihem. length)he. jihem+=bj. last0；for(i=0；i<l；i+)for(j=0；j<N；j+)if(CHANGEm=bj. change0)；(he. jihemi=bj. first0)if(he. jihem. find

6、(bj. last0)>he. jihem. length)he. jihem+=bj. last0；)输出void outputfa(int len,int h,chan _t)int i,j,m；cout« a I f9 ；for(i=0；i<len；i+)cout«,r,«CHANGEi<< a w ；cout<<endl<< “" <<endl；for(i=0；i<h； i+)(cout<<n H<<ti. Itab；m=ti. Itab. length；f

7、or(j=0；j<len；j+)(kong (8-m)；m=ti. jihej. length；cout<<ti. jihej；)cout<<endl；)void main(edge _b=new edgeMA_S；int i,len；笫6页共15页bool flag；string jhIA_S, endnode, ednode, sta；cout<<”请输入NFA各边信息(起点条件空为终点)， 以#结束：" <<endl；for(i=0；i<MA_S；i+)(cin>>bi. first；if(bi. firs

8、t= ) break；cin>>bi. change>>bi. last；)N=i；/_for(j=0； j<N； j+)cout«bj. first«bj. change«bj. last«endl；_/for(i=0；i<N；i+)(if(NODE. find(bi. first)>N0DE. length)NODE+=bi. first；if (NODE, find last)>N0DE. length)NODE+=bi. last；if (CHANGE. find(bi. change) >C

9、HANGE. length) ； ； (biL ch ange!= )CHANGE+=bi. change；len=CHANGE. length；cout<< “结点中属于终态的是："Vendl；cin>>endnode；for(i=0；i<endnode. length；i+)if (NODE, find (endnode i)>N()DE. length)(cout<<”所输终态不在集合中，错误! " «endl； return；)/cout<< "endnode二" «

10、endnode<<endl；chan _t=new chanMA_S；t0. ltab=b0.first；h=l；eclouse (b0. first 0, t 0. ltab,b)； 求 e-clouse/cout<<t0. ltab<<endl；for(i=0；i<h； i+)(for (j=0；j<ti. Itab. length； j+)for(m=O；m<len；m+)eclouse(t i. ltabj, ti. jihem ,b)； 求 e-clouse for(k=0；k<len；k+)/cout<<ti.

11、 jihek<< ；move(ti ,k,b)； 求 move (I, a)/cout«ti. jihek<<endl；for(j=0；j<ti. jihek. length；j+)eclouse(ti. jihekj,ti. jihek,b)； /求 e- clouse)for(j=0；j<len；j+)(pai_u(ti. jihej); 对集合排序以便比较for(k=O；k<h；k+)(flag=operator=(tk. Itab,ti. jihej)；if(flag)break；)if(!flag；;ti. jihej. lengt

12、h)th+. ltab=ti. jihej；)cout<endl<"状态转换矩阵如下：«endl；笫10页共15页outputfa(len,h,t) ； /输出状态转换矩阵状态重新命名string _d=new stringh；NODE, erase；cout<endl<< “重命名：«endl；for(i=0；i<h；i+)(sta=ti. Itab；ti. Itab. erase；ti. Itab="A"+i；NODE+=ti. Itab；cout«,r «sta« = &#

13、171;ti. ltab«endl；for (j=0；j<endnode. length；j+) if(sta. find(endnodej)<sta. length)d1=ednode+=ti.Itab；for(k=0；k<h；k+)for(m=0；m<len；m+) if(sta=tk. jihem)tk. jihem=ti. Itab；for (i=0；i<NODE. length；i+)if(ednode. find(NODEi)>ednode. length)dO+=NODEi；endnode=ednode；cout<<end

14、l<< UDFA 如下： <<endl；outputfa(len,h, t)； 输出 DFAcout<”其中终态为：«endnode«endl；/DFA最小化m=2；sta. erase；flag=0；for(i=0；i<m；i+)(/cout« «i« "=" «di«endl；for (k=0；k<len；k+)(/cout« T «CHANGEk«endl；y 二m；for(j=0；j<di. length；j+)(for

15、 (n=0；n<y；n+)(if(dn. find(tNODE. find(dij). jihek)<dn. leng th |t NODE. find(di j)L jihek. length=0 )if(tNODE, find(dij). jihek. length=0)_二m；else_=n；if(!sta. length)(sta+=_+48；)elseif(sta0!=_+48)(dm+=di j；flag=l；di. erase(j,1)； /cout«di«endl； j;break； 跳出 n/n/jif(flag)m+；flag=O；)cout

16、<< “sta=" <<sta<endl；sta. erase；k/icout<<end"< ”集合划分:；for(i=0；i<m；i+)cout« «di« <( w ；cout<<endl；状态重新命名chan _md=new chanm；NODE, erase；cout<<end"<"重命名:«endl；for(i=0；i<m；i+)(mdi. ltab=,，A"+i；N0DE+=mdi. Itab；cout« (i 9f «di«= «mdi. ltab«endl；for(i=0；i<m；i+)for(k=0；k<len；k+)for(j=0；j<h；j+)(if(diO=tj. ltab0)(for (n=0；n<m；n+)(if (!tj. jihek. length)break；elseif(dn. find(tj. jihek)<dn. length) (mdi. jihek=mdn. Itab；break；)break；)ednode