确定的有穷自动机

本文格式为Word版，下载可任意编辑——确定的有穷自动机测验五：有穷自动机确实定化一：要求1.输入：

非确定有限（穷）状态自动机。

2.输出：

确定化的有限（穷）状态自动二：测验目的1.纯熟掌管DFA及NFA的定义及有关概念。

2.理解并掌管确定的有穷自动机的化简等算法。

三：测验原理1.由定义可见，不确定有限自动机NFA与确定有限自动机DFA的主要识别是：

（1）NFA的初始状态S为一个状态集，即允许有多个初始状态；

（2）NFA中允许状态在某输出边上有一致的符号，即对同一个输入符号可以有多个后继状态。即DFA中的F是单值函数，而NFA中的F是多值函数。

2.NFA确定化为DFA同一个字符串α可以由多条通路产生，而在实际应用中，作为描述操纵过程的自动机，通常都是确定有限自动机DFA，因此这就需要将不确定有限自动机转换成等价确实定有限自动机，这个过程称为不确定有限自动机确实定化，即NFA确定化为DFA。

下面介绍一种NFA确实定化算法，这种算法称为子集法：

（1）若NFA的全部初态为S1，S2，…，Sn，那么令DFA的初态为：

S＝[S1，S2，…，Sn]，其中方括号用来表示若干个状态构成的某一状态。

（2）设DFA的状态集K中有一状态为[Si，Si+1，…，Sj]，若对某符号a∈∑，在NFA中有F（{Si，Si+1，…，Sj}，a）={Si’，Si+1’，…，Sk’}那么令F（{Si，Si+1，…，Sj}，a）={Si’，Si+1’，…，Sk’}为DFA的一个转换函数。若[Si’，Si+1’，…，Sk‘]不在K中，那么将其作为新的状态参与到K中。

（3）重复第2步，直到K中不再有新的状态参与为止。

（4）上面得到的全体状态构成DFA的状态集K，转换函数构成DFA的F，DFA的字母表依旧是NFA的字母表∑。

（5）DFA中只要含有NFA终态的状态都是DFA的终态。

3.NFA确定化的实质是以原有状态集上的子集作为DFA上的一个状态，将原状态间的转换为该子集间的转换，从而把不确定有限自动机确定化。经过确定化后，状态数可能增加，而且可能展现一些等价状态，这时就需要简化。

四：数据布局与算法structedge{stringfirst;//边的初始结点stringcondition;//边上的条件stringlast;//边的终点};stringclosure(stringa,edge*b)//求状态集合I的#definemax100intn;//NFA的边数vectorvalue;structedge{stringfirst;//边的初始结点stringcondition;//边上的条件stringlast;//边的终点};stringclosure(stringa,edge*b)//求状态集合I的for(i=0;i>b[i].first;if(b[i].first==“#“)break;elsecin>>b[i].condition>>b[i].last;}n=i;cout>First>>Last;cout>Condition;T[x]=closure(First,b);//字符串数组存储空闭包并排序T[x]=sort(T[x]);value.push_back(0);i=0;while(value[i]==0for(j=0;j<Condition.length();j++){ss=““;ss=move(T[i],Condition[j],b);length=value.size();for(h=0;h<length;h++){if(T[h]==sort(closure(ss,b)))break;}if(h==length){T[++x]=sort(closure(ss,b));value.push_back(0);}}i++;}edge*DFA=newedge[max];for(i=0;i<=x;i++)//构造DFA的各边{for(j=0;j<Condition.length();j++){DFA[d].first=T[i];DFA[d].condition=Condition[j];ss=““;ss=sort(closure(move(T[i],Condition[j],b),b));for(m=0;m<=x;m++)if(ss==T[m])DFA[d++].last=T[m];}}cout<<“NFA构造的DFA的各边信息如下：“<<endl<<“起点条件终点“<<endl;for(i=0;i<d;i++){for(m=0;m<=x;m++){if(DFA[i].first==T[m])cout<<m<<““<<DFA[i].condition;}for(m=0;m<=x;m++)if(DFA[i].last==T[m])cout<<““<<m<<endl;;}cout<<“确定后的DFA的初态为：“;for(m=0;m<=x;m++){for(j=0;j<T[m].length();j++){ss=T[m];if(ss[j]==First[0])cout<<m<<endl;}}cout<<“确定后的DFA的终态为：“;for(m=0;