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

编译原理实验报告(二) 鲁庆河 实验名称： 不确定有穷状态自动机的确定化 实验目的： 输入：非确定有穷状态自动机NFA 输出：确定化的有穷状态自动机DFA 实验原理： NFA确定化为DFA 同一个字符串α可以由多条通路产生，而在实际应用中，作为描述控制过程的自动机，通常都是确定有限自动机DFA，因此这就需要将不确定有限自动机转换成等价的确定有限自动机，这个过程称为不确定有限自动机的确定化，即NFA确定化为DFA。 NFA的确定化算法 ----- 子集法： 若NFA的全部初态为S1，S2，…，Sn，则令DFA的初态为： S＝[S1，S2，…，Sn]， 其中方括号用来表示若干个状态构成的某一状态。 设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中。 重复第2步，直到K中不再有新的状态加入为止。 上面得到的所有状态构成DFA的状态集K，转换函数构成DFA的F，DFA的字母表仍然是NFA的字母表∑。 DFA中凡是含有NFA终态的状态都是DFA的终态。 closure（I）函数，move(I,a)函数的 假设I是NFA M状态集K的一个子集（即I∈K），则定义ε-closure（I）为： 若Q∈I，则Q∈ε-closure（I）； 若Q∈I，则从Q出发经过任意条ε弧而能到达的任何状态Q’，则Q’∈closure（I）。 状态集ε-closure（I）称为状态I的ε闭包。 假设NFA M＝( K,∑,F,S,Z ),若I∈K，a∈∑,则定义Ia＝closure（J）,其中J是所有从closure（I）出发,经过一条a弧而到达的状态集。 NFA确定化的实质是以原有状态集上的子集作为DFA上的一个状态,将原状态间的转换为该子集间的转换，从而把不确定有限自动机确定化。经过确定化后，状态数可能增加,而且可能出现一些等价状态，这时就需要简化。 实验思路：(数据结构及变量设计等) 实验小结： 在写此次试验之初，数据结构设计是这样的，K,E,S,Z都用一位字符数组存储，F用下面的链表存储，但是最终在写move函数时查找J集合麻烦，加之数据结构算法的实现基本功不够，在同学的指点下就从新定义了数据结构。 在新的数据结构中，使用邻接表来存储转换函数的，虽然数据结构部分对于顺序表 链表 邻接表的操作很陌生，但通过此次的实验让我对于数据结构中邻接表的使用有了很好的复习和回顾，也学会了邻接表中指针的使用和插入删除操作…… 此次实验过程中，代码虽然全部都是本人自己编写，但很多不是我自己的思想，是从同学那剽窃来理解消化的，在别人和我讲述了代码之后，我自己独立的去写时，细节的地方仍然是漏洞百出，到处出错。我的代码能力太差，也常常因为这而自卑，但也不知如何去提升，虽然课本上的确定化会写，算法也能够理解和掌握，但是实现起来就是无从下手，所以动手能力差的同时，书本知识也得不到强化。 我会借编译原理实验的机会慢慢的熟悉代码，自己去想通算法，自己去实现算法。 我很感激姚老师的严厉要求，我相信我们院的老师都要像您和王爱平老师这样的就好了！ 附件：（程序和运行结果截图） 程序： #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];//用邻接表存储的NFA headvex DFA[N];//用邻接表存储的DFA char Alp[N];//存储需要输入的行为集，即字母表 void main() { void designby();//函数声明 void clos