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

《不确定有穷状态自动机的确定化实验报告》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、编译原理实验报告(二)E01214055鲁庆河1.实验名称：不确定有穷状态自动机的确定化2.实验目的：a)输入：非确定有穷状态自动机NFAb)输出：确定化的有穷状态自动机DFA3.实验原理：a)NFA确定化为DFA同一个字符串2可以山多条通路产生，而在实际应用中，作为描述控制过程的自动机，通帘都是确定有限自动机DFA,因此这就需要将不确定冇限自动机转换成等价的确定冇限自动机，这个过程称为不确定冇限自动机的确定化，即Nb'A确定化为DFA。b)NFA的确定化算法——子集法：•若NFA的全部初态为S2,…，Sn,

2、则令DFA的初态为：S=［S„S2,…，SJ,其中方括号用來表示若干个状态构成的某一状态。•设DFA的状态集K中冇一状态为［Si,Sl+1,…，SJ,若对某符号在NFA小冇F({S”…，S」},a)=(Si',Si",…，S「},则令F({Si,Shi,…，Sj},a)={S；,,…,}为DFA的一个转换函数。若［S「，Sw,…，SJ］不在K中，则将其作为新的状态加入到K中。•重复第2步，直到K中不再有新的状态加入为止。•上面得到的所有状态构成DI'A的状态集K,转换函数构成DEA的I',DI'A的字母表仍然

3、是NEA的字母表£。•DFA中凡是含冇NFA终态的状态都是DFA的终态。c)closure(I)函数，moved,a)函数的假设I是NFAM状态集K的一个子集(即IWK〉，则定义e-closure(T)为：1.若QWI,则Qee-closure(I)；2.若QG1,则从Q出发经过任意条£弧而能到达的任何状态Q',则Q'eclosure(Do3.状态集£-closure(I)称为状态I的£闭包。假设NFAM=(K,E,F,S,Z)，若IEK,aEL,则定义【—closure(J),其中J是所冇从closure(

4、I)出发,经过一条a弧而到达的状态集。NFA确定化的实质是以原有状态集上的子集作为DFA上的一个状态，将原状态间的转换为该子集间的转换，从而把不确定有限口动机确定化。经过确定化后，状态数可能增加，而且可能出现一些等价状态,这时就需要简化。4.实验思路：(数据结构及变量设计等)typedefstruatadjvex旧{charnextstate;chararc;/Wvstruatadjvex*next;}adjvex;typedefstructheadvex日{charstate;adjvex*firstar

5、c;}headvex;charcharcharcharcharNFA_start[N];DFA_start[N];NFA_final[N];DFA_final[N];x/vwwwWVWWWWVVVWVWzSAAWvWvWv-x/vwwwWWWWWWSAAAAWzXAAWvWvWv-newstate[N][N];WVWWvVvVWWWWvvoidmain()田｛voidclosure(charsfcharset[N])VvAAAAAAAAAA/WWWWW«>AAAA/WWVWWAAAAAAAAAAA/WvW

6、AAAAAA/WW»E]{voidmove(charFrom[N],chararcfcharTo[N])VWWWvWWVWWVWWWWWWWWVWWWWWVWvWSAA/WWWWWWWVS田｛voidOrder(chara；N])QEW*ZvWW'Zv^zv>/«vwWv**v1vSA/WvVvVvoidSpecial(charDFA_st且Mt[N],charnew_state[N][N])//7?&^(Vr?i^rnhZ^-iTFiS+亜旦缶—//x■、'VWWvAZ'z*

7、AAA>A/vAZyvA/vA>A/vA/WVvAZvWVW»^AA>Ayw«VvVvAAAAAAAAAAAAA//vAZ>AAA>A

8、AAAA/VVVVVVVVVXAAA^charI；wwvwx*charE;charIE[10]；structtransforms*next;-}transforms;在新的数据结构中，使用邻接表來心储转换两数的，址然数据结构部分对于顺序表链表邻接表的操作很陌生，但通过此次的实验让我对于数据结构中邻接衣的使用冇了很好的复习和冋顾，也学会了邻接衣中指针的使用和插入删除操作……■侈鋅E八rT人4NkrXg