《不确定有穷自动机的确定化(共10页).doc》由会员分享，可在线阅读，更多相关《不确定有穷自动机的确定化(共10页).doc（10页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、精选优质文档-倾情为你奉上编译原理实验报告不确定有限状态自动机的确定化实验名称 2011/5/23实验时间 计算机科学与技术专业院系 08计算机一班班级 E学号 王全鸿姓名 1. 试验目的输入： 非确定有限（穷）状态自动机。输出： 确定化的有限（穷）状态自动机2. 实验原理一个确定的有限自动机（DFA）M可以定义为一个五元组，M（K，F，S，Z），其中：（1） K是一个有穷非空集，集合中的每个元素称为一个状态；（2） 是一个有穷字母表，中的每个元素称为一个输入符号；（3） F是一个从KK的单值转换函数，即F（R，a）Q，（R，QK）表示当前状态为R，如果输入字符a，则转到状态Q，状态Q称为状态
2、R的后继状态；（4） SK，是惟一的初态；（5） ZK，是一个终态集。由定义可见，确定有限自动机只有惟一的一个初态，但可以有多个终态，每个状态对字母表中的任一输入符号，最多只有一个后继状态。 对于DFA M，若存在一条从某个初态结点到某一个终态结点的通路，则称这条通路上的所有弧的标记符连接形成的字符串可为DFA M所接受。若M的初态结点同时又是终态结点，则称可为M所接受（或识别），DFA M所能接受的全部字符串（字）组成的集合记作L（M）。一个不确定有限自动机（NFA）M可以定义为一个五元组，M（K，F，S，Z），其中：（1） k是一个有穷非空集，集合中的每个元素称为一个状态；（2） 是一个有
3、穷字母表，中的每个元素称为一个输入符号；（3） F是一个从KK的子集的转换函数；（4） SK，是一个非空的初态集；（5） ZK，是一个终态集。由定义可见，不确定有限自动机NFA与确定有限自动机DFA的主要区别是:（1）NFA的初始状态S为一个状态集，即允许有多个初始状态；（2）NFA中允许状态在某输出边上有相同的符号，即对同一个输入符号可以有多个后继状态。即DFA中的F是单值函数，而NFA中的F是多值函数。因此，可以将确定有限自动机DFA看作是不确定有限自动机NFA的特例。和DFA一样，NFA也可以用矩阵和状态转换图来表示。对于NFA M，若存在一条从某个初态结点到某一个终态结点的通路，则称这
4、条通路上的所有弧的标记（除外）连接形成的字符串可为M所接受。NFA M所能接受的全部字符串（字）组成的集合记作L（M）。由于DFA是NFA的特例，所以能被DFA所接受的符号串必能被NFA所接受。设M1和M2是同一个字母集上的有限自动机，若L（M1）L（M2），则称有限自动机M1和M2等价。由以上定义可知，若两个自动机能够接受相同的语言，则称这两个自动机等价。DFA是NFA的特例，因此对于每一个NFA M1总存在一个DFA M2，使得L（M1）L（M2）。即一个不确定有限自动机能接受的语言总可以找到一个等价的确定有限自动机来接受该语言。NFA确定化为DFA同一个字符串可以由多条通路产生，而在实际
5、应用中，作为描述控制过程的自动机，通常都是确定有限自动机DFA，因此这就需要将不确定有限自动机转换成等价的确定有限自动机，这个过程称为不确定有限自动机的确定化，即NFA确定化为DFA。下面介绍一种NFA的确定化算法，这种算法称为子集法：（1） 若NFA的全部初态为S1，S2，Sn，则令DFA的初态为：SS1，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的一个转换函数。
6、若 Si，Si+1，Sk 不在K中，则将其作为新的状态加入到K中。（3） 重复第2步，直到K中不再有新的状态加入为止。（4） 上面得到的所有状态构成DFA的状态集K，转换函数构成DFA的F，DFA的字母表仍然是NFA的字母表。（5） DFA中凡是含有NFA终态的状态都是DFA的终态。对于上述NFA确定化算法子集法，还可以采用另一种操作性更强的描述方式，下面我们给出其详细描述。首先给出两个相关定义。 假设I是NFA M状态集K的一个子集（即IK），则定义-closure（I）为：（1） 若QI，则Q-closure（I）；（2） 若QI，则从Q出发经过任意条弧而能到达的任何状态Q，则Q-clos
7、ure（I）。状态集-closure（I）称为状态I的闭包。假设NFA M（K，F，S，Z），若IK，a，则定义Ia-closure（J），其中J是所有从-closure（I）出发，经过一条a弧而到达的状态集。NFA确定化的实质是以原有状态集上的子集作为DFA上的一个状态，将原状态间的转换为该子集间的转换，从而把不确定有限自动机确定化。经过确定化后，状态数可能增加，而且可能出现一些等价状态，这时就需要简化。3. 实验内容 实现计算闭包closure（I）的算法； 实现转换函数move（q，a）的算法； 输出界面如下：NFA的 图形形式DFA的图形形式4. 实验心得本次实验对我来说是非常困难的，
8、因为我以往的编程经验匮乏，故满腔墨水无从倾洒。所以，本次的实验代码是我从网上下载得来的。虽然代码不是我所写，但我可以保证的是程序实例是我创建并自己手动输入的，对于程序的设计原理和运行过程我还是相当熟练的。针对于这种情况，我已决定以后加强锻炼，逐步提升自己的编程能力，不仅要做到能读得懂，也要能写得出。但此非一朝一夕，希望老师能够理解。5.实验代码专心-专注-专业#define MAX 10#define INFINIT 32767#define NumMaxChar 10#define NumMAXTN 10 #include #include #include typedef struct e
9、dge/边int dest;char cost;struct edge *link;/指向下一边*Edge; typedef struct vertex/顶点char data;/状态Edge adj;/边*Vertex; typedef struct graph/图Vertex NodeTable;int NumVertex;int MaxNumVertex;int NumEdge;*Graph;typedef struct tablenode/转换表节点char newname;/新命名char chMAX;/顶点集合*TableNode; typedef struct tablequeu
10、e/转换表列TableNode TNMAX;/转换表节点数组char transword;/转换条件int NumTn;/添加的顶点数*TableQueue; typedef struct transmatrix/状态转换矩阵TableQueue TQ;/转换表列组int transnum;/转换表列数*TranMatrix; int GraphEmpty(Graph g)/图判空return g-NumVertex=0; int GraphFull(Graph g)/判图满return g-NumVertex=g-MaxNumVertex; char GetValue(Graph g,int
11、 i)/寻找下标为i的顶点return (i0 & iNumVertex? g-NodeTablei.data: ); void Insert_Vertex(Graph g,char vertex)/插入新的顶点g-NodeTableg-NumVertex.data=vertex;g-NodeTableg-NumVertex.adj=NULL;g-NumVertex+; void Insert_Edge(Graph g,int v1,int v2,char weight)/插入边Edge p;p=(Edge)malloc(sizeof(struct edge);p-cost=weight;p-
12、dest=v2;p-link=g-NodeTablev1.adj;g-NodeTablev1.adj=p; int GetVertexPos(Graph g,char v)/得到顶点在图中的下标int i=0;while(iNumVertex)if(g-NodeTablei.data=v)return i;i+;return INFINIT; void Construct_Graph(Graph g)/创建图int k,j,i,vexn,edgen;char head,tail,name;char weight;g-NumVertex=0;g-NumEdge=0;g-MaxNumVertex=
13、MAX;g-NodeTable=(Vertex)malloc(g-MaxNumVertex)*sizeof(struct vertex);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()
14、;/依次获取边的信息（起始顶点，接受字符，到达的顶点），并将这些边插入图中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); void Destruct_Graph(Graph g)/销毁图 int i;Edge p;for(i=0;iNumVertex;i+)p=g-NodeTablei.adj;while(p!=NULL)g-NodeTablei.adj=p-link
15、;p-link=NULL;free (p);p=g-NodeTablei.adj;g-NumEdge=0;g-NumVertex=0;printf(图已销毁n); void Show_Graph(Graph g)/显示图 int i; Edge p;for(i=0;iNumVertex;i+)p=g-NodeTablei.adj;while(p!=NULL)printf(%c,%c):%c ,g-NodeTablei.data,g-NodeTablep-dest.data,p-cost);p=p-link;printf(n);void Init_Matrix(TranMatrix TM)int
16、 i,j,k;printf(输入接受字符数:);scanf(%d,&TM-transnum);TM-TQ=(TableQueue)malloc(TM-transnum+1)*sizeof(struct tablequeue);/初始化转换矩阵的第一列for(j=0;jTQ0.TNj=(TableNode)malloc(sizeof(struct tablenode);TM-TQ0.TNj-newname=0;for(k=0;kTQ0.TNj-chk=0;TM-TQ0.transword=I;TM-TQ0.NumTn=0;/初始化转换矩阵的其它列for(i=1;itransnum;i+)prin
17、tf(输入第%d个转换字符:n,i);flushall();scanf(%c,&TM-TQi.transword);for(j=0;jTQi.TNj=(TableNode)malloc(sizeof(struct tablenode);TM-TQi.TNj-newname=0;for(k=0;kTQi.TNj-chk=0;TM-TQi.NumTn=0;void BubbleSort(char a,int len)/冒泡排序int i,j;char temp; for(i=0;ilen;i+)for(j=0;jaj+1)temp=aj+1;aj+1=aj;aj=temp; int CheckCh
18、ar(char t,char ti)/检查数组t中是否有与ti相同的字符/0 有重复，1 无重复int i;for(i=0;iNumMaxChar;i+)if(ti=ti) return 0;return 1; int CheckTable(TranMatrix TM,char str)/检查转换矩阵的第一列中是否有与str相同的字符串/ i 有重复（并返回重复的位置），1 无重复int i;for(i=0;iTQ0.NumTn;i+)if(!strcmp(TM-TQ0.TNi-ch,str)return i;return 1; void Smove(Graph g,char t1,char
19、t2,char transword)/根据NFA，将t1中的状态接受了transword后转为对应的t2中的状态int i,j,k=0,check,len;Edge p;while(t2k!=0) k+;for(i=0;iMAX;i+)for(j=0;jNumVertex;j+)if(g-NodeTablej.data=t1i) p=g-NodeTablej.adj;while(p!=NULL)if(p-cost=transword) check=CheckChar(t2,g-NodeTablep-dest.data);if(check=1) t2k=g-NodeTablep-dest.dat
20、a;k+;p=p-link;elsep=p-link;len=k;BubbleSort(t2,k); void E_Closure(Graph g,char t)/对进行了Smove后的状态集合求闭包，并将结果按升序排列int i=0,j,k=0,check,len;Edge p;/找到字符数组中的最后一个字符的位置while(tk!=0) k+;for(i=0;ti!=0;i+) /每个顶点都要查看一次for(j=0;jNumVertex;j+)/if(g-NodeTablej.data=ti)p=g-NodeTablej.adj;while(p!=NULL)if(p-cost=*)/空输入
21、 check=CheckChar(t,g-NodeTablep-dest.data);if(check=1)tk=g-NodeTablep-dest.data;k+; p=p-link;len=k;BubbleSort(t,k);/结果按升序排列 void Show_TranMatrix(TranMatrix TM)int i,j,k;printf(状态转换矩阵:n);for(j=0;jtransnum;j+) printf(转换字符:%c ,TM-TQj.transword);printf(n);for(k=0;kMAX;k+) for(j=0;jtransnum;j+) if(TM-TQj
22、.TNk-newname=0) printf(NULL );else printf(%c:,TM-TQj.TNk-newname);for(i=0;TM-TQj.TNk-chi!=0;i+) printf(%c,TM-TQj.TNk-chi);if(TM-TQj.TNk-ch0=0) printf(NULL);printf( );printf(n); void NFA_to_DFA(Graph g,TranMatrix TM)int j=0,i,check;char temp2=0,0;TM-TQ0.TN0-ch0=g-NodeTable0.data;for(i=1;itransnum;i+)
23、E_Closure(g,TM-TQ0.TN0-ch);printf(输入新状态名:);flushall();scanf(%c,&TM-TQ0.TN0-newname);TM-TQ0.NumTn+;while(jTQ0.NumTn)for(i=1;itransnum;i+)Smove(g,TM-TQ0.TNj-ch,TM-TQi.TNj-ch,TM-TQi.transword);E_Closure(g,TM-TQi.TNj-ch);if (TM-TQi.TNj-ch0!=0)/如果为空则可忽略，不记入结果状态check=CheckTable(TM,TM-TQi.TNj-ch);if(check=
24、1) printf(输入新状态名:);flushall();scanf(%c,&TM-TQi.TNj-newname);strcpy(TM-TQ0.TNTM-TQ0.NumTn-ch,TM-TQi.TNj-ch);TM-TQ0.TNTM-TQ0.NumTn-newname=TM-TQi.TNj-newname;TM-TQ0.NumTn+;else TM-TQi.TNj-newname=TM-TQ0.TNcheck-newname;j+; void Show_DFA(TranMatrix TM)int i,j;for(j=0;TM-TQ0.TNj-newname!=0;j+)for(i=1;it
25、ransnum;i+) if (TM-TQi.TNj-newname!=0)printf(%c,%c,%c) ,TM-TQ0.TNj-newname,TM-TQi.transword,TM-TQi.TNj-newname);printf(n); void main()Graph g;TranMatrix TM;g=(Graph)malloc(sizeof(struct graph);TM=(TranMatrix)malloc(sizeof(struct transmatrix);Construct_Graph(g);Init_Matrix(TM);printf(nNFA图:n);Show_Graph(g);printf(n(初始状态):n);Show_TranMatrix(TM);NFA_to_DFA(g,TM);printf(n(转换过程):n);Show_TranMatrix(TM);printf(n转化后的DFA:n);Show_DFA(TM);printf(n程序结束，销毁图.n);Destruct_Graph(g);Show_Graph(g);