不确定有穷状态自动机地确定化试验报告材料

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

2、号用来表示假设干个状态构成的某一状态.设DFA的状态集K中有一状态为S S,+i,S,假设对某符号aE,在NFA中有F( S, S+i ,S, a) 一 '一'一'一 , A,_"一 '_'_'一一 一'= Si , S+1 ,Sk ,那么令 F ( S, S+1,Sj , a) = Si , S+i ,$ 为 DFA的一个转换函数.假设S , Si：,&'不在K中,那么将其作为新的状态参加到K中.重复第2步,直到K中不再有新的状态参加为止.上面得到的所有状态构成 DFA的状态集K,转换函数构成 DFA的F, D

3、FA的字母表仍然是 NFA的字母表万.DFA中但凡含有NFA终态的状态都是 DFA的终态.c) closure (I)函数,move(I,a)函数的假设I是NFA M犬态集K的一个子集(即I GK),那么定义£ -closure (I)为：1. 假设 QG I ,贝U QG e -closure (I)；2. 假设QG I ,那么从Q出发经过任意条£弧而能到达的任何状态Q',那么Q' e closure (I ).3. 状态集e -closure (I)称为状态I的e闭包.假设NFA M= ( K,汇,F,S,Z ),假设I G K, aE ,那么定义I a

4、= closure (J),其中J是所有从closure (I)出发,经过一 条a弧而到达的状态集.NFA确定化的实质是以原有状态集上的子集作为DFA上的一个状态,将原状态间的转换为该子集间的转换,从而把不确定有限自动机确定化.经过确定化后,状态数可能增加,而且可能出现一些等价状态,这时就需要简化.4 .实验思路：(数据结构及变量设计等)typedef struct adjvexR1char nextstate;char arc;struct adj vex nexT；;vex;typedef struct headvexchar 号七ate;adjvex *firstarc:.rieadve

5、x;文案大全实用标准文档charNFA_3tartN;1 _I -Xve_ _, , '1 ' 'J -囊的新太charD?A start：N：;一charNFA_finalN);AAAAAAflcharDFA_fi.nalN;charnew_5tate；NK /jffffltAaaaw*voidirat口 ()|3'"wAAAAAAAAflAvvoid closure(char sf char setN)RI: 旬延自身gn为门条交瓠AFMVWWAAAivoid move(char FrcmfNJ * char arcf char ToN>vo

6、id designbyi：IB :5 .实验小结：在写此次试验之初,数据结构设计是这样的,K,E,S,Z都用一位字符数组存储,F用下面的链表存储,但是最终在写move函数时查找J集合麻烦,加之数据结构算法的实现根本功不够,在同学的指点下就从新定义了数据结构.typedef struct transforms%*AK»EicharI；charE;aliarI_E 10J ；struct transforias next;l j transforms;在新的数据结构中,使用邻接表来存储转换函数的,虽然数据结构局部对于顺序表链表 邻接表的操作很陌生,但通过此次的实验让我对于数据结构中邻接表

7、的使用有了很好的复习和回忆,也学会了邻接表中指针的使用和插入删除操作EHtypedef stimat adjvexWW'iHiiiWW!BBWWWiAAAAAaBB»VWW'»WXAAA«a«lWXAXWB»VXAAAi!«i«WXA?V1»Wm fi Xt B t BtC HrvWWVWVWWWWVWWVWVWVWWahar arc;一struct adj vex *ne*r; ->adjveK；typedef stT?uct headvexAXWii?VXAAAiA?VVVaAAAAAAr

8、t?VWXjSHiVVVWiA/VHAAjWAAAA«char stats;adjvex . firstarc;hcadvex;文案大全实用标准文档此次实验过程中,代码虽然全部都是本人自己编写, 但很多不是我自己的思想,是从同学那 剽窃来理解消化的,在别人和我讲述了代码之后,我自己独立的去写时,细节的地方仍然是漏 洞百出,到处出错.我的代码水平太差,也常常由于这而自卑,但也不知如何去提升,虽然课 本上确实定化会写,算法也能够理解和掌握,但是实现起来就是无从下手,所以动手水平差的 同时,书本知识也得不到强化.我会借编译原理实验的时机慢慢的熟悉代码,自己去想通算法,自己去实现算法.我很感

9、谢姚老师的严厉要求,我相信我们院的老师都要像您和王爱平老师这样的就好了！存放NFA的初态存放DFA的初态存放NFA的终态存放DFA的终态char new_stateNN;/存放DFA的I的二维数组 每一6 .附件：(程序和运行结果截图)a)程序：#include <stdlib.h>#include <malloc.h>#include <stdio.h>#include <conio.h>#define N 20 /用于限制数组的最大长度/用邻接表存储NFA和DFA勺状态 字母 后继typedef struct adjvex/定义邻接表的邻接点

