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

编译原理实验报告实验名称不确定有限状态自动机的确定化实验时间院系计算机科学与技术学院班级学号姓名1.试验目的输入：非确定有限（穷）状态自动机。输出：确定化的有限（穷）状态自动机2.实验原理一个确定的有限自动机（DFA）M可以定义为一个五元组，M＝（K，∑，F，S，Z），其中：（1）K是一个有穷非空集，集合中的每个元素称为一个状态；（2）∑是一个有穷字母表，∑中的每个元素称为一个输入符号；（3）F是一个从K×∑→K的单值转换函数，即F（R，a）＝Q，（R，Q∈K）表示当前状态为R，如果输入字符a，则转到状态Q，状态Q称为状态R的后继状态；（4）S∈K，是惟一的初态；（5）ZK，是一个终态集。由定义可见，确定有限自动机只有惟一的一个初态，但可以有多个终态，每个状态对字母表中的任一输入符号，最多只有一个后继状态。对于DFAM，若存在一条从某个初态结点到某一个终态结点的通路，则称这条通路上的所有弧的标记符连接形成的字符串可为DFAM所接受。若M的初态结点同时又是终态结点，则称ε可为M所接受（或识别），DFAM所能接受的全部字符串（字）组成的集合记作L（M）。一个不确定有限自动机（NFA）M可以定义为一个五元组，M＝（K，∑，F，S，Z），其中：（1）k是一个有穷非空集，集合中的每个元素称为一个状态；（2）∑是一个有穷字母表，∑中的每个元素称为一个输入符号；（3）F是一个从K×∑→K的子集的转换函数；（4）SK，是一个非空的初态集；（5）ZK，是一个终态集。由定义可见，不确定有限自动机NFA与确定有限自动机DFA的主要区别是：（1）NFA的初始状态S为一个状态集，即允许有多个初始状态；（2）NFA中允许状态在某输出边上有相同的符号，即对同一个输入符号可以有多个后继状态。即DFA中的F是单值函数，而NFA中的F是多值函数。因此，可以将确定有限自动机DFA看作是不确定有限自动机NFA的特例。和DFA一样，NFA也可以用矩阵和状态转换图来表示。对于NFAM，若存在一条从某个初态结点到某一个终态结点的通路，则称这条通路上的所有弧的标记（ε除外）连接形成的字符串可为M所接受。NFAM所能接受的全部字符串（字）组成的集合记作L（M）。由于DFA是NFA的特例，所以能被DFA所接受的符号串必能被NFA所接受。设M1和M2是同一个字母集∑上的有限自动机，若L（M1）＝L（M2），则称有限自动机M1和M2等价。由以上定义可知，若两个自动机能够接受相同的语言，则称这两个自动机等价。DFA是NFA的特例，因此对于每一个NFAM1总存在一个DFAM2，使得L（M1）＝L（M2）。即一个不确定有限自动机能接受的语言总可以找到一个等价的确定有限自动机来接受该语言。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的终态。对于上述NFA确定化算法——子集法，还可以采用另一种操作性更强的描述方式，下面我们给出其详细描述。首先给出两个相关定义。假设I是NFAM状态集K的一个子集（即I∈K），则定义ε-closure（I）为：（1）若Q∈I，则Q∈ε-closure（I）；（2）若Q∈I，则从Q出发经过任意条ε弧而能到达的任何状态Q’，则Q’∈ε-closure（I）。状态集ε-closure（I）称为状态I的ε闭包。假设NFAM＝（K，∑，F，S，Z），若I∈K，a∈∑，则定义Ia＝ε-closure（J），其中J是所有从ε-closure（I）出发，经过一条a弧而到达的状态集。NFA确定化的实质是以原有状态集上的子集作为DFA上的一个状态，将原状态间的转换为该子集间的转换，从而把不确定有限自动机确定化。经过确定化后，状态数可能增加，而且可能出现一些等价状态，这时就需要简化。3..实验内容输入：非确定有限（穷）状态自动机。输出：确定化的有限（穷）状态自动机4.实验心得5.实验代码与结果#includeiostream#includestring#includevectorusingnamespacestd;#definemax100structedge{stringfirst;//边的初始结点stringchange;//边的条件stringlast;//边的终点};intN;//NFA的边数vectorintvalue;stringclosure(stringa,edge*b){inti,j;for(i=0;ia.length();i++){for(j=0;jN;j++){if(b[j].first[0]==a[i]&&b[j].change==&){a=a+b[j].last[0];}}}returna;}stringmove(stringjihe,charch,edge*b){inti,j;strings=;for(i=0;ijihe.length();i++){for(j=0;jN;j++){if(b[j].first[0]==jihe[i]&&b[j].change[0]==ch)s=s+b[j].last;}}returns;}stringsort(stringt){intk,i,j;chartt;for(i=0;it.length()-1;i++){k=i;for(j=i+1;jt.length();j++){if(t[j]t[k])k=j;}tt=t[k];t[k]=t[i];t[i]=tt;}returnt;}voidmain(){inti,j,x=0,h,length,m,d=0;stringChange;stringFirst,Last;//初态，终态，stringT[max],ss;edge*b=newedge[max];cout请输入各边信息：起点条件（空用&表示）终点，以输入#结束。endl;for(i=0;imax;i++){cinb[i].first;if(b[i].first==#)break;elsecinb[i].changeb[i].last;}N=i;cout请输入该NFA的初态及终态：endl;cinFirstLast;cout请输入此NFA状态中的输入符号即边上的条件:endl;cinChange;T[x]=closure(First,b);T[x]=sort(T[x]);value.push_back(0);i=0;while(value[i]==0&&value.size()){value[i]=1;for(j=0;jChange.length();j++){ss=;ss=move(T[i],Change[j],b);length=value.size();for(h=0;hlength;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;jChange.length();j++){DFA[d].first=T[i];DFA[d].change=Change[j];ss=;ss=sort(closure(move(T[i],Change[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;id;i++){for(m=0;m=x;m++){if(DFA[i].first==T[m])coutmDFA[i].change;}for(m=0;m=x;m++)if(DFA[i].last==T[m])coutmendl;;}cout该DFA的初态为：;for(m=0;m=x;m++){for(j=0;jT[m].length();j++){ss=T[m];if(ss[j]==First[0])coutmendl;}}cout该DFA的终态为：;for(m=0;m=x;m++){for(j=0;jT[m].length();j++){ss=T[m];if(ss[j]==Last[0])coutm;}}coutendl;system(pause);}