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

1、编译原理实验报告(二)E01214055鲁庆河1. 实验名称：不确定有穷状态自动机的确定化2. 实验目的：a) 输入：非确定有穷状态自动机NFAb) 输出：确定化的有穷状态自动机DFA3. 实验原理：a) NFA确定化为DFA同一个字符串a可以由多条通路产生， 而在实际应用中，作为描述控制过程的自动机， 通常都是确定有限自动机 DFA 因此这就需要将不确定有限自动机转换成等价的确定有限自动机，这个过程称为不确定有限自动机的确定化，即NFA确定化为DFAb) NFA的确定化算法-子集法：若NFA的全部初态为Si，S2，S，则令DFA的初态为：S=Sl，S2，Sn，其中方括号用来表示若干个状态构成

2、的某一状态。设DFA的状态集K中有一状态为Si，Si+i，Sj，若对某符号aE，在NFA中有F ( S，S+i，S ，a) = Si，S+1，S ,则令 F ( Si，S+1，S ，a) = Si，S+i，s 为 DFA 的一个转换函数。 若S i，Si+1 ，S 不在K中，则将其作为新的状态加入到K中。重复第2步，直到K中不再有新的状态加入为止。上面得到的所有状态构成 DFA的状态集K，转换函数构成 DFA的F，DFA的字母表仍然是 NFA的字母表刀。 DFA中凡是含有NFA终态的状态都是 DFA的终态。c) closure (I)函数，move(l,a)函数的假设I是NFA Ml状态集K的

3、一个子集(即I K)，则定义 -closure (I )为：1. 若 Q I，贝U QCe -closure (I)；2. 若Q I，则从Q出发经过任意条弧而能到达的任何状态Q，则Q closure (I)。3. 状态集 -closure (I )称为状态I的闭包。假设NFA g ( K,刀,F,S,Z ),若I K，aE ,则定义I a= closure (J),其中J是所有从closure (I)出发，经过一 条a弧而到达的状态集。NFA确定化的实质是以原有状态集上的子集作为DFA上的一个状态，将原状态间的转换为该子集间的转换，从而把不确定有限自动机确定化。经过确定化后，状态数可能增加，而

4、且可能出现一些等价状态，这时就需要简化。4.实验思路：(数据结构及变量设计等)typedef struct adjvexRchar arc;struct adjvex nex匸；vex;typedef st met headvexchar s匸ate;adjvex *firstarc:1-/headvex;charNFA_staztN|;i Z_J：_, 1 / J - VMVWyVYm ghincWZZZEZcharDFA_startN;WmVmVm charNFA_finaL 阳；ArAAAAAAflj-charDFA_.final N;charnew3tateN| N / / Jfewv

