编译原理实验报告(二) E01214055 鲁庆河
1. 实验名称：
不确定有穷状态自动机的确定化
2. 实验目的：
a) 输入：非确定有穷状态自动机NFA
b) 输出：确定化的有穷状态自动机DFA
3. 实验原理：
a) NFA确定化为DFA
同一个字符串α可以由多条通路产生，而在实际应用中，作为描述控制过程的自动机，通常都是确定有限自动机DFA，因此这就需要将不确定有限自动机转换成等价的确定有限自动机，这个过程称为不确定有限自动机的确定化，即NFA确定化为DFA。
b) 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的终态。
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∈∑,则定义Ia＝closure（J）,其中J是所有从closure（I）出发,经过一条a弧而到达的状态集。 NFA确定化的实质是以原有状态集上的子集作为DFA上的一个状态,将原状态间的转换为该子集间的转换，从而把不确定有限自动机确定化。经过确定化后，状态数可能增加,而且可能出现一些等价状态，这时就需要简化。
4. 实验思路：(数据结构及变量设计等)
5. 实验小结：
在写此次试验之初，数据结构设计是这样的，K,E,S,Z都用一位字符数组存储，F用下面的链表存储，但是最终在写move函数时查找J集合麻烦，加之数据结构算法的实现基本功不够，在同学的指点下就从新定义了数据结构。
在新的数据结构中，使用邻接表来存储转换函数的，虽然数据结构部分对于顺序表 链表 邻接表的操作很陌生，但通过此次的实验让我对于数据结构中邻接表的使用有了很好的复习和回顾，也学会了邻接表中指针的使用和插入删除操作……
此次实验过程中，代码虽然全部都是本人自己编写，但很多不是我自己的思想，是从同学那剽窃来理解消化的，在别人和我讲述了代码之后，我自己独立的去写时，细节的地方仍然是漏洞百出，到处出错。我的代码能力太差，也常常因为这而自卑，但也不知如何去提升，虽然课本上的确定化会写，算法也能够理解和掌握，但是实现起来就是无从下手，所以动手能力差的同时，书本知识也得不到强化。 我会借编译原理实验的机会慢慢的熟悉代码，自己去想通算法，自己去实现算法。
我很感激姚老师的严厉要求，我相信我们院的老师都要像您和王爱平老师这样的就好了！
6. 附件：（程序和运行结果截图）
a) 程序：
#include
#include
#include
#include
#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 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; inextstate=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
本文档为【不确定有穷状态自动机的确定化实验报告】，请使用软件OFFICE或WPS软件打开。作品中的文字与图均可以修改和编辑，
图片更改请在作品中右键图片并更换，文字修改请直接点击文字进行修改，也可以新增和删除文档中的内容。
该文档来自用户分享，如有侵权行为请发邮件ishare@vip.sina.com联系网站客服，我们会及时删除。
[版权声明] 本站所有资料为用户分享产生，若发现您的权利被侵害，请联系客服邮件isharekefu@iask.cn，我们尽快处理。
本作品所展示的图片、画像、字体、音乐的版权可能需版权方额外授权，请谨慎使用。
网站提供的党政主题相关内容(国旗、国徽、党徽..)目的在于配合国家政策宣传，仅限个人学习分享使用，禁止用于任何广告和商用目的。
浙公网安备 33021202002483