《c语言编程NFA确定化》由会员分享，可在线阅读，更多相关《c语言编程NFA确定化（12页珍藏版）》请在金锄头文库上搜索。
1、.NFA 确定化为 DFA1实验目的设计并实现将NFA 确定化为DFA 的子集构造算法，从而更好地理解有限自动机之间的等价性，掌握词法分析器自动产生器的构造技术。该算法也是构造LR 分析器的基础。2实验要求设计并实现计算状态集合 I 的闭包的算法_Closure(I) 和转换函数 Move(I,a) ，并在此基础 上 实 现 子 集 构 造 算 法 Subset_Construction 。 利 用 该 从 NFA 到 DFA 的 转 换 程 序Subset_Construction ，任意输入一个NFA N=（ S,s0,F），输出一个接收同一语言的DFA M=（S,s0,F）。3实验内容(
2、1) 令 I 是 NFA N 的状态集 S 的一个子集， I 的闭包的Closure(I)构造规则如下：(a) 若 s I，则 sClosure(I) ；(b) 若 s_Closure(I)且(s, )=s 而 s? Closure(I) ，则 s_Closure(I)根据上面的规则，下面给出了一个计算I 的闭包的算法_Closure(I)。SET S;SETClosure(input)SET *input;S=input;/*初始化*/push();/*把输入状态集中的全部状态压入栈中*/while( 栈非空 )Nfa_state i;pop();/*把栈顶元素弹出并送入i*/if(存在(i
3、, )=j)if(j 不在 S 中 ) 把 i 加到 S 中 ; 把 j 压入栈中 ;Word 文档.return S;/*返回_Closure(input) 集合*/完成上述算法的设计。(2) 令 I 是 NFA N 的状态集 S 的一个子集， a, 转换函数 Move(I,a) 定义为：Move(I,a)= Closure(J)其中， J=s|sI 且(s,a)=s转换函数Move(I,a) 的设计通过调用 _Closure(input) 实现，完成该函数的设计。(3)从 NFA N 构造一个与其等价的 DFA M 的子集构造算法，就是要为 DFA M 构造状态转换表 Trans，表中的每
4、个状态是 NFA N 状态的集合， DFA M 将“并行”地模拟NFA N面对输入符号串所有可能的移动。下面给出了子集构造算法Subset_Construction的框架，请完成其设计过程。有关数据结构：States是一个 M 的数组，每个状态有两个域，set 域存放 N 的状态集合， flg域为一标识。Trans是 M 的转移矩阵（输入字母表元素个数最大状态数），Transia=下一状态。iM 的当前状态号a输入符号， aNstates M 的下一新状态号S定义 M 的一个状态的N 的状态集初始化：States0.set= Closure(N 的初态 )States0.flg=FALSENs
5、tates=1i=0S= Trans 初始化为无状态- while(Statesi 的 flg 为 FALSE)Statesi.flg=TRUE;for( 每个输入符号a)S=Closure(Move(Statesi.set,a);if(S 非空 )if(States 中没有 set 域等于S 的状态 )StatesNstates.set=S;StatesNstates.flg=FALSE;Transia= Nstates+;elseTransia= States中一个 set 域为 S 的下标 ;此算法的输出M 主要由Trans 矩阵描述，其中省略了每个状态是否为终态的描述，Word 文档.
6、应加以完善。4实验程序 ;#include#include#define MAXS 100using namespace std;string NODE; / 结点集合string CHANGE; / 终结符集合int N;/NFA 边数struct edgestring first;string change;string last;struct chanstring ltab;string jiheMAXS;void kong(int a)int i;for(i=0;ia;i+)cout ;Word 文档./ 排序void paixu(string &a)int i,j;char b;fo
7、r(j=0;ja.length();j+)for(i=0;iNODE.find(ai+1)b=ai;ai=ai+1;ai+1=b;void eclouse(char c,string &he,edge b)int k;for(k=0;khe.length()he+=bk.last;eclouse(bk.last0,he,b);void move(chan &he,int m,edge b)int i,j,k,l;l=he.jihem.length();for(i=0;ik;i+)for(j=0;jhe.jihem.length()he.jihem+=bj.last0;for(i=0;il;i+
8、)for(j=0;jhe.jihem.length()he.jihem+=bj.last0;Word 文档./ 输出void outputfa(int len,int h,chan *t)int i,j,m;cout I;for(i=0;ilen;i+)coutICHANGEi;coutendl-endl;for(i=0;ih;i+)cout ti.ltab;m=ti.ltab.length();for(j=0;jlen;j+)kong(8-m);m=ti.jihej.length();coutti.jihej;coutendl;Word 文档.void main()edge *b=new e
9、dgeMAXS;int i,j,k,m,n,h,x,y,len;bool flag;string jhMAXS,endnode,ednode,sta;cout 请输入 NFA 各边信息（起点条件 空为 * 终点），以 #结束： endl;for(i=0;ibi.first;if(bi.first=#) break;cinbi.changebi.last;N=i;/*for(j=0;jN;j+)coutbj.firstbj.changebj.lastendl;*/for(i=0;iNODE.length()NODE+=bi.first;if(NODE.find(bi.last)NODE.length()NODE+=bi.last;Word 文档.if(CHANGE.find(bi.change)CHANGE.length()&(bi.change!=*)CHANGE+=bi.change;len=CHANGE.length();cout 结点中属于终态的是： endnode;for(i=0;iNODE.length()
