不确定有限状态自动机的确定化

1、不确定有限状态自动机确实定 化2021-12-05 22:11#include<iostream>#include<string>#define MAXS 100using namespace std;string NODE; / 结点集合string CHANGE; / 终结符集合int N; /NFA 边数struct edgestring first;string change;string last;struct chanstring ltab;string jiheMAXS;void kong(int a)int i;for(i=0;i<a;i+)cou

2、t<<' '/排序void paixu(string &a)int i,j;char b;for(j=0;j<a.length();j+) for(i=0;i<a.length();i+)if(NODE.find(ai)>NODE.find(ai+1)b=ai; ai=ai+1; ai+1=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

3、.last)>he.length() he+=bk.last;eclouse(bk.last0,he,b);void move(chan &he,int m,edge b) int i,j,k,l;k=he.ltab.length(); l=he.jihem.length();for(i=0;i<k;i+)for(j=0;j<N;j+)if(CHANGEm=bj.change0)&&(he.ltabi=bj.first0) if(he.jihem.find(bj.last0)>he.jihem.length() he.jihem+=bj.last

4、0;for(i=0;i<l;i+)for(j=0;j<N;j+)if(CHANGEm=bj.change0)&&(he.jihemi=bj.first0) if(he.jihem.find(bj.last0)>he.jihem.length() he.jihem+=bj.last0;/输出void outputfa(int len,int h,chan *t) int i,j,m; cout<<" I "for(i=0;i<len;i+)cout<<'I'<<CHANGEi<&

5、lt;" ""<<endl;cout<<endl<<" for(i=0;i<h;i+)cout<<' '<<ti.ltab; m=ti.ltab.length();for(j=0;j<len;j+)kong(8-m);m=ti.jihej.length();cout<<ti.jihej; cout<<endl;void main()edge *b=new edgeMAXS;int i,j,k,m,n,h,x,y,len;bool flag;st

6、ring jhMAXS,endnode,ednode,sta;<<encout<<" 请输入 NFA 各边信息 ( 起点 条件 空为 * 终点) ，以#终 止： dl;for(i=0;i<MAXS;i+)cin>>bi.first;if(bi.first="#") break; cin>>bi.change>>bi.last;N=i;/*for(j=0;j<N;j+) cout<<bj.first<<bj.change<<bj.last<<end

7、l;*/ for(i=0;i<N;i+) if(NODE.find(bi.first)>NODE.length() NODE+=bi.first; if(NODE.find(bi.last)>NODE.length() NODE+=bi.last;if(CHANGE.find(bi.change)>CHANGE.length()&&(bi.change!=")CHANGE+=bi.change;len=CHANGE.length();cout<<" 结点中属于终态的是： "<<endl; cin>

8、;>endnode;for(i=0;i<endnode.length();i+) if(NODE.find(endnodei)>NODE.length()cout<<" 所输终态不在集合中，错误！"<<endl; return; /cout<<"endnode="<<endnode<<endl;chan *t=new chanMAXS; t0.ltab=b0.first;h=1;eclouse(b0.first0,t0.ltab,b); / 求 e-clouse/cout<

9、;<t0.ltab<<endl;for(i=0;i<h;i+) for(j=0;j<ti.ltab.length();j+) for(m=0;m<len;m+) eclouse(ti.ltabj,ti.jihem,b);/求 e-clousefor(k=0;k<len;k+)/cout<<ti.jihek<<"->"move(ti,k,b);/求 move(I,a)/cout<<ti.jihek<<endl;for(j=0;j<ti.jihek.length();j+) e

10、clouse(ti.jihekj,ti.jihek,b); /求 e-clouse for(j=0;j<len;j+)paixu(ti.jihej);/对集合排序以便比较for(k=0;k<h;k+)flag=operator=(tk.ltab,ti.jihej);if(flag)break;if(!flag&&ti.jihej.length() th+.ltab=ti.jihej;cout<<endl<<" 状态转换矩阵如下： "<<endl; outputfa(len,h,t);/ 输出状态转换矩阵 /状态

11、重新命名 string *d=new stringh;NODE.erase();cout<<endl<<" 重命名： "<<endl;for(i=0;i<h;i+)sta=ti.ltab;ti.ltab.erase();ti.ltab='A'+i;NODE+=ti.ltab;cout<<''<<sta<<"="<<ti.ltab<<endl; for(j=0;j<endnode.length();j+) if(sta

12、.find(endnodej)<sta.length() d1=ednode+=ti.ltab;for(k=0;k<h;k+)for(m=0;m<len;m+) if(sta=tk.jihem) tk.jihem=ti.ltab; for(i=0;i<NODE.length();i+) if(ednode.find(NODEi)>ednode.length() d0+=NODEi;endnode=ednode; cout<<endl<<"DFA 如下： "<<endl; outputfa(len,h,t);/

13、输出 DFAcout<<" 其中终态为： "<<endnode<<endl;/DFA 最小化m=2;sta.erase();flag=0;for(i=0;i<m;i+)/cout<<"d"<<i<<"="<<di<<endl; for(k=0;k<len;k+)/cout<<"I"<<CHANGEk<<endl;y=m;for(j=0;j<di.length();j+

14、)for(n=0;n<y;n+) if(dn.find(tNODE.find(dij).jihek)<dn.length()|tNODE.find(dij).jihek.length()=0)if(tNODE.find(dij).jihek.length()=0)x=m;elsex=n;if(!sta.length()sta+=x+48;elseif(sta0!=x+48)dm+=dij;flag=1;di.erase(j,1); /cout<<di<<endl; j-;break; / 跳出 n/n/jif(flag)m+;flag=0;/cout<

15、<"sta="<<sta<<endl; sta.erase();/k/icout<<endl<<" 集合划分： "for(i=0;i<m;i+)cout<<""<<di<<" "cout<<endl;/状态重新命名chan *md=new chanm;NODE.erase();cout<<endl<<" 重命名： "<<endl;for(i=0;i<

16、;m;i+)mdi.ltab='A'+i;NODE+=mdi.ltab; cout<<""<<di<<"="<<mdi.ltab<<endl; for(i=0;i<m;i+)for(k=0;k<len;k+)for(j=0;j<h;j+)if(di0=tj.ltab0)for(n=0;n<m;n+)if(!tj.jihek.length() break;else if(dn.find(tj.jihek)<dn.length()mdi.jihek=md

17、n.ltab;break;break; ednode.erase(); for(i=0;i<m;i+) for(j=0;j<endnode.length();j+) if(di.find(endnodej)<di.length()&&ednode.find(mdi.ltab) ednode+=mdi.ltab;endnode=ednode; cout<<endl<<" 最小化 DFA 如下： "<<endl; outputfa(len,m,md);cout<<" 其中终态为： "<<endnode<<endl;/ 测试数据：i * 11 a 11 b 11 * 22 a 32 b 43 a 54 b 55 * 66 a 66 b 6/运行结果：请输入 NFA 各边信息起点 条件 空为* 终点，以 #终止： i1 a 11 b 11 * 22 a 32 b 43 a 54 b 55 * 66 a 66 b 66 * f#结点中属于终态的是:状态转