不确定有穷自动机的确定化

编译原理实验报告不确定有限状态自动机的确定化实验名称2011/5/23实验时间计算机科学与技术专业院系08计算机一班班级E10814065学号王全鸿姓名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.实验内容⑴实现计算闭包closure（I）的算法；⑵实现转换函数move（q，a）的算法；⑶输出界面如下：4.实验心得本次实验对我来说是非常困难的，因为我以往的编程经验匮乏，故满腔墨水NFA的图形形式DFA的图形形式无从倾洒。所以，本次的实验代码是我从网上下载得来的。虽然代码不是我所写，但我可以保证的是程序实例是我创建并自己手动输入的，对于程序的设计原理和运行过程我还是相当熟练的。针对于这种情况，我已决定以后加强锻炼，逐步提升自己的编程能力，不仅要做到能读得懂，也要能写得出。但此非一朝一夕，希望老师能够理解。5.实验代码#defineMAX10#defineINFINIT32767#defineNumMaxChar10#defineNumMAXTN10#includestdio.h#includestdlib.h#includestring.htypedefstructedge{//边intdest;charcost;structedge*link;//指向下一边}*Edge;typedefstructvertex{//顶点chardata;//状态Edgeadj;//边}*Vertex;typedefstructgraph{//图VertexNodeTable;intNumVertex;intMaxNumVertex;intNumEdge;}*Graph;typedefstructtablenode{//转换表节点charnewname;//新命名charch[MAX];//顶点集合}*TableNode;typedefstructtablequeue{//转换表列TableNodeTN[MAX];//转换表节点数组chartransword;//转换条件intNumTn;//添加的顶点数}*TableQueue;typedefstructtransmatrix{//状态转换矩阵TableQueueTQ;//转换表列组inttransnum;//转换表列数}*TranMatrix;intGraphEmpty(Graphg){//图判空returng-NumVertex==0;}intGraphFull(Graphg){//判图满returng-NumVertex==g-MaxNumVertex;}charGetValue(Graphg,inti){//寻找下标为i的顶点return(i0&&ig-NumVertex?g-NodeTable[i].data:'');}voidInsert_Vertex(Graphg,charvertex){//插入新的顶点g-NodeTable[g-NumVertex].data=vertex;g-NodeTable[g-NumVertex].adj=NULL;g-NumVertex++;}voidInsert_Edge(Graphg,intv1,intv2,charweight){//插入边Edgep;p=(Edge)malloc(sizeof(structedge));p-cost=weight;p-dest=v2;p-link=g-NodeTable[v1].adj;g-NodeTable[v1].adj=p;}intGetVertexPos(Graphg,charv){//得到顶点在图中的下标inti=0;while(ig-NumVertex){if(g-NodeTable[i].data==v)returni;i++;}returnINFINIT;}voidConstruct_Graph(Graphg){//创建图intk,j,i,vexn,edgen;charhead,tail,name;charweight;g-NumVertex=0;g-NumEdge=0;g-MaxNumVertex=MAX;g-NodeTable=(Vertex)malloc((g-MaxNumVertex)*sizeof(structvertex));printf(输入NFA状态数:);scanf(%d,&vexn);printf(输入NFA状态名称:\n);flushall();//依次获取状态名称，并将这些顶点插入图中for(i=0;ivexn;i++){scanf(%c,&name);flushall();Insert_Vertex(g,name);}printf(输入NFA的边数:);scanf(%d,&edgen);printf(输入起始状态，接受字符和到达状态:\n);flushall();//依次获取边的信息（起始顶点，接受字符，到达的顶点），并将这些边插入图中for(i=0;iedgen;i++){flushall();scanf(%c%c%c,&tail,&weight,&head);k=GetVertexPos(g,tail);j=GetVertexPos(g,head);Insert_Edge(g,k,j,weight);}}voidDestruct_Graph(Graphg){//销毁图inti;Edgep;for(i=0;ig-NumVertex;i++){p=g-NodeTable[i].adj;while(p!=NULL){g-NodeTable[i].adj=p-link;p-link=NULL;free(p);p=g-NodeTable[i].adj;}}g-NumEdge=0;g-NumVertex=0;printf(图已销毁\n);}voidShow_Graph(Graphg){//显示图inti;Edgep;for(i=0;ig-NumVertex;i++){p=g-NodeTable[i].adj;while(p!=NULL){printf((%c,%c):%c,g-NodeTable[i].data,g-NodeTable[p-dest].data,p-cost);p=p-link;}printf(\n);}}voidInit_Matrix(TranMatrixTM){inti,j,k;printf(输入接受字符数:);scanf(%d,&TM-transnum);TM-TQ=(TableQueue)malloc((TM-transnum+1)*sizeof(structtablequeue));//初始化转换矩阵的第一列for(j=0;jMAX;j++){TM-TQ[0].TN[j]=(TableNode)malloc(sizeof(structtablenode));TM-TQ[0].TN[j]-newname='\0';for(k=0;kNumMaxChar;k++)TM-TQ[0].TN[j]-ch[k]='\0';}TM-TQ[0].transword='I';TM-TQ[0].NumTn=0;//初始化转换矩阵的其它列for(i=1;i=TM-transnum;i++){printf(输入