实验四有穷自动机的确定化

《实验四有穷自动机的确定化》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、编译原理实验报告实验四：有穷状态自动机的确定化实验目的：1.熟练掌握DFA及NFA的定义及有关概念。2.理解并掌握确定的有穷自动机的化简等算法。实验要求：1.输入：非确定有限（穷）状态自动机。2.输出：确定化的有限（穷）状态自动实验原理：1.由定义可见，不确定有限自动机NFA与确定有限自动机DFA的主要区别是：（1）NFA的初始状态S为一个状态集，即允许有多个初始状态；（2）NFA中允许状态在某输出边上有相同的符号，即对同一个输入符号可以有多个后继状态。即DFA中的F是单值函数，而NFA中的F是多值函数。2.NFA确定化为DFA同一个字符串α可以由多条通路产生，而在实际

2、应用中，作为描述控制过程的自动机，通常都是确定有限自动机DFA，因此这就需要将不确定有限自动机转换成等价的确定有限自动机，这个过程称为不确定有限自动机的确定化，即NFA确定化为DFA。下面介绍一种NFA的确定化算法，这种算法称为子集法：（1）若NFA的全部初态为S1，S2，…，Sn，则令DFA的初态为：S＝[S1，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，…

3、，Sj}，a）={Si’，Si+1’，…，Sk’}为DFA的一个转换函数。若[Si’，Si+1’，…，Sk‘]不在K中，则将其作为新的状态加入到K中。（3）重复第2步，直到K中不再有新的状态加入为止。（4）上面得到的所有状态构成DFA的状态集K，转换函数构成DFA的F，DFA的字母表仍然是NFA的字母表∑。（5）DFA中凡是含有NFA终态的状态都是DFA的终态。3.NFA确定化的实质是以原有状态集上的子集作为DFA上的一个状态，将原状态间的转换为该子集间的转换，从而把不确定有限自动机确定化。经过确定化后，状态数可能增加，而且可能出现一些等价状态，这时就需要简化。实验内容

4、：1.程序代码如下：#include#include#includeusingnamespacestd;#definemax100structedge{stringfirst;//边的初始结点stringchange;//边的条件stringlast;//边的终点};intN;//NFA的边数vectorvalue;//求状态集合I的&-闭包，用&代替“空“stringclosure(stringa,edge*b){inti,j;for(i=0;i

5、+){if(b[j].first[0]==a[i]&&b[j].change=="&"){a=a+b[j].last[0];}}}returna;}//状态集合I的a弧转换stringmove(stringjihe,charch,edge*b){inti,j;strings="";for(i=0;i

6、hartt;for(i=0;i

7、;i>b[i].first;if(b[i].first=="#")break;elsecin>>b[i].change>>b[i].last;}N=i;cout<<"请输入该NFA的初态及终态："<>First>>Last;cout<<"请输入此NFA状态中的输入符号即边上的条件:"<>Change;T[x]=closure(First,b);T[x]=sort(T[x]);value.push_back(0);i=0;while(value[i]==0&&value.s