不确定有穷状态自动机的确定化试验报告

本文格式为Word版，下载可任意编辑——不确定有穷状态自动机的确定化试验报告编译原理试验报告(二)E01214055鲁庆河

1.试验名称：

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

2.试验目的：

a)输入：非确定有穷状态自动机NFAb)输出：确定化的有穷状态自动机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是NFAM状态集K的一个子集（即I∈K），则定义ε-closure（I）为：1.若Q∈I，则Q∈ε-closure（I）；

2.若Q∈I，则从Q出发经过任意条ε弧而能到达的任何状态Q’，则Q’∈closure（I）。3.状态集ε-closure（I）称为状态I的ε闭包。

假设NFAM＝(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

#defineN20//用于控制数组的最大长度

//用邻接表存储NFA和DFA的状态字母后继typedefstructadjvex

{//定义邻接表的邻接点域的数据表示charnextstate;//头结点状态的后继状态chararc;//弧

structadjvex*next;//指向该头结点状态的下一个后继状态

的指针}adjvex;

typedefstructheadvex

{//定义邻接表的头部的数据表示charstate;//状态

adjvex*firstarc;//指向第一个后继状态的指针

}headvex;

//定义两个邻接表的头部，为全局数组headvexNFA[N];//用邻接表存储的NFAheadvexDFA[N];//用邻接表存储的DFAcharAlp[N];//存储需要输入的行为集，即字母表

voidmain(){voiddesignby();//函数声明

voidclosure(chars,charset[N]);//求e_closure闭包函数

voidSpecial(charDFA_start[N],charnew_state[N][N]);//确

定化函数designby();inti,j;

charNFA_start[N];//存放NFA的初态

charDFA_start[N];//存放DFA的初态charNFA_final[N];//存放NFA的终态charDFA_final[N];//存放DFA的终态

charnew_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;jarc==A