《实验四有穷自动机的确定化》由会员分享，可在线阅读，更多相关《实验四有穷自动机的确定化（6页珍藏版）》请在金锄头文库上搜索。
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 的初态为：SS1，S2 ， ，Sn，其中方括号用来表示若干个状态构成的某一状态。（2） 设 DFA 的状态集 K 中有一状态为Si ，Si+1，Sj ，若对某符号a ，在 NFA 中有 F（ Si，Si+1，Sj ，a）= Si，Si+1 ，Sk 则令 F
3、（ 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 上的一个状态，将原状态间的转换为该子集间的转换，从而把不确定有限自动机确定化。经过确定化后，状态数可能增加，而且可能出
4、现一些等价状态，这时就需要简化。实验内容：1.程序代码如下：#include#include#includeusing namespace std;#define max 100struct edgestring first;/边的初始结点string change;/边的条件string last;/边的终点;int N;/NFA 的边数vector value;/求状态集合 I 的&- 闭包，用&代替“空“string closure(string a,edge *b)int i,j;for(i=0;ibi.first;if(bi.first=#)break;elsecinbi.chang
5、ebi.last;N=i; coutFirstLast;coutChange;Tx=closure(First,b);Tx=sort(Tx);value.push_back(0);i=0;while(valuei=0&value.size() valuei=1;for(j=0;jChange.length();j+)ss=;ss=move(Ti,Changej,b);length=value.size();for(h=0;hlength;h+)if(Th=sort(closure(ss,b)break;if(h=length)T+x=sort(closure(ss,b);value.push_
6、back(0);i+;edge *DFA=new edgemax;for(i=0;i=x;i+)/构造 DFA 的各边for(j=0;jChange.length();j+)DFAd.first=Ti;DFAd.change=Changej;ss=;ss=sort(closure(move(Ti,Changej,b),b);for(m=0;m=x;m+)if(ss=Tm)DFAd+.last=Tm;cout此 NFA 构造的 DFA 的各边信息如下：endl 起点 条件 终点endl;for(i=0;id;i+) for(m=0;m=x;m+)if(DFAi.first=Tm)coutm DF
7、Ai.change;for(m=0;m=x;m+)if(DFAi.last=Tm)cout mendl;cout该 DFA 的初态为：;for(m=0;m=x;m+)for(j=0;jTm.length();j+)ss=Tm;if(ssj=First0)coutmendl;cout该 DFA 的终态为：;for(m=0;m=x;m+)for(j=0;jTm.length();j+)ss=Tm;if(ssj=Last0)coutm ;coutendl;system(pause);2 实验测试用例：0 & 10 & 71 & 21 & 42 a 34 b 53 & 65 & 66 & 16 & 77 a 88 b 99 b A#0 Aa b实验运行结果：
