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

PAGE PAGE 2 . . 实验五：有穷自动机的确定化 一：要求 1.输入： 非确定有限（穷）状态自动机。 2.输出： 确定化的有限（穷）状态自动 二：实验目的 熟练掌握DFA及NFA的定义及有关概念。 理解并掌握确定的有穷自动机的化简等算法。 三：实验原理 1.由定义可见，不确定有限自动机NFA与确定有限自动机DFA的主要区别是： （1）NFA的初始状态S为一个状态集，即允许有多个初始状态； （2）NFA中允许状态在某输出边上有相同的符号，即对同一个输入符号可以有多个后继状态。即DFA中的F是单值函数，而NFA中的F是多值函数。 2. NFA确定化为DFA 同一个字符串α可以由多条通路产生，而在实际应用中，作为描述控制过程的自动机，通常都是确定有限自动机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，…，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上的一个状态，将原状态间的转换为该子集间的转换，从而把不确定有限自动机确定化。经过确定化后，状态数可能增加，而且可能出现一些等价状态，这时就需要简化。 四：数据结构与算法 struct edge{ string first;//边的初始结点 string condition;//边上的条件 string last;//边的终点 }; string closure(string a,edge *b)//求状态集合I的-闭包，用代替空 string move(string collection,char ch,edge *b)//状态集合I的a弧转换 string sort(string t)//字符串排序 五：出错分析 1:缺少#includevector，会有很多错误。 2:在数据结构的定义之中，字符与字符串的差别，本次实验室字符串而不是字符 六：实验结果与分析 七：源代码 #includeiostream #includestring #includevector using namespace std; #define max 100 int n;//NFA的边数 vectorint value; struct edge{ string first;//边的初始结点 string condition;//边上的条件 string last;//边的终点 }; string closure(string a,edge *b)//求状态集合I的-闭包，用代替空 { int i,j; for(i=0;ia.length();i++) { for(j=0;jn;j++) { if(b[j].first[0]==a[i]b[j].condition==) { a=a+b[j].last[0]; } } } return a; } string move(string collection,char ch,edge *b)//状态集合I的a弧转换 { int i,j; string s=; for(i=0;icollection.length();i++) { for(j=0;jn;j++) { if(b[j].first[0]==collection[i]b[j].condition[0]==ch) s=s+b[j].last; } } return s; } string sort(string t)//字符串排序 { int k,i,j; char tt; for(i=0;it.length()-1;i++) { k=i; for(j=i+1;jt.length