c语言编程NFA确定化

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=F

5、ALSENstates=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 矩阵描述，其中省略了每个状态是否为终态的描述，Wo

6、rd 文档.应加以完善。4实验程序 ;#include<iostream>#include<string>#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;i<a;i+)cout<<'

7、; 'Word 文档./ 排序void paixu(string &a)int i,j;char b;for(j=0;j<a.length();j+)for(i=0;i<a.length();i+)if(NODE.find(ai)>NODE.find(ai+1)b=ai;ai=ai+1;ai+1=b;void eclouse(char c,string &he,edge b)int k;for(k=0;k<N;k+)if(c=bk.first0)if(bk.change="*")Word 文档.if(he.find(bk.la

8、st)>he.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;i<k;i+)for(j=0;j<N;j+)if(CHANGEm=bj.change0)&&(he.ltabi=bj.first0)if(he.jihem.find(bj.last0)>he.jihem.length()he.jihem+=bj.last0;for(i=0;i<l;i+)for(j=0

9、;j<N;j+)if(CHANGEm=bj.change0)&&(he.jihemi=bj.first0)if(he.jihem.find(bj.last0)>he.jihem.length()he.jihem+=bj.last0;Word 文档./ 输出void outputfa(int len,int h,chan *t)int i,j,m;cout<<" I"for(i=0;i<len;i+)cout<<'I'<<CHANGEi<<""cout<

10、<endl<<"-"<<endl;for(i=0;i<h;i+)cout<<' '<<ti.ltab;m=ti.ltab.length();for(j=0;j<len;j+)kong(8-m);m=ti.jihej.length();cout<<ti.jihej;cout<<endl;Word 文档.void main()edge *b=new edgeMAXS;int i,j,k,m,n,h,x,y,len;bool flag;string jhMAXS,endnod

11、e,ednode,sta;cout<<" 请输入 NFA 各边信息（起点条件 空为 * 终点），以 #结束： "<<endl;for(i=0;i<MAXS;i+)cin>>bi.first;if(bi.first="#") break;cin>>bi.change>>bi.last;N=i;/*for(j=0;j<N;j+)cout<<bj.first<<bj.change<<bj.last<<endl;*/for(i=0;i<N

12、;i+)if(NODE.find(bi.first)>NODE.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<<" 结点中属于终态的是： "<<endl;cin>>endn

13、ode;for(i=0;i<endnode.length();i+)if(NODE.find(endnodei)>NODE.length()cout<<" 所输终态不在集合中，错误！"<<endl;return;/cout<<"endnode="<<endnode<<endl;chan *t=new chanMAXS;t0.ltab=b0.first;h=1;eclouse(b0.first0,t0.ltab,b);/ 求 e-clouse/cout<<t0.ltab&l

14、t;<endl;for(i=0;i<h;i+)for(j=0;j<ti.ltab.length();j+)for(m=0;m<len;m+)Word 文档.eclouse(ti.ltabj,ti.jihem,b);/ 求 e-clousefor(k=0;k<len;k+)/cout<<ti.jihek<<"->"move(ti,k,b);/ 求 move(I,a)/cout<<ti.jihek<<endl;for(j=0;j<ti.jihek.length();j+)eclouse(t

15、i.jihekj,ti.jihek,b); / 求 e-clousefor(j=0;j<len;j+)paixu(ti.jihej);/ 对集合排序以便比较for(k=0;k<h;k+)flag=operator=(tk.ltab,ti.jihej);if(flag)break;if(!flag&&ti.jihej.length()th+.ltab=ti.jihej;Word 文档.cout<<endl<<"状态转换矩阵如下： "<<endl;outputfa(len,h,t);/ 输出状态转换矩阵/ 状态重新

16、命名string *d=new stringh;NODE.erase();cout<<endl<<"重命名： "<<endl;for(i=0;i<h;i+)sta=ti.ltab;ti.ltab.erase();ti.ltab='A'+i;NODE+=ti.ltab;cout<<''<<sta<<"="<<ti.ltab<<endl;for(j=0;j<endnode.length();j+)if(sta.find(endnodej)<sta.length()d1=ednode+=ti.ltab;for(k=0;k<h;k+)for(m=0;m<len;m+)if(sta=tk.jihem)tk.jihem=ti.ltab;for(i=0;i