《NFA到DFA的确定化及最小化.doc》由会员分享，可在线阅读，更多相关《NFA到DFA的确定化及最小化.doc（8页珍藏版）》请在三一文库上搜索。
1、NFA 转化为 DFA 确实定化及最小化一 NFA 向 DFA 的转换从 NFA 的矩阵表示中可以看出，表项通常是一状态的集合，而在 DFA 的矩阵表示中，表 项是一个状态， NFA 到相应的 DFA 的构造的根本思路是： DFA 的每一个状态对应 NFA 的 一组状态 .DFA 使用它的状态记录在 NFA 读入一个输入符号后可能到达的所有状态 .得到新的 DFA 之后，并没有完成任务，因为通过 NFA 转化成 DFA 不一定是最简的，也 就是说，有多余的状态可以被删除，而我们需要的是得到一个唯一的最简的 DFA12 ，也就 是说， NFA 转化为 DFA 之后，还需要化简，也就是最小化。二
2、NFA 确实定化方法子集法：1先把DFA M中的Q和F置为空集；2. M的开场状态qO =q0，把qO置为未标记后参加到Q中；3. 如果Q中存在未标记的状态q1,q2, , , qi，那么对每个a 刀定义：3 (q1,q2, qi,a)=p1,p2, ,pi当且仅当 3 (q1,q2, , qi,a)=p1,p2, ,pi。如果q1,q2, , , qi不在Q中，那么把它置为为标记后参加到 Q中；如果p1,p2, ,pi中至少有一个是 M的终 态，那么同时把p1,p2, , ,pi参加到F中；然后给 Q中所有的状态都标记为止；4. 重复执行3，直到不能向Q中参加新状态，并且Q中所有的状态都有标
3、记为止；5. 重新命名 Q中的状态，最后获得等价的DFA M。二、对含&变迁的NFA确实定化：1.置Q , F为空集；2.令q0 = _CLOSURE(q0),并把q0置为未标记后参加到 Q中；3.如果Q中存在未标记状态q1,q2, , ,qi,那么对每个 aE定义：d (q1,q2, qi,a)=p1,p2, ,pj当且仅当d(q1,q2,qi,a)=r1,r2,rk,_CLOSURE(r1,r2, , ,rk)=p1,p2, , ,pj。如果p1,p2, , ,pj不在 Q 中，那么把它置为未标记后参加到 Q中；如果p1,p2, , ,pj中至少有一个是 M的终态，那么同时把p1,p2,
4、,pj 参加到F中；然后给 Q中的状态q1,q2, , ,qi加上标记；4. 重复执行3,直到不能向 Q中参加新状态，并且Q中所有的状态都有标记为止；5. 重新命名 Q中的状态，然后获得等价的 DFA M三 数据构造struct edgestring first;string change; string last;struct chan string ltab; string jiheMAXS;四 源代码#include #include #define MAXS 100 using namespace std; string NODE; / 结点集合 string CHANGE; / 终结
5、符集合 int N; /NFA 边数 struct edgestring first;string change; string last;struct chan string ltab; string jiheMAXS;void kong(int a)int i;for(i=0;ia;i+) cout ; /排序 void paixu(string &a) int i,j; char b;for(j=0;ja.length();j+) for(i=0;iNODE.find(ai+1) b=ai; ai=ai+1; ai+1=b;void eclouse(char c,string &he,e
6、dge b)int k;for(k=0;khe.length() he+=bk.last;eclouse(bk.last0,he,b);void move(chan &he,int m,edge b)int i,j,k,l;l=he.jihem.length();for(i=0;ik;i+) for(j=0;jhe.jihem.length() he.jihem+=bj.last0;for(i=0;il;i+) for(j=0;jhe.jihem.length() he.jihem+=bj.last0;/输出void outputfa(int len,int h,chan *t)int i,j
7、,m;cout I ;for(i=0;ilen;i+)coutICHANGEi ;coutendlendl;for(i=0;ih;i+)cout ti.ltab;m=ti.ltab.length();for(j=0;jlen;j+)kong(8-m);m=ti.jihej.length();coutti.jihej;coutendl;void main()edge *b=new edgeMAXS;int i,j,k,m,n,h,x,y,len;bool flag;endl;string jhMAXS,endnode,ednode,sta;cout请输入NFA各边信息起点 条件空为*终点，以#完
8、毕:for(i=0;ibi.first;if(bi.first=#) break;cinbi.changebi.last;N=i;/*for(j=0;jN;j+) coutbj.firstbj.changebj.lastendl;*/ for(i=0;iNODE.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();cou
9、t 结点中属于终态的是:endnode;for(i=0;iNODE.length() cout 所输终态不在集合中，错误！ endl;return;/coutendnode=endnodeendl;chan *t=new chanMAXS;t0.ltab=b0.first;h=1;eclouse(b0.first0,t0.ltab,b); / 求 e-clouse/coutt0.ltabendl;for(i=0;ih;i+)for(j=0;jti.ltab.length();j+)for(m=0;mlen;m+)eclouse(ti.ltabj,ti.jihem,b); / 求 e-clous
10、e for(k=0;klen;k+)/coutti.jihek;move(ti,k,b); / 求 move(I,a)/coutti.jihekendl;for(j=0;jti.jihek.length();j+)eclouse(ti.jihekj,ti.jihek,b); / 求 e-clouse for(j=0;jlen;j+)paixu(ti.jihej); / 对集合排序以便比拟 for(k=0;kh;k+)flag=operator=(tk.ltab,ti.jihej);if(flag)break;if(!flag&ti.jihej.length()th+.ltab=ti.jihej
11、;coutendl 状态转换矩阵如下： endl;outputfa(len,h,t); / 输出状态转换矩阵/状态重新命名string *d=new stringh;NODE.erase();coutendl 重命名： endl;for(i=0;ih;i+)sta=ti.ltab;ti.ltab.erase();ti.ltab=A+i;NODE+=ti.ltab;coutsta=ti.ltabendl;for(j=0;jendnode.length();j+)if(sta.find(endnodej)sta.length()d1=ednode+=ti.ltab; for(k=0;kh;k+)
12、for(m=0;mlen;m+) if(sta=tk.jihem) tk.jihem=ti.ltab;for(i=0;iednode.length() d0+=NODEi;endnode=ednode; coutendlDFA 如下： endl; outputfa(len,h,t); / 输出 DFA cout 其中终态为： endnodeendl; /DFA 最小化 m=2;sta.erase();flag=0;for(i=0;im;i+)/coutdi=diendl; for(k=0;klen;k+)/coutICHANGEkendl;y=m;for(j=0;jdi.length();j+
13、)for(n=0;ny;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);/coutdiendl;j-;break; / 跳出 n/n/jif(flag)m+;flag=0;/coutsta=staendl;sta.erase();/k/ic
14、outendl 集合划分： ;for(i=0;im;i+)coutdi ;coutendl;/状态重新命名chan *md=new chanm;NODE.erase();coutendl 重命名： endl;for(i=0;im;i+)mdi.ltab=A+i;NODE+=mdi.ltab; coutdi=mdi.ltabendl;for(i=0;im;i+)for(k=0;klen;k+)for(j=0;jh;j+)if(di0=tj.ltab0)for(n=0;nm;n+)if(!tj.jihek.length() break;elseif(dn.find(tj.jihek)dn.leng
15、th() mdi.jihek=md n .Itab; break; break;edno de.erase();for(i=0;im;i+)for(j=0;je ndnode.len gth();j+)if(di.fi nd(e ndn odej)di.le ngth()&ed node.fi nd(mdi.ltab)edno de+=mdi.ltab;endnode=ednode;coutendl最小化 DFA 如下：endl; outputfa(le n,m ,md);cout其中终态为：e ndno dee ndl;输入:输出:DEFEEFFGFGEF戶中煤态为* 康合划分m flO CG重命名; 哂 =BBJ =C =P-E最小化DFft如下tI 11 00CBEBCnDDDED0真中烬态为：BEPiess mny kmy tocont inue.四实验体会通过本次实验进一步的了解并掌握 NFA确定化的运用，同时发现自己对关于 NFA的很多 知识不是很熟，运用的也不好。但是通过和同学的配合和学习知道了NFA，DFA的本质内容及其功能，以后会更多的学习这些知识，更好的掌握和熟练的运用所学的知识。