5、oidrrain ()，彳1|3* R田void cl os are ichar s f alhar set N )/*K 一个状木m綽过仟寺逹统个的手列1所至1沃的等价状水的：W 合吕e tFHi 一句屯白号即7Z1Ivoid move(char FrcmfNJ 申 char arcf char ToN、iSiiBPrWrVAWwVWi*田void Order(char aNJ)丰FSl斗田void Special i char DFA_start N f char 11 皂w_st.ate IN N)”二一Hlvoid designbyi：|S15.实验小结：在写此次试验之初，数据结构设计

6、是这样的，K,E,S,Z都用一位字符数组存储，F用下面的链表存储，但是最终在写move函数时查找J集合麻烦，加之数据结构算法的实现基本功不够，在同学的指点下就从新定义了数据结构。typedef struct transforms%*AKHicharI；charE;aliarI_E1CJ;struct transforias next;L j 匸工ansf omisi;在新的数据结构中，使用邻接表来存储转换函数的，虽然数据结构部分对于顺序表链表 邻接表的操作很陌生，但通过此次的实验让我对于数据结构中邻接表的使用有了很好的复习和回顾，也学会了邻接表中指针的使用和插入删除操作WWM-typedef

7、stimct adjvexEHchar nexcstate;char arc;struct adjvsx next;J adjveK；typedef stT?uct headvexchar stae;adjvex 七 firstarc;Js !希n 广 rs =4*rg q rAXXAW*AAAAiVVXAiiV*AAAAAAAXWXjSVWWiH?VHAAAAAAAAheadvex;此次实验过程中，代码虽然全部都是本人自己编写， 但很多不是我自己的思想，是从同学那 剽窃来理解消化的，在别人和我讲述了代码之后，我自己独立的去写时，细节的地方仍然是漏 洞百出，到处出错。我的代码能力太差，也常常因

8、为这而自卑，但也不知如何去提升，虽然课 本上的确定化会写，算法也能够理解和掌握，但是实现起来就是无从下手，所以动手能力差的 同时，书本知识也得不到强化。我会借编译原理实验的机会慢慢的熟悉代码，自己去想通算法，自己去实现算法。我很感激姚老师的严厉要求，我相信我们院的老师都要像您和王爱平老师这样的就好了！存放NFA的初态存放DFA的初态存放NFA的终态存放DFA的终态char new_stateNN;存放DFA的I的二维数组 每一6附件：(程序和运行结果截图)a)程序：#include #include #include #include #define N 20 /用于控制数组的最大长度/用邻接

9、表存储NFA和DFA的状态 字母 后继typedef struct adjvex定义邻接表的邻接点域的数据表示char n extstate;/头结点状态的后继状态char arc;/ 弧struct adjvex *next;/ 指向该头结点状态的下一个后继状态的指针adjvex;typedef struct headvex/定义邻接表的头部的数据表示char state;/ 状态adjvex *firstarc;/ 指向第一个后继状态的指针headvex;/定义两个邻接表的头部，为全局数组headvex NFAN; 用邻接表存储的NFAheadvex DFAN;/ 用邻接表存储的DFAch

10、ar AlpN;/存储需要输入的行为集，即字母表void mai n()void desig nby();函数声明void closure(char s,char setN);/求 e_closure 闭包函数voidSpecial(charDFA_startN,charn ew_stateNN);确定化函数designby();int i,j;char NFA_startN;/ char DFA_startN;/ char NFA_fi nalN;/ char DFA_fi nalN;/行为一个原NFA的一个新的状态集，e-closure(move(I,a)for(i=0; iN; i+)N

11、FAi.state=#;NFAi.firstarc=NULL;DFAi.state=#;DFAi.firstarc=NULL;Alpi=#;NFA_starti=#;DFA_starti=#;NFA_finali=#;DFA_finali=#;for(j=0; jN; j+)new_stateij=#;int m,n;printf( 请输入NFA:状态的个数:bbb);scanf(%d,&n);fflush(stdin);printf(状态转换个数:bbb);scanf(%d,&m);fflush(stdin);printf(”请输入各状态:(状态,0/1/2)，终态输2,非初终态输1,初态输

12、0.n);创建邻接表int f;for(i=0; in; i+)/n个状态的输入，依次存储到已开辟空间的邻接表头结点中，并根据状态分类装入NFA的初态终态数组中.printf(状态 %d ,i+1);sea nf(%c,%d,&N FAi.state, &f);fflush(stdi n);if(f=0)/ 输入状态若为初态，依次存入到NFA_startN数组中for(j=0; jN & NFA_startj!=#;j+); NFA_startj=NFAi.state;if(f=2)/ 输入状态若为终态，依次存入到NFA_fin alN数组中for(j=0; jN & NFA_fi nalj!

13、=# ;j+);NFA_fi nalj=NFAi.state;printf(输入完毕!nn);printf(请输入状态转换函数:(状态1,状态2,输入字 符)n);adjvex *p;/ 定义一个指向adjvex的指针pchar from,to,arc;int k;for(i=0; i nextstate=to;p-arc=arc;for(k=0; NFAk.state!=from; k+);/结束时 k的值即为匹配状态所在的头结点p- next=NFAk.firstarc;前插法插入结点到头结点后NFAk.firstarc=p;前插法插入结点到头结点后if(arc!=$)/输入字符不为空，保

14、存到 AlpsN字母表中for(j=0; jN & Alpj!=#;j+)if(arc=Alpj)break;/存在则跳出，结束不 保存/上循环结束的两个可能：1、该输入 字符已经存在于字母表中不存跳出，则下面的if也不会成立；/2、从0开始到#结束都没找不到一样的字母，结束for，记下了 j.if(Alpj=#) Alpj=arc;printf(”输入完毕!nn);/求所有NFA_startN中所有初态的closure形成总的 初态 DFA_startN/char startNN;/for(i=0; iN; i+)/ for(j=0; jN; j+)/startij=#;/for(i=0;

15、NFA_starti!=#; i+)/依次对每个 NFA初态求等价状态放在二维数组中/ closure(NFA_starti,DFA_start);/*int k;for(i=0;NFA_starti!=#;i+)/ 将 start 二维数组变到一位数组 DFA_startN中for(j=0; startij!=#; j+)k=0;for(k=0;DFA_startk!=startij&DFA_startk!=#;k+);if(DFA_startk=#)DFA_startk=startij;else continue;*/k=0;while(NFAk.state!=NFA_start0)k+;

