下载文档原格式
实用文档2016.11.02不确定有穷状态自动机的确定化目录一、实验名称 (2)二、实验目的 (2)三、实验原理 (2)1、NFA定义 (2)2、DFA的定义 (2)3、closure函数 (2)4、move函数 (3)四、实验思路 (3)1、输入 (3)2、closure算法 (3)3、move算法 (3)4、构造子集 (4)5、输出 (4)五、实验小结 (4)1、输入存储问题 (4)2、closure算法问题 (4)3、输出问题 (5)六、附件 (5)1、源代码 (5)2、运行结果截图 (7)一、实验名称不确定有穷状态自动机的确定化二、实验目的输入：非确定有穷状态自动机NFA输出：确定化的有穷状态自动机DFA三、实验原理1、NFA定义一个不确定的有穷自动机M是一个五元组，M=(K,E,f,S,Z)其中a.K是一个有穷集，它的每个元素称为一个状态；b.E是一个有穷字母表，它的每个元素称为一个输入符号；c.f是一个从K×E*到K的子集的映像，即：K*E*->2k，其中2k表示K的幂集；d.S包含于K，是一个非空初态集；e.Z包含于K，是一个终态集。
2、DFA的定义一个确定的有穷自动机M是一个五元组，M=(K,E,f,S,Z)其中a.K是一个有穷集，它的每个元素称为一个状态；b.E是一个有穷字母表，它的每个元素称为一个输入符号；c.f是转换函数，是K×E->K上的映像，即，如f(ki,a)=kj(ki∈K,kj∈K)就意味着，当前状态为ki，输入字符为a时，将转换到下一状态kj，我们把kj称作ki的一个后继状态；d.S∈K，是唯一的一个初态；e.Z包含于K，是一个终态集，终态也称可接受状态或结束状态。
3、closure函数状态集合I的ε—闭包，表示为ε—closure(I)，定义为一状态集，是状态集I中的任何状态S经任意条ε弧而能到达的状态的集合。
4、move函数状态集合I的a弧转换，表示为move(I,a)，定义为状态集合J，其中J是所有那些从I中的某一状态经过一条a弧而到达的状态的全体。
课程设计报告课程：编译原理学号：姓名：班级：教师：时间：2014.5--2014.6.20计算机科学与技术系图4.4-1 NFA-DFA处理流程图2.NFA转换为DFA的原理及过程通过以下例子说明：①假如输入的NFA如图4.4-2所示：图4.4-2 NFA状态转换图②对于图4.2-2中的状态转换图的状态转换矩阵为：在图4.2-2中的状态转换图加一个起始状态X和结束状态Y，I为起始节点X经过一个或多个ε边到达的状态集，Ia为{X,1}经过a边到达的结点的ε闭包，Ib经过b边到达的结点的ε闭包;知道Ia和Ib列都在I列中出现为止。
如下表4.2.1所示：表4.2.1状态转换矩阵I Ia Ib{X,1} {2,3,Y}{2,3,Y} {2,3,Y}③对表4.2.1的状态转换矩阵进行重新命名，令A={X,1}，B={2,3,Y}，转换结果如下表4.2.2所示：表4.2.2重命名的状态转换矩阵④表4.2.2相对应的 DFA状态转换图为下图图4.2-2所示：图4.2-2 DFA状态图I Ia IbA BB B结果与分析（可以加页）：1.对于下图1中的NFA：图1 NFA状态图2.输入图1中NFA的各边信息：如下截图图2所示：图2 输入各边信息截图3.对于图1的NFA状态转换矩阵和重命名后的状态矩阵如下截图图3所示：图3 DFA状态矩阵截图4.将图3中的状态矩阵图最小化，如下截图图4所示：图4 最小化的DFA5.根据图4最小化的DFA状态转换矩阵，画出DFA状态转换图，如下图图5所示：图5 DFA状态装换图设计体会与建议：编译原理是一门重要但难学的课程，因为编译原理是关于编写编译器的技术，编译器的编写一直被认为是十分困难的事情，所以这次选到课程设计的课题就有些无从下手的感觉，感觉任务挺艰巨的。
设计要求从理论上就不太好理解，不像以前的设计编写一个应用程序实现常见的功能，这次的课程设计注重各种算法的实现，比如用子集法实现不确定的有限自动机的确定化、又能够分割法实现确定的有限自动机的最小化。
DFA确定化实验报告一、课程设计的目的通过课程设计进一步理解高级语言在计算机中的执行过程，加深对编译原理中重点算法和编译技术的理解，提高自己的编程能力，培养好的程序设计风格。
同时通过某种可视化编程语言的应用，具备初步的Windows环境下的编程思想。
掌握子集法，即将NFA转换为与之等价的DFA的算法。
二、课程设计的内容及要求1.通过设计编写和调试将不确定的有穷自动机转换为与之等价的确定的有穷自动机的程序，使学生了解子集法，掌握转换过程中的相关概念和方法。
2.输入一个NFA3.输出与之等价的DFA三、实现原理1、构造数据结构：1）图的数据结构；2）转换关系的数据结构。
2、求图的开始节点的ε-closure ，作为子集链表的头节点。
然后对其ε-closure 中的每个节点，根据转换关系，求出新的子集，将新求出的子集插入到子集链表的尾部。
构造主要的数据结构：struct diagram {int snum; //节点编号move *transfer; //转换关系diagram *next;};//图的数据结构构造主要的数据结构：struct subset {int snum; //节点编号，char closure[MAX]; //该节点中包含原来的哪些节点，也就是其ε_closure move *transfer; //来源关系subset *next;};//子集的数据结构构造主要的数据结构：struct move{int point; //来自或转向哪一个节点char input; //转向条件move *next;};//存储来源关系四、算法实现与流程（1）读取文件中的数据，组成图的初始链表。
通常，用自然语言描述这个阶段的工作是烦琐的，用子集矩阵完成这阶段工作具有直观性和简单性。
以下过程将描述用子集矩阵法完成从NFA（图1）到DFA的转化：先将图1运用子集矩阵法，通过运算得到表1。
其中s表示状态，即算法描述中的自己族C；a，b表示输入字符。
有限状态自动机的确定化姓名：翟彦清学号：E10914127一、实验目的设计并实现将 NFA确定化为DFA的子集构造算法，从而更好地理解有限自动机之间的等价性，掌握词法分析器自动产生器的构造技术。
该算法也是构造LR分析器的基础。
输入：非确定有限(穷)状态自动机。
输出：确定化的有限(穷)状态自动机二、实验原理一个确定的有限自动机(DFA M可以定义为一个五元组，M k( K,E, F, S, Z),其中：(1)K是一个有穷非空集，集合中的每个元素称为一个状态；(2)刀是一个有穷字母表，刀中的每个元素称为一个输入符号；(3)F是一个从K XE^ K的单值转换函数，即 F (R, a)= Q ( R, Q€ K)表示当前状态为R,如果输入字符 a,则转到状态 Q,状态Q称为状态R的后继状态；(4)S€ K,是惟一的初态；(5)Z K,是一个终态集。
由定义可见,确定有限自动机只有惟一的一个初态,但可以有多个终态,每个状态对字母表中的任一输入符号,最多只有一个后继状态。
对于DFAM,若存在一条从某个初态结点到某一个终态结点的通路，则称这条通路上的所有弧的标记符连接形成的字符串可为DFAM所接受。
若M的初态结点同时又是终态结点，则称&可为 M所接受(或识别)，DFA M所能接受的全部字符串(字)组成的集合记作 L(M)。
一个不确定有限自动机(NFA M可以定义为一个五元组，M=(K, E, F, S, Z), 其中：( 1) k 是一个有穷非空集,集合中的每个元素称为一个状态；(2)E是一个有穷字母表，E中的每个元素称为一个输入符号；(3)F是一个从K xE^ K的子集的转换函数；(4)S K,是一个非空的初态集；(5)Z K,是一个终态集。
由定义可见，不确定有限自动机 NFA与确定有限自动机DFA的主要区别是：(1)NFA的初始状态S为一个状态集，即允许有多个初始状态；(2)NFA中允许状态在某输出边上有相同的符号，即对同一个输入符号可以有多个后继状态。
编译原理实验NFA确定化为DFA编译原理中的NFA（Non-deterministic Finite Automaton，非确定性有限自动机）是一种能够识别正则语言的形式化模型。
它的设计简单，但效率较低。
为了提高识别效率，需要将NFA转化为DFA（Deterministic Finite Automaton，确定性有限自动机）。
本文将介绍NFA确定化为DFA的一般方法，并以一个具体例子来说明该过程。
首先，我们来了解一下NFA和DFA的差异。
NFA可以有多个转移路径，每个输入符号可以对应多个状态转移，而DFA每个输入符号只能对应唯一的状态转移。
这使得NFA在识别过程中具有非确定性，无法确定下一个状态。
而DFA则能够准确地根据当前状态和输入符号确定下一个状态。
NFA确定化为DFA的一般方法如下：1.创建DFA的初始状态。
该状态对应NFA的起始状态以及从起始状态经过ε（空）转移可以到达的所有状态。
2.对DFA的每个状态进行如下处理：a)对当前状态的每个输入符号进行处理。
b)根据当前状态和输入符号，确定下一个状态。
如果有多个状态，需要将它们合并为一个DFA状态。
c)重复上述步骤，直到处理完所有输入符号。
3.对于合并的DFA状态，需要重复执行第2步的处理过程，直到没有新的合并状态产生为止。
4.最终得到的DFA包含的状态即为NFA确定化的结果。
下面以一个具体的例子来说明NFA确定化为DFA的过程。
考虑以下NFA：（状态）（输入符号）（转移状态）1a,ε1,22a33b44a5首先，创建DFA的初始状态，根据NFA的起始状态和通过ε转移可以到达的状态。
在该例子中，起始状态为1，通过ε转移可以到达状态1和2、因此，初始状态为{1,2}。
接下来，对初始状态{1,2}进行处理。
对于输入符号a，根据NFA的状态转移表可以得到DFA的下一个状态为{1,2,3}，因为NFA的状态1通过a和ε可以到达状态3、对于输入符号b，当前状态没有转移。
编译原理实验报告(二) E01214055 鲁庆河1.实验名称：不确定有穷状态自动机的确定化2.实验目的：a)输入：非确定有穷状态自动机NFAb)输出：确定化的有穷状态自动机DFA3.实验原理：a)NFA确定化为DFA同一个字符串α可以由多条通路产生，而在实际应用中，作为描述控制过程的自动机，通常都是确定有限自动机DFA，因此这就需要将不确定有限自动机转换成等价的确定有限自动机，这个过程称为不确定有限自动机的确定化，即NFA确定化为DFA。
b)NFA的确定化算法 ----- 子集法：●若NFA的全部初态为S1，S2，…，S n，则令DFA的初态为：S＝[S1，S2，…，S n]，其中方括号用来表示若干个状态构成的某一状态。
●设DFA的状态集K中有一状态为[S i，S i+1，…，S j]，若对某符号a∈∑，在NFA中有F（{ S i，S i+1，…，S j}，a）={ S i’，S i+1’，…，S k’ },则令F（{ S i，S i+1，…，S j }，a）={ S i’，S i+1’，…，S k’ }为DFA的一个转换函数。
若[ S i’，S i+1’，…，S k‘ ]不在K中，则将其作为新的状态加入到K中。
●重复第2步，直到K中不再有新的状态加入为止。
●上面得到的所有状态构成DFA的状态集K，转换函数构成DFA的F，DFA的字母表仍然是NFA的字母表∑。
●DFA中凡是含有NFA终态的状态都是DFA的终态。
c)closure（I）函数，move(I,a)函数的假设I是NFA M状态集K的一个子集（即I∈K），则定义ε-closure（I）为：1.若Q∈I，则Q∈ε-closure（I）；2.若Q∈I，则从Q出发经过任意条ε弧而能到达的任何状态Q’，则Q’∈closure（I）。
3.状态集ε-closure（I）称为状态I的ε闭包。
假设NFA M＝( K,∑,F,S,Z ),若I∈K，a∈∑,则定义I a＝closure（J）,其中J是所有从closure（I）出发,经过一条a弧而到达的状态集。
NFA确定化的实质是以原有状态集上的子集作为DFA上的一个状态,将原状态间的转换为该子集间的转换，从而把不确定有限自动机确定化。
经过确定化后，状态数可能增加,而且可能出现一些等价状态，这时就需要简化。
4.实验思路：(数据结构及变量设计等)5.实验小结：在写此次试验之初，数据结构设计是这样的，K,E,S,Z都用一位字符数组存储，F用下面的链表存储，但是最终在写move函数时查找J集合麻烦，加之数据结构算法的实现基本功不够，在同学的指点下就从新定义了数据结构。
在新的数据结构中，使用邻接表来存储转换函数的，虽然数据结构部分对于顺序表链表邻接表的操作很陌生，但通过此次的实验让我对于数据结构中邻接表的使用有了很好的复习和回顾，也学会了邻接表中指针的使用和插入删除操作……此次实验过程中，代码虽然全部都是本人自己编写，但很多不是我自己的思想，是从同学那剽窃来理解消化的，在别人和我讲述了代码之后，我自己独立的去写时，细节的地方仍然是漏洞百出，到处出错。
我的代码能力太差，也常常因为这而自卑，但也不知如何去提升，虽然课本上的确定化会写，算法也能够理解和掌握，但是实现起来就是无从下手，所以动手能力差的同时，书本知识也得不到强化。
我会借编译原理实验的机会慢慢的熟悉代码，自己去想通算法，自己去实现算法。
我很感激姚老师的严厉要求，我相信我们院的老师都要像您和王爱平老师这样的就好了！6.附件：（程序和运行结果截图）a)程序：#include <stdlib.h>#include <malloc.h>#include <stdio.h>#include <conio.h>#define N 20 //用于控制数组的最大长度//用邻接表存储NFA和DFA的状态字母后继typedef struct adjvex{//定义邻接表的邻接点域的数据表示char nextstate;//头结点状态的后继状态char arc;//弧struct adjvex *next;//指向该头结点状态的下一个后继状态的指针}adjvex;typedef struct headvex{//定义邻接表的头部的数据表示char state;//状态adjvex *firstarc;//指向第一个后继状态的指针}headvex;//定义两个邻接表的头部，为全局数组headvex NFA[N];//用邻接表存储的NFAheadvex DFA[N];//用邻接表存储的DFAchar Alp[N];//存储需要输入的行为集，即字母表void main(){void designby();//函数声明void closure(char s,char set[N]);//求e_closure闭包函数void Special(char DFA_start[N],char new_state[N][N]);//确定化函数designby();int i,j;char NFA_start[N];//存放NFA的初态char DFA_start[N];//存放DFA的初态char NFA_final[N];//存放NFA的终态char DFA_final[N];//存放DFA的终态char new_state[N][N];//存放DFA的I的二维数组每一行为一个原NFA的一个新的状态集，e-closure(move(I,a)) for(i=0; i<N; 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; j<N; j++)new_state[i][j]='#';}int m,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");//创建邻接表int f;for(i=0; i<n; 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; j<N && NFA_start[j]!='#';j++);NFA_start[j]=NFA[i].state;}if(f==2)//输入状态若为终态,依次存入到NFA_final[N]数组中{for(j=0; j<N && NFA_final[j]!='#';j++);NFA_final[j]=NFA[i].state;}}printf("输入完毕!\n\n");printf("请输入状态转换函数:(状态1,状态2,输入字符)\n");adjvex *p;//定义一个指向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; NFA[k].state!=from; k++);//结束时k的值即为匹配状态所在的头结点p->next=NFA[k].firstarc;//前插法插入结点到头结点后NFA[k].firstarc=p;//前插法插入结点到头结点后if(arc!='$')//输入字符不为空，保存到Alps[N]字母表中{for(j=0; j<N && 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]//char start[N][N];//for(i=0; i<N; i++)// for(j=0; j<N; j++)// start[i][j]='#';//for(i=0; NFA_start[i]!='#'; i++)//依次对每个NFA初态求等价状态放在二维数组中// closure(NFA_start[i],DFA_start);/*int k;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];else continue;}*/k=0;while(NFA[k].state!=NFA_start[0])k++;closure(NFA[k].state,DFA_start);//求初态的e_closure闭包//for(int z=0; z<N; z++)//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; z<N; z++)// {// printf("%s\n",new_state[z]);// }k=0;for(i=0;i<N&&new_state[i][0]!='#';i++)//寻找DFA的终态{for(j=0;j<N&&new_state[i][j]!='#';j++){for(f=0;f<N&&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;i<N&&new_state[i][0]!='#';i++)//寻找DFA的终态for(j=0;j<N&&new_state[i][j]!='#';j++){for(f=0;f<N&&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[j]){printf("%3c",p->nextstate);break;}elsep=p->next;}if(p==NULL)printf(" ");}for(k=0;k<N&&DFA_final[k]!='#';k++)if(DFA[i].state==DFA_final[k])break;if(DFA_final[k]=='#')printf(" 0");elseprintf(" 1");printf("\n");}printf("每个新的状态对应的原状态子集如下：\n");//输出对应的NFA子集for(i=0;i<N&&new_state[i][0]!='#';i++){printf("%3c",i+65);printf(" {");for(j=0;j<N&&new_state[i][j+1]!='#';j++)printf("%c,",new_state[i][j]);printf("%c}",new_state[i][j]);printf("\n");}printf("新的终态如下：\n");for(i=0;i<N&&DFA_final[i]!='#';i++){printf("%3c",DFA_final[i]);}printf("\n");}void closure(char s,char set[N])//找一个状态s经过任意连续个的空弧所到达的等价状态的集合set[N](包括自身即为0条空弧) {int i,j;for(i=0;set[i]!='#';i++)//将自身存储到set[N]中，0条空弧if(set[i]==s)break;if(set[i]=='#')set[i]=s;for(j=0;NFA[j].state!=s;j++);//查找相应状态所在的邻接表的头结点状态位置jadjvex *p;p=NFA[j].firstarc;//指针p指向该头结点状态的第一个后继状态while(p){if(p->arc=='$'){closure(p->nextstate,set);//若为空弧的话，递归进入该后继状态所对应的头结点状态处依次查找其空弧后继，查找结束回到上一层后继状态继续查找p=p->next;}elsep=p->next;//查看该头结点状态的下一个后继状态}return;}void move(char From[N],char arc,char To[N])//找一个状态集From[N]的所有状态的arc后继状态的集合To[N]{int i,j,k,t=0;adjvex *p;j=0;//首先定义j为0for(i=0; i<N && From[i]!='#';i++ )//依次对其中的每一个状态求move，直至结束{for(k=0;NFA[k].state!=From[i];k++);//查找相应状态所在的邻接表的头结点状态位置jp=NFA[k].firstarc;//指针p指向该头结点状态的第一个后继状态while(p)//逐个后继状态往后判断后继结束，每次将弧为arc的状态保存到To[N]中if(p->arc==arc){for(k=0; k<N && To[k]!='#'; k++)if(To[k]==p->nextstate){p=p->next;break;//该状态若已存在To[N]中，跳出循环不保存，移动指针查看下一个后继状态}if(To[k]=='#')//直达结束没有发现已经存入，{To[t++]=p->nextstate;p=p->next;}}else p=p->next;}}void Order(char a[N]){//由小到大对数组中的每个字符排序int i,j;char temp;for(i=0;i<N&&a[i]!='#';i++)for(j=i+1;j<N&&a[j]!='#';j++){if(a[j]<a[i]){temp=a[i];a[i]=a[j];a[j]=temp;}}}void Special(char DFA_start[N],char new_state[N][N]){int i,j;char To1[N],To2[N];char order1[N],order2[N];for(i=0; i<N; i++){To1[i]='#';To2[i]='#';}for(i=0; i<N && DFA_start[i]!='#';i++)new_state[0][i]=DFA_start[i];//将DFA_start[N]复制到new_state[0],作为一个状态int st,k,t;adjvex *p;for(st=0; st<N && new_state[st][0]!='#'; st++ ){DFA[st].state=st+65;for(i=0; Alp[i]!='#'; i++){for(k=0; k<N; k++){To1[k]='#';To2[k]='#';//每次使用TO1，To2都要清除原有数据}move(new_state[st],Alp[i],To1);for(j=0;To1[j]!='#';j++)//循环求状态集的closure闭包(求每一个状态的closure时，都会对上一个状态得到的To2[N]从头找不相同的存进去){closure(To1[j],To2);}for(j=0; j<N&&new_state[j][0]!='#'; j++){//将new_state和closure( move(I,a) )转存到两个新数组中，排序比较是否已经存在此状态集合，以防出错for(k=0; k<N; k++){order1[k]=new_state[j][k];order2[k]=To2[k];}Order(order1);Order(order2);//比较是否相等for(k=0;k<N&&order1[k]!='#'&&order2[k]!='#'; k++)if(order1[k]!=order2[k]) break;if(order1[k]==order2[k]) break;//前面比较一直相等，最后第k个也为#，同时结束，说明相同}if(new_state[j][0]=='#')//不存在与新状态相等的状态，将其存入最后一行new_state[j]{for(t=0;t<N&&To2[t]!='#';t++)new_state[j][t]=To2[t];}p=(adjvex *)malloc(sizeof(adjvex));//为这个状态转换创建一个结点p->nextstate=j+65;p->arc=Alp[i];p->next=DFA[st].firstarc;DFA[st].firstarc=p;}}}void designby(){printf("\n\t\t编译原理实验（二）\n\n");printf("\t实验名称：不确定有穷状态自动机的确定化.\n");printf("\t实验目的：输入：非确定有穷状态自动机NFA\n");printf("\t 输出：确定化的有穷状态自动机DFA\n\n");printf("\t姓名：鲁庆河( E01214055 )\n");printf("\t日期：2015.05.12 -- 2015.05.15\n");getch();printf("\n");}b)截图：。
