编译原理实验五有穷自动机的确定化

1、实验五：有穷自动机的确定化一：要求1.输入： 非确定有限（穷）状态自动机。2.输出： 确定化的有限（穷）状态自动二：实验目的1. 熟练掌握DFA及NFA的定义及有关概念。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的初态为：SS1，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，Sj ，a）= Si，Si+1，Sk 为DFA的一个转换函数。若 Si，Si+1，Sk 不在K中，则

3、将其作为新的状态加入到K中。（3）重复第2步，直到K中不再有新的状态加入为止。（4）上面得到的所有状态构成DFA的状态集K，转换函数构成DFA的F，DFA的字母表仍然是NFA的字母表。（5）DFA中凡是含有NFA终态的状态都是DFA的终态。3. NFA确定化的实质是以原有状态集上的子集作为DFA上的一个状态，将原状态间的转换为该子集间的转换，从而把不确定有限自动机确定化。经过确定化后，状态数可能增加，而且可能出现一些等价状态，这时就需要简化。四：数据结构与算法struct edge string first;/边的初始结点string condition;/边上的条件string last;/

4、边的终点;string closure(string a,edge *b)/求状态集合I的&-闭包，用&代替"空"string move(string collection,char ch,edge *b)/状态集合I的a弧转换string sort(string t)/字符串排序五：出错分析1:缺少#include<vector>，会有很多错误。2:在数据结构的定义之中，字符与字符串的差别，本次实验室字符串而不是字符六：实验结果与分析七：源代码#include<iostream>#include<string>#incl

5、ude<vector>using namespace std;#define max 100int n;/NFA的边数vector<int> value;struct edge string first;/边的初始结点string condition;/边上的条件string last;/边的终点;string closure(string a,edge *b)/求状态集合I的&-闭包，用&代替"空"int i,j;for(i=0;i<a.length();i+)for(j=0;j<n;j+)if(bj.first0=ai

6、&&bj.condition="&")a=a+bj.last0;return a;string move(string collection,char ch,edge *b)/状态集合I的a弧转换int i,j;string s=""for(i=0;i<collection.length();i+) for(j=0;j<n;j+)if(bj.first0=collectioni&&bj.condition0=ch) s=s+bj.last;return s;string sort(string t)/字

7、符串排序int k,i,j;char tt;for(i=0;i<t.length()-1;i+)k=i;for(j=i+1;j<t.length();j+)if(tj<tk)k=j;tt=tk;tk=ti;ti=tt;return t;void main() int i,j,x=0,h,length,m,d=0; string Condition;/边上的条件 string First,Last;/初态，终态， string Tmax,ss; edge *b=new edgemax; cout<<".编译原理实验五：有穷自动机的确定化."<

8、;<endl; cout<<"请输入各边信息：起点 条件（空用&表示） 终点 并以输入#结束！"<<endl; for(i=0;i<max;i+)/存储每条边信息 cin>>bi.first; if(bi.first="#")break; else cin>>bi.condition>>bi.last; n=i; cout<<"请输入NFA的初态及终态："<<endl; cin>>First>>Last; c

9、out<<"请输入NFA状态中的输入符号即边上的条件:"<<endl; cin>>Condition; Tx=closure(First,b);/字符串数组存储空闭包并排序 Tx=sort(Tx); value.push_back(0); i=0; while(valuei=0&&value.size() valuei=1; for(j=0;j<Condition.length();j+) ss="" ss=move(Ti,Conditionj,b); length=value.size(); f

10、or(h=0;h<length;h+) if(Th=sort(closure(ss,b)break; if(h=length) T+x=sort(closure(ss,b); value.push_back(0); i+; edge *DFA=new edgemax; for(i=0;i<=x;i+)/构造DFA的各边 for(j=0;j<Condition.length();j+) DFAd.first=Ti; DFAd.condition=Conditionj; ss="" ss=sort(closure(move(Ti,Conditionj,b),b

11、); for(m=0;m<=x;m+) if(ss=Tm)DFAd+.last=Tm; cout<<"NFA构造的DFA的各边信息如下："<<endl<<"起点 条件 终点"<<endl; for(i=0;i<d;i+) for(m=0;m<=x;m+) if(DFAi.first=Tm)cout<<m<<" "<<DFAi.condition; for(m=0;m<=x;m+) if(DFAi.last=Tm)cout<<" "<<m<<endl; cout<<"确定后的DFA的初态为：" for(m=0;m<=x;m+) for(j=0;j<Tm.length();j+) ss=Tm; if(ssj=First0)cout<<m<<endl; cou