16、closure(NFAk.state,DFA_start);/求初态的e_closure 闭包/for(i nt z=0; zN; z+)printf(%4c %4cn,NFA_startz,DFA_start z);Special(DFA_start,new_state);有 DFA_startN,即为new_state0通过对NFAN邻接表依次求/for(z=0;zN; z+)/pri ntf(%sn, new_state z);/k=0;for(i=0;iN&new_statei0!=#;i+)寻找 DFA的终态for(j=0;jN &n ew_stateij!=# ;j+)for(f=

17、 0;f N& NFA_fin alf!=# ;f+)if(n ew_stateij=NFA_fi nalf)DFA_fi nalk=i+65;k+;break;if(n ew_stateij=NFA_fi nalf)break;/NFA和DFA的输出:k=0;for(i=0;iN&new_statei0!=#;i+)寻找 DFA的终态for(j=0;jN &n ew_stateij!=# ;j+)for(f= 0;farc=Alpj)prin tf(%3c,p- nextstate);break;elsep=p-next;if(p=NULL)printf();for(k=0;k N&DFA_

18、finalk!=#;k+) if(DFAi.state=DFA_finalk) break;if(DFA_finalk=#)printf( 0);elseprintf( 1);printf(n);printf(每个新的状态对应的原状态子集如下：n);输岀对应的NFA子集for(i=0;iN &new_statei0!=#;i+)printf(%3c,i+65);printf( );for(j=0;jN &new_stateij+1!=#;j+)printf(%c,new_stateij);printf(%c,new_stateij);printf(n);printf(新的终态如下：n);for

19、(i=0;iarc=$)closure(p-nextstate,set);若 为空弧的话，递归进入该后继状态所对应的头结点状态处依次查找其空弧后继，查找结束回到上一层后继状态继续查找p=p- n ext;elsep=p-next;查看该头结点状态的下一个后继状态return;void move(char FromN,char arc,char ToN)找一个状态集FromN的所有状态的arc后继状态的集合ToNint i,j,k,t=0;adjvex *p;j=0; 首先定义j为0for(i=0; iarc=arc)for(k=0; kn extstate) p=p-n ext;break;/

20、该状态若已存 在ToN中，跳出循环不保存，移动指针查看下一个后继状态if(Tok=#)直达结束没有发现已经存入，Tot+=p-n extstate; p=p- n ext;else p=p-n ext;void Order(char aN)/由小到大对数组中的每个字符排序int i,j;char temp;for(i=0;iN &ai!=#;i+)for(j=i+1;j N&aj!=#;j+)if(ajai)temp=ai;ai=aj;aj=temp;void Special(char DFA_startN,char new_stateNN)int i,j;char To1N,To2N;cha

21、r order1N,order2N;for(i=0; iN; i+)To1i=#;To2i=#;for(i=0; iN & DFA_starti!=#;i+)new_state0i=DFA_starti;将DFA_startN复制到 new_state0,作为一个状态int st,k,t;adjvex *p;for(st=0; stN & new_statest0!=#： st+ )DFAst.state=st+65;for(i=0; Alpi!=#; i+)for(k=0; kN; k+)To1k=#;To2k=#：每次使用TO1 To2都要清除原有数据move( new_statest,Alpi,To1);for(j=0;To1j!=#;j+)循环求状态集的closure闭包(求每一个状态的closure 时，都会对上一个 状态得到的To2N从头找不相同的存进去)closure (T o1j,To2);for(j=0;jN&n ew_statej0!=#;j+)/ 将 new_state 禾口 closure( move(I,a)转存到两个新数组中，排序比较是否已经存在此状态集合，以 防出错for(k=0; kN; k+)order1k=n ew_