资源描述:
《c语言编程NFA确定化》由会员上传分享,免费在线阅读,更多相关内容在工程资料-天天文库。
1、实用标准NFA确定化为DFA1.实验目的设计并实现将NFA确定化为DFA的子集构造算法,从而更好地理解有限自动机之间的等价性,掌握词法分析器自动产生器的构造技术。该算法也是构造LR分析器的基础。2.实验要求设计并实现计算状态集合I的ε闭包的算法ε_Closure(I)和转换函数Move(I,a),并在此基础上实现子集构造算法Subset_Construction。利用该从NFA到DFA的转换程序Subset_Construction,任意输入一个NFAN=(S,Σ,δ,s0,F),输出一个接收同一语言的DFAM=(S’,
2、Σ,δ’,s0’,F’)。3.实验内容(1)令I是NFAN的状态集S的一个子集,I的ε闭包的ε_Closure(I)构造规则如下:(a)若s∈I,则s∈ε_Closure(I);(b)若s∈ε_Closure(I)且δ(s,ε)=s’而s’∉ε_Closure(I),则s’∈ε_Closure(I)根据上面的规则,下面给出了一个计算I的ε闭包的算法ε_Closure(I)。SETS;SETε_Closure(input)SET*input;{S=input;/*初始化*/push();/*把输入状态集中的全部状态压入栈中
3、*/while(栈非空){Nfa_statei;pop();/*把栈顶元素弹出并送入i*/if(存在δ(i,ε)=j)if(j不在S中){把i加到S中;文档大全实用标准把j压入栈中;}}returnS;/*返回ε_Closure(input)集合*/}完成上述算法的设计。(1)令I是NFAN的状态集S的一个子集,a∈Σ,转换函数Move(I,a)定义为:Move(I,a)=ε_Closure(J)其中,J={s’
4、s∈I且δ(s,a)=s’}转换函数Move(I,a)的设计通过调用ε_Closure(input)实现,完
5、成该函数的设计。(2)从NFAN构造一个与其等价的DFAM的子集构造算法,就是要为DFAM构造状态转换表Trans,表中的每个状态是NFAN状态的集合,DFAM将“并行”地模拟NFAN面对输入符号串所有可能的移动。下面给出了子集构造算法Subset_Construction的框架,请完成其设计过程。有关数据结构:States[]是一个M的数组,每个状态有两个域,set域存放N的状态集合,flg域为一标识。Trans[]是M的转移矩阵(输入字母表Σ元素个数×最大状态数),Trans[i][a]=下一状态。iM的当前状态号a
6、输入符号,a∈ΣNstates[]M的下一新状态号S定义M的一个状态的N的状态集初始化:States[0].set=ε_Closure({N的初态})States[0].flg=FALSENstates=1i=0S=ФTrans初始化为无状态’-’while(States[i]的flg为FALSE){States[i].flg=TRUE;for(每个输入符号a∈Σ){S=ε_Closure(Move(States[i].set,a));if(S非空)if(States中没有set域等于S的状态){States[Nstat
7、es].set=S;States[Nstates].flg=FALSE;Trans[i][a]=Nstates++;}elseTrans[i][a]=States中一个set域为S的下标;}}文档大全实用标准此算法的输出M主要由Trans矩阵描述,其中省略了每个状态是否为终态的描述,应加以完善。4.实验程序;#include#include#defineMAXS100usingnamespacestd;stringNODE;//结点集合stringCHANGE;//终结符集合intN;
8、//NFA边数structedge{stringfirst;stringchange;stringlast;};structchan{stringltab;stringjihe[MAXS];};voidkong(inta){inti;for(i=0;iNODE.find(a[i+
9、1])){b=a[i];a[i]=a[i+1];a[i+1]=b;}}voideclouse(charc,string&he,edgeb[]){intk;for(k=0;k