10、域的数据表示char nextstate;/头结点状态的后继状态char arc;/ 弧struct adjvex *next;/ 指向该头结点状态的下一个后继状态的指针adjvex;typedef struct headvex/定义邻接表的头部的数据表示char state;/ 状态adjvex *firstarc;/指向第一个后继状态的指针headvex;/定义两个邻接表的头部,为全局数组 headvex NFAN;/ 用邻接表存储的NFA headvex DFAN;/ 用邻接表存储的DFA char AlpN;/存储需要输入的行为集,即字母表void main()void designb

11、y();/函数声明void closure(char s,char setN);/求 e_closure 闭包函数voidSpecial(charDFA_startN,charnew_stateNN);/确定化函数designby();int i,j;char NFA_startN;/char DFA_startN;/char NFA_finalN;/char DFA_finalN;/行为一个原NFA的一个新的状态集,e-closure(move(I,a)for(i=0; i<N; i+)NFAi.state='#'NFAi.firstarc=NULL;DFAi.stat

12、e='#'DFAi.firstarc=NULL;Alpi='#'NFA_starti='#'DFA_starti='#'NFA_finali='#'DFA_finali='#'for(j=0; j<N; j+)new_stateij='#'int m,n;printf(" 请输入NFA:状态的个数:bbb");scanf("%d",&n);fflush(stdin);printf("状态转换个数:bbb");s

13、canf("%d",&m);fflush(stdin);printf("请输入各状态:(状态,0/1/2),终态输2,非初终态输1,初态输0.n");创立邻接表int f;文案大全实用标准文档for(i=0; i<n; i+)/n个状态白输入,依次存储到已开辟空间的邻接表头结点中,并根据状态分类装入NFA的初态终态数组中.(printf("状态d ",i+1);scanf("%c,%d",&NFAi.state,&f);fflush(stdin);if(f=0)/ 输入状态假设为初态,

14、依次存入到NFA_startN数组中 (for(j=0; j<N && NFA_startj!='#'j+);NFA_startj=NFAi.state;if(f=2)/ 输入状态假设为终态,依次存入到NFA_finalN数组中 (for(j=0; j<N && NFA_finalj!='#'j+);NFA_finalj=NFAi.state; printf("输入完毕!nn");printf("请输入状态转换函数:(状态1,状态2,输入字 符八n");adjvex *p;/定义

15、一个指向adjvex的指针pchar from,to,arc;int k;for(i=0; i<m; 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; NFAk.state!=from; k+);/结束时 k的值

16、即为匹配状态所在的头结点p->next=NFAk.firstarc;/前插法插入结点到头结点后NFAk.firstarc=p;/前插法插入结点到头结点后if(arc!='$')/输入字符不为空,保存到 AlpsN字母表中(for(j=0; j<N && Alpj!='#'j+)if(arc=Alpj)break;/存在那么跳出,结束不 保存/上循环结束的两个可能：1、该输入字符已经存在于字母表中不存跳出,那么下面的if也不会成立；/2、从0开始到挺吉束都没找不到一¥的字母,结束 for , 记下了 j.if(Alpj=

17、9;#') Alpj=arc;printf("输入完毕!nn");/求所有NFA_startN中所有初态的closure形成总的 初态 DFA_startN/char startNN;/for(i=0; i<N; i+)/ for(j=0; j<N; j+)/startij='#'/for(i=0; NFA_starti!='#' i+)/依次对每个 NFA初态求等价状态放在二维数组中/ closure(NFA_starti,DFA_start);/*int k;for(i=0; NFA_starti!='#

18、9; 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+;closure(NFAk.state,DFA_start);/求 初态的e_closure 闭包/for(int z=0; z

19、<N; z+)文案大全实用标准文档/printf("%4c %4cn",NFA_startz,DFA_startz);Special(DFA_start,new_state);/ 有 DFA_startN,即为new_state0通过对NFAN邻接表依次求/for(z=0;z<N; z+)/printf("%sn",new_statez);/k=0;for(i=0;i<N&&new_statei0!='#'i+)/寻找 DFA的终态for(j=0;j<N&&new_stateij!=

20、'#'j+)for(f=0;f<N&&NFA_finalf!='#'f+)if(new_stateij=NFA_finalf)DFA_finalk=i+65;k+;break;if(new_stateij=NFA_finalf)break;/NFA和DFA勺输出：k=0;for(i=0;i<N&&new_statei0!='#'i+)/寻找 DFA的终态for(j=0;j<N&&new_stateij!='#'j+)for(f=0;f<N&&N

21、FA_finalf!='#'f+)if(new_stateij=NFA_finalf)DFA_finalk=i+65;k+;break;if(new_stateij=NFA_finalf)break;printf("确定化后的DFA如下所示：n");printf("");for(i=0;Alpi!='#'i+)printf("%3c",Alpi);printf(" 初终")；printf("n");for(i=0;DFAi.state!='#'i+

22、)/以矩阵形式输出DFAprintf("%4c",DFAi.state);for(j=0;Alpj!='#'j+)p=DFAi.firstarc;while(p)if(p->arc=Alpj)printf("%3c",p->nextstate);break;elsep=p->next;if(p=NULL)printf("");for(k=0;k<N&&DFA_finalk!='#'k+)if(DFAi.state=DFA_finalk)break;if(DFA_f

23、inalk='#')printf(" 0");elseprintf(" 1");printf("n");printf("每个新的状态对应的原状态子集如下：n");/输出对应的NFA子集for(i=0;i<N&&new_statei0!='#'i+)printf("%3c,i+65);printf(" ");for(j=0;j<N&&new_stateij+1!='#'j+)printf(&quo

24、t;%c,",new_stateij);printf("%c",new_stateij);文案大全实用标准文档printf("n");)printf(" 新的终态如下：n");for(i=0;i<N&&DFA_finali!='#'i+)(printf("%3c",DFA_finali);) printf("n");)void closure(char s,char setN)/找一个状态 s 经过任意连续个的空弧所到达白等价状态的集合setN(包

25、括自身即为0条空弧)(int i,j;for(i=0;seti!='#'i+)/将自身存储到 setN中,0条空弧if(seti=s)break;if(seti='#')seti=s;for(j=0;NFAj.state!=s;j+);/查找相应状态所在的邻接表的头结点状态位置jadjvex *p;p=NFAj.firstarc;/ 指针p指向该头结点状态的第一个后继状态while(p)(if(p->arc='$')(closure(p->nextstate,set);/ 假设 为空弧的话,递归进入该后继状态所对应的头结点状态处依次查

26、找其 空弧后继,查找结束回到上一层后继状态继续查找p=p->next;)elsep=p->next;/ 查看该头结点状态的下一个后继状态) return;)void move(char FromN,char arc,char ToN)/找一个状态集FromN的所有状态的arc后继状态的集合ToN(int i,j,k,t=0;adjvex *p;j=0;/首先定义j为0for(i=0; i<N && Fromi!='#'i+ )/依次对其中的每一个状态求move,直至结束(for(k=0;NFAk.state!=Fromi;k+);查找相应状态所

27、在的邻接表的头结点状态位置jp=NFAk.firstarc;/ 指针p指向该头结点状态的第一个后继状态while(p)/ 逐个后继状态往后判断后继结束,每次 将弧为arc的状态保存到ToN中if(p->arc=arc)(for(k=0; k<N && Tok!='#' k+)if(Tok=p->nextstate)(p=p->next;break;/该状态假设已存在ToN中,跳出循环不保存,移动指针查看下一个后继状态)if(Tok='#')/直达结束没有发现已经存入,(Tot+=p->nextstate;p=p-&g

28、t;next;)else p=p->next;)void Order(char aN)(/由小到大对数组中的每个字符排序int i,j;char temp;for(i=0;i<N&&ai!='#'i+)for(j=i+1;j<N&&aj!='#'j+)(if(aj<ai)(temp=ai;文案大全实用标准文档ai=aj；aj=temp;)void Special(char DFA_startN,char new_stateNN)(int i,j;char To1N,To2N;char order1N,ord

29、er2N;for(i=0; i<N; i+)(To1i='#'To2i='#')for(i=0; i<N && DFA_starti!='#'i+)new_state0i=DFA_starti;/将DFA_startN复制到 new_state0,作为一个状态int st,k,t;adjvex *p;for(st=0; st<N && new_statest0!='#' st+ )(DFAst.state=st+65;for(i=0; Alpi!='#' i+)(f

30、or(k=0; k<N; k+)(To1k='#'To2k='#'/每次使用TO1 To2都要去除原有数据)move(new_statest,Alpi,To1);for(j=0;To1j!='#'j+)循环求状态集白c closure闭包(求每一个状态的closure 时,都会对上一个 状态得到的To2N从头找不相同的存进去)(closure(To1j,To2);)for(j=0; j<N&&new_statej0!='#'j+)/ 将 new_state 和 closure( move(I,a)转存到

31、两个新数组中,排序比拟是否已经存在此状态集合,以 防出错for(k=0; k<N; k+)order1k=new_statejk;order2k=To2k;)Order(order1);Order(order2);比拟是否相等for(k=0;k<N&&order1k!='#'&&order2k!='#' k+)if(order1k!=order2k)break;if(order1k=order2k)break;/前面比拟一直相等,最后第k个也为#,同时结束,说明相同)if(new_statej0='#')/不存 在与新状态相等的状态,将其存入最后一行new_statejfor(t=0;t<N&&To2t!='#'t+)new_statejt=To2t;)p=(adjvex*)malloc(sizeof(adjvex);为这个状态转换创立一个结点p->nextstate=j+65;p->arc=Alpi;p->next=DFAst.firstarc;DFA