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

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

1、不确定有限状态自动机的确定化【实验目的】　输入：非确定有限（穷）状态自动机。输出：确定化的有限（穷）状态自动机。【实验原理】　　　同一个字符串α可以由多条通路产生，而在实际应用中，作为描述控制过程的自动机，通常都是确定有限自动机DFA，因此这就需要将不确定有限自动机转换成等价的确定有限自动机，这个过程称为不确定有限自动机的确定化，即NFA确定化为DFA。　　　NFA确定化的实质是以原有状态集上的子集作为DFA上的一个状态，将原状态间的转换为该子集间的转换，从而把不确定有限自动机确定化。经过确定化后，状态数可能增加，而且可能出现一些等价

2、状态，这时就需要简化。【程序代码】#include#include#includeusingnamespacestd;#definemax100structedge{stringfirst;//边的初始结点stringchange;//边的条件stringlast;//边的终点};intN;//NFA的边数vectorvalue;stringclosure(stringa,edge*b){inti,j;for(i=0;i

3、N;j++){if(b[j].first[0]==a[i]&&b[j].change=="&"){a=a+b[j].last[0];}}}returna;}stringmove(stringjihe,charch,edge*b){inti,j;strings="";for(i=0;i

4、intk,i,j;chartt;for(i=0;i

5、以输入#结束。"<>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;wh

6、ile(value[i]==0&&value.size()){value[i]=1;for(j=0;j

7、];for(i=0;i<=x;i++)//构造DFA的各边{for(j=0;j

8、r(m=0;m<=x;m++){if(DFA[i].first==T[m])cout<