NFA的确定化和最小化
一、实验名称NFA的确定化和最小化
二、实验原理
NFA，也称不确定的有穷自动机，是由一个五元式定义的数学模型，特点是它的不确定性，即在当前状态下，读入同一个字符，可能有多个下一状态。
DFA，也称确定的有穷自动机，也是由一个五元式定义的数学模型，相对的特点是它的确定性，即在当前状态下，读入同一个字符，最多有一个后继状态。
在非确定的有限自动机NFA中,由于某些状态的转移需从若干个可能的后续状态中进行选择，故一个NFA对符号串的识别就必然是一个试探的过程。这种不确定性给识别过程带来的反复，无疑会影响到FA的工作效率。而DFA则是确定的,将NFA转化为DFA将大大提高工作效率,因此将NFA转化为DFA是有其一定必要的。
得到新的DFA之后，并没有完成任务，因为通过NFA转化成DFA不一定是最简的，也就是说，有多余的状态可以被删除，而我们需要的是得到一个唯一的最简的DFA[12]，也就是说，NFA转化为DFA之后，还需要化简，也就是最小化。
DFA的化简是指：寻找一个状态数最少的DFA M，使得L（M）=L（M’）。化简的方法是消去DFA M中的多余状态（或无用状态），合并等价状态。
DFA中的多余状态是指这样的状态：从开始状态出发，读入任何输入串都不能到达的那个状态；或者从这个状态没有通路到达终态。
两个状态S 和T等价是指：如果从状态S出发能读出某个字W而停于终态，从T出发也能读出同样的字W而停于终态；反之，从T出发能读出同样的字W而停于终态，从S出发也能读出某个字W而停于终态。
化简DFA的基本思想是指导它的状态分成一些互不相交的子集，每一个子集中的状态都不是等价的，不同子集中的状态可以由某个输入串来区别，最后将不能区别的每个子集用一个状态来做代表[13-15]，这种方法称为“分割法”。具体过程是：
（1）将M的所有状态分成两个子集——终态集和非终态集；
（2）考察每一个子集，若发现某子集中的状态不等价，将其划分为两个集合；（3）重复第（2）步，继续考察已得到的每一个子集，直到没有任何一个子集需要继续划分为止。这时DFA的状态被分成若干个互不相交的子集。
（4）从每个子集中选出一个状态做代表即可得到最简的DFA。
三、实验目的要求
编写程序实现NFA的确定化（即NFA—>DFA）和最小化（即DFA的化简）
四、注意事项
输入一个NFA的各边信息，将其转化成DFA并化简，输入时，状态集不能为两个字符，例如不能出现“10”这样可能出错。
五、实验心得
NFA转化为与其等价的DFA需分两步进行：1、构造NFA的状态的子集的算法；2、计算ε-closure。完成这些子模块的设计后，再通过某一中间模块的总控程序对其调用，最后再由主程序总调用，也就实现了NFA转化为其等价的DFA，接下来就是以分割法的思想为指导实现DFA的化简。
通过本次实验，加深了对NFA和DFA的理解以及他们之间的相互关系，同时通过各种途径也略微提高了对Ｃ＋＋的认识和理解。尤其是对字符串的比较和显示等。
六、源程序代码
#include
#include
#define MAXS 100
using namespace std;
string NODE; //结点集合
string CHANGE; //终结符集合
int N; //NFA边数
struct edge{
string first;
string change;
string last;
};
struct chan{
string ltab;
string jihe[MAXS];
};
void kong(int a)
{
int i;
for(i=0;i cout<<' '; } //排序 void paixu(string &a) { int i,j; char b; for(j=0;j for(i=0;i if(NODE.find(a[i])>NODE.find(a[i+1])) { b=a[i]; a[i]=a[i+1]; a[i+1]=b; } } void eclouse(char c,string &he,edge b[]) { int k; for(k=0;k { if(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); } } } void move(chan &he,int m,edge b[]) { int i,j,k,l; k=he.ltab.length(); l=he.jihe[m].length(); for(i=0;i for(j=0;j if((CHANGE[m]==b[j].change[0])&&(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 for(j=0;j if((CHANGE[m]==b[j].change[0])&&(he.jihe[m][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]; } //输出 void outputfa(int len,int h,chan *t) { int i,j,m; cout<<" I "; for(i=0;i cout<<'I'< cout< for(i=0;i { cout<<' '< m=t[i].ltab.length(); for(j=0;j { kong(8-m); m=t[i].jihe[j].length(); cout< } cout< } } void main() { edge *b=new edge[MAXS]; int i,j,k,m,n,h,x,y,len; bool flag; string jh[MAXS],endnode,ednode,sta; cout<<"请输入NFA各边信息（起点条件[空为*] 终点），以#结束："< { cin>>b[i].first; if(b[i].first=="#") break; cin>>b[i].change>>b[i].last; } N=i; for(i=0;i { if(NODE.find(b[i].first)>NODE.length()) NODE+=b[i].first; if(NODE.find(b[i].last)>NODE.length()) NODE+=b[i].last; if((CHANGE.find(b[i].change)>CHANGE.length())&&(b[i].change!="*")) CHANGE+=b[i].change; } len=CHANGE.length(); cout<<"结点中属于终态的是："< cin>>endnode; for(i=0;i if(NODE.find(endnode[i])>NODE.length()) { cout<<"所输终态不在集合中，错误！"< return; } //cout<<"endnode="< chan *t=new chan[MAXS]; t[0].ltab=b[0].first; h=1; eclouse(b[0].first[0],t[0].ltab,b); //求e-clouse //cout< for(i=0;i { for(j=0;j for(m=0;m eclouse(t[i].ltab[j],t[i].jihe[m],b); //求e-clouse for(k=0;k { //cout< move(t[i],k,b); //求move(I,a) //cout< for(j=0;j eclouse(t[i].jihe[k][j],t[i].jihe[k],b); //求e-clouse } for(j=0;j { paixu(t[i].jihe[j]); //对集合排序以便比较 for(k=0;k { flag=operator==(t[k].ltab,t[i].jihe[j]); if(flag) break; } if(!flag&&t[i].jihe[j].length()) t[h++].ltab=t[i].jihe[j]; } } cout< //状态重新命名 string *d=new string[h]; NODE.erase(); cout< for(i=0;i { sta=t[i].ltab; t[i].ltab.erase(); t[i].ltab='A'+i; NODE+=t[i].ltab; cout<<'{'< for(j=0;j if(sta.find(endnode[j]) d[1]=ednode+=t[i].ltab; for(k=0;k for(m=0;m if(sta==t[k].jihe[m]) t[k].jihe[m]=t[i].ltab; } for(i=0;i if(ednode.find(NODE[i])>ednode.length()) d[0]+=NODE[i]; endnode=ednode; cout< cout<<"其中终态为："< //DFA最小化 m=2; sta.erase(); flag=0; for(i=0;i { //cout<<"d["< for(k=0;k { //cout<<"I"< y=m; for(j=0;j { for(n=0;n { if(d[n].find(t[NODE.find(d[i][j])].jihe[k]) { if(t[NODE.find(d[i][j])].jihe[k].length()==0) x=m; else x=n; if(!sta.length()) { sta+=x+48; } else if(sta[0]!=x+48) { d[m]+=d[i][j]; flag=1; d[i].erase(j,1); //cout< j--; } break; //跳出n } }//n }//j if(flag) { m++; flag=0; } //cout<<"sta="< sta.erase(); }//k }//i cout< for(i=0;i cout<<"{"< cout< //状态重新命名 chan *md=new chan[m]; NODE.erase(); cout< for(i=0;i { md[i].ltab='A'+i; NODE+=md[i].ltab; cout<<"{"< } for(i=0;i for(k=0;k for(j=0;j { if(d[i][0]==t[j].ltab[0]) { for(n=0;n { if(!t[j].jihe[k].length()) break; else if(d[n].find(t[j].jihe[k]) { md[i].jihe[k]=md[n].ltab; break; } } break; } } ednode.erase(); for(i=0;i for(j=0;j if(d[i].find(endnode[j]) endnode=ednode; cout< outputfa(len,m,md); cout<<"其中终态为："< } 七、实验截图