NFA到DFA的确定化及最小化.doc

《NFA到DFA的确定化及最小化.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、NFA转化为DFA的确定化及最小化一NFA向DFA的转换  从NFA的矩阵表示中可以看出，表项通常是一状态的集合，而在DFA的矩阵表示中，表项是一个状态，NFA到相应的DFA的构造的基本思路是： DFA的每一个状态对应NFA的一组状态.DFA使用它的状态记录在NFA读入一个输入符号后可能达到的所有状态.得到新的DFA之后，并没有完成任务，因为通过NFA转化成DFA不一定是最简的，也就是说，有多余的状态可以被删除，而我们需要的是得到一个唯一的最简的DFA[12]，也就是说，NFA转化为DFA之后，还需要化简，也就是最小化

2、。二NFA的确定化方法子集法：1．先把DFA M’中的Q’和F’置为空集； 2．M’的开始状态q0’=[q0]，把[q0]置为未标记后加入到Q’中； 3．如果Q’中存在未标记的状态[q1,q2,„，qi]，则对每个a∈∑定义：δ’([q1,q2,„，qi],a)=[p1,p2,„,pi]当且仅当δ({q1,q2,„，qi},a)={p1,p2,„,pi}。如果[q1,q2,„，qi]不在Q’中，则把它置为为标记后加入到Q’中；如果p1,p2,„,pi中至少有一个是M的终态，则同时把[p1,p2,„,pi]加入到F’中；

3、然后给Q’中所有的状态都标记为止； 4．重复执行（3），直到不能向Q’中加入新状态，并且Q’中所有的状态都有标记为止； 5. 重新命名Q’中的状态，最后获得等价的DFA M’。 二、对含ε变迁的NFA的确定化： 1．置Q’, F’为空集； 2．令q0’=[ε_CLOSURE({q0})],并把[q0]置为未标记后加入到Q’中； 3．如果Q’中存在未标记状态[q1,q2,„,qi],则对每个a∈∑定义：d‘([q1,q2,„qi],a)=[p1,p2,„,pj]当且仅当d({q1,q2,„qi},a)={r1,r2,„,

4、rk}, ε_CLOSURE({r1,r2,„,rk})= {p1,p2,„,pj}。如果[p1,p2,„,pj]不在Q’中，则把它置为未标记后加入到Q’中；如果p1,p2,„,pj中至少有一个是M的终态，则同时把[p1,p2,„,pj]加入到F’中；然后给Q’中的状态[q1,q2,„,qi]加上标记； 4．重复执行3，直到不能向Q’中加入新状态，并且Q’中所有的状态都有标记为止； 5．重新命名Q’中的状态，然后获得等价的DFA M’三数据结构structedge{stringfirst;stringchange;st

5、ringlast;};structchan{stringltab;stringjihe[MAXS];};四源代码#include#include#defineMAXS100usingnamespacestd;stringNODE;//结点集合stringCHANGE;//终结符集合intN;//NFA边数structedge{stringfirst;stringchange;stringlast;};structchan{stringltab;stringjihe[MAXS];};v

6、oidkong(inta){inti;for(i=0;iNODE.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

7、c==b[k].first[0])if(b[k].change=="*"){if(he.find(b[k].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

8、&(he.ltab[i]==b[j].first[0]))if(he.jihe[m].find(b[j].last[0])>he.jihe[m].length())he.jihe[m]+=b[j].last[0];for(i=0;i