不确定有穷状态自动机的确定化实验报告

.word教育资料编译原理实验报告(二)E01214055鲁庆河1.实验名称：不确定有穷状态自动机的确定化2.实验目的：a)输入：非确定有穷状态自动机NFAb)输出：确定化的有穷状态自动机DFA3.实验原理：a)NFA确定化为DFA同一个字符串α可以由多条通路产生，而在实际应用中，作为描述控制过程的自动机，通常都是确定有限自动机DFA，因此这就需要将不确定有限自动机转换成等价的确定有限自动机，这个过程称为不确定有限自动机的确定化，即NFA确定化为DFA。b)NFA的确定化算法-----子集法：若NFA的全部初态为S1，S2，…，Sn，则令DFA的初态为：S＝[S1，S2，…，Sn]，其中方括号用来表示若干个状态构成的某一状态。设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中。重复第2步，直到K中不再有新的状态加入为止。上面得到的所有状态构成DFA的状态集K，转换函数构成DFA的F，DFA的字母表仍然是NFA的字母表∑。DFA中凡是含有NFA终态的状态都是DFA的终态。c)closure（I）函数，move(I,a)函数的假设I是NFAM状态集K的一个子集（即I∈K），则定义ε-closure（I）为：1.若Q∈I，则Q∈ε-closure（I）；2.若Q∈I，则从Q出发经过任意条ε弧而能到达的任何状态Q’，则Q’∈closure（I）。3.状态集ε-closure（I）称为状态I的ε闭包。假设NFAM＝(K,∑,F,S,Z),若I∈K，a∈∑,则定义Ia＝closure（J）,其中J是所有从closure（I）出发,经过一条a弧而到达的状态集。NFA确定化的实质是以原有状态集上的子集作为DFA上的一个状态,将原状态间的转换为该子集间的转换，从而把不确定有限自动机确定化。经过确定化后，状态数可能增加,而且可能出现一些等价状态，这时就需要简化。4.实验思路：(数据结构及变量设计等).word教育资料5.实验小结：在写此次试验之初，数据结构设计是这样的，K,E,S,Z都用一位字符数组存储，F用下面的链表存储，但是最终在写move函数时查找J集合麻烦，加之数据结构算法的实现基本功不够，在同学的指点下就从新定义了数据结构。在新的数据结构中，使用邻接表来存储转换函数的，虽然数据结构部分对于顺序表链表邻接表的操作很陌生，但通过此次的实验让我对于数据结构中邻接表的使用有了很好的复习和回顾，也学会了邻接表中指针的使用和插入删除操作…….word教育资料此次实验过程中，代码虽然全部都是本人自己编写，但很多不是我自己的思想，是从同学那剽窃来理解消化的，在别人和我讲述了代码之后，我自己独立的去写时，细节的地方仍然是漏洞百出，到处出错。我的代码能力太差，也常常因为这而自卑，但也不知如何去提升，虽然课本上的确定化会写，算法也能够理解和掌握，但是实现起来就是无从下手，所以动手能力差的同时，书本知识也得不到强化。我会借编译原理实验的机会慢慢的熟悉代码，自己去想通算法，自己去实现算法。我很感激姚老师的严厉要求，我相信我们院的老师都要像您和王爱平老师这样的就好了！6.附件：（程序和运行结果截图）a)程序：#includestdlib.h#includemalloc.h#includestdio.h#includeconio.h#defineN20//用于控制数组的最大长度//用邻接表存储NFA和DFA的状态字母后继typedefstructadjvex{//定义邻接表的邻接点域的数据表示charnextstate;//头结点状态的后继状态chararc;//弧structadjvex*next;//指向该头结点状态的下一个后继状态的指针}adjvex;typedefstructheadvex{//定义邻接表的头部的数据表示charstate;//状态adjvex*firstarc;//指向第一个后继状态的指针}headvex;//定义两个邻接表的头部，为全局数组headvexNFA[N];//用邻接表存储的NFAheadvexDFA[N];//用邻接表存储的DFAcharAlp[N];//存储需要输入的行为集，即字母表voidmain(){voiddesignby();//函数声明voidclosure(chars,charset[N]);//求e_closure闭包函数voidSpecial(charDFA_start[N],charnew_state[N][N]);//确定化函数designby();inti,j;charNFA_start[N];//存放NFA的初态charDFA_start[N];//存放DFA的初态charNFA_final[N];//存放NFA的终态charDFA_final[N];//存放DFA的终态charnew_state[N][N];//存放DFA的I的二维数组每一行为一个原NFA的一个新的状态集，e-closure(move(I,a))for(i=0;iN;i++){NFA[i].state='#';NFA[i].firstarc=NULL;DFA[i].state='#';DFA[i].firstarc=NULL;Alp[i]='#';NFA_start[i]='#';DFA_start[i]='#';NFA_final[i]='#';DFA_final[i]='#';for(j=0;jN;j++)new_state[i][j]='#';}intm,n;printf(请输入NFA:状态的个数:[]\b\b\b);scanf(%d,&n);fflush(stdin);printf(状态转换个数:[]\b\b\b);scanf(%d,&m);fflush(stdin);printf(请输入各状态:(状态,0/1/2)，终态输2，非初终态输1,初态输0.\n);//创建邻接表intf;.word教育资料for(i=0;in;i++)//n个状态的输入,依次存储到已开辟空间的邻接表头结点中，并根据状态分类装入NFA的初态终态数组中.{printf(状态%d：,i+1);scanf(%c,%d,&NFA[i].state,&f);fflush(stdin);if(f==0)//输入状态若为初态,依次存入到NFA_start[N]数组中{for(j=0;jN&&NFA_start[j]!='#';j++);NFA_start[j]=NFA[i].state;}if(f==2)//输入状态若为终态,依次存入到NFA_final[N]数组中{for(j=0;jN&&NFA_final[j]!='#';j++);NFA_final[j]=NFA[i].state;}}printf(输入完毕!\n\n);printf(请输入状态转换函数:(状态1,状态2,输入字符)\n);adjvex*p;//定义一个指向adjvex的指针pcharfrom,to,arc;intk;for(i=0;im;i++)//m个转换函数的输入,开辟空间并依次存储至相应头结点状态的邻接表中.{printf(状态转换%d：,i+1);scanf(%c,%c,%c,&from,&to,&arc);fflush(stdin);p=(adjvex*)malloc(sizeof(adjvex));p-nextstate=to;p-arc=arc;for(k=0;NFA[k].state!=from;k++);//结束时k的值即为匹配状态所在的头结点p-next=NFA[k].firstarc;//前插法插入结点到头结点后NFA[k].firstarc=p;//前插法插入结点到头结点后if(arc!='$')//输入字符不为空，保存到Alps[N]字母表中{for(j=0;jN&&Alp[j]!='#';j++)if(arc==Alp[j])break;//存在则跳出，结束不保存//上循环结束的两个可能:1、该输入字符已经存在于字母表中不存跳出，则下面的if也不会成立；//2、从0开始到#结束都没找不到一样的字母，结束for，记下了j.if(Alp[j]=='#')Alp[j]=arc;}}printf(输入完毕!\n\n);//求所有NFA_start[N]中所有初态的closure形成总的初态DFA_start[N]//charstart[N][N];//for(i=0;iN;i++)//for(j=0;jN;j++)//start[i][j]='#';//for(i=0;NFA_start[i]!='#';i++)//依次对每个NFA初态求等价状态放在二维数组中//closure(NFA_start[i],DFA_start);/*intk;for(i=0;NFA_start[i]!='#';i++)//将start二维数组变到一位数组DFA_start[N]中for(j=0;start[i][j]!='#';j++){k=0;for(k=0;DFA_start[k]!=start[i][j]&&DFA_start[k]!='#';k++);if(DFA_start[k]=='#')DFA_start[k]=start[i][j];elsecontinue;}*/k=0;while(NFA[k].state!=NFA_start[0])k++;closure(NFA[k].state,DFA_start);//求初态的e_closure闭包//for(intz=0;zN;z++).word教育资料//printf(%4c%4c\n,NFA_start[z],DFA_start[z]);Special(DFA_start,new_state);//有DFA_start[N],即为new_state[0]通过对NFA[N]邻接表依次求//for(z=0;zN;z++)//{//printf(%s\n,new_state[z]);//}k=0;for(i=0;iN&&new_state[i][0]!='#';i++)//寻找DFA的终态{for(j=0;jN&&new_state[i][j]!='#';j++){for(f=0;fN&&NFA_final[f]!='#';f++)if(new_state[i][j]==NFA_final[f]){DFA_final[k]=i+65;k++;break;}if(new_state[i][j]==NFA_final[f])break;}}//NFA和DFA的输出：k=0;for(i=0;iN&&new_state[i][0]!='#';i++)//寻找DFA的终态for(j=0;jN&&new_state[i][j]!='#';j++){for(f=0;fN&&NFA_final[f]!='#';f++)if(new_state[i][j]==NFA_final[f]){DFA_final[k]=i+65;k++;break;}if(new_state[i][j]==NFA_final[f])break;}printf(确定化后的DFA如下所示:\n);printf();for(i=0;Alp[i]!='#';i++)printf(%3c,Alp[i]);printf(初终);printf(\n);for(i=0;DFA[i].state!='#';i++)//以矩阵形式输出DFA{printf(%4c,DFA[i].state);for(j=0;Alp[j]!='#';j++){p=DFA[i].firstarc;while(p){if(p-arc==Alp[