编译实验三(NFA转换成DFA和DFA化简)

...wd......wd......wd...实验三〔一〕NFADFA〔2小时〕一.问题描述NFADFA。1.实验目的：学会编程实现子集构造法。2.实验任务：存储NFA与DFA，编程实现子集构造法将NFA转换成DFA。3.实验内容：〔1〕确定NFA与DFA的存储格式，为3个以上测试NFA准备好存储文件。〔2〕用C或JAVA语言编写将NFA转换成DFA的子集构造法的程序。〔3〕经测试无误。测试不易。可求出NFA与DFA的语言集合的某个子集〔如长度小于某个N〕，再证实两个语言集合完全一样！〔4〕测试用例参考：将以下语言用RE表示，再转换成NFA使用：(a)以a开头和结尾的小字字母串；a(a|b|…|z)*a|a(b)不包含三个连续的b的，由字母a与b组成的字符串；(|b|bb)(a|ab|abb)*(c)(aa|b)*(a|bb)*二．算法描述NFA的输入：分别输入NFA的“字符集〞、“状态集〞、“开场状态〞、“承受状态集〞、“状态转换表〞等内容，并保存在设定的变量中。NFA的存储与读写：将上述NFA的五元组保存在一个文本文件中。存储格式如下所示〔以以下列图中NFA为例〕：2//字符集中的字符个数(以下两行也可合并成一行)ab//以空格分隔的字符集。4//状态个数(以下两行也可合并成一行)1234//状态编号。假设约定总是用从1开场的连续数字表示，则此行可省略1//开场状态的编号。假设约定为1，则此行可省略1//完毕状态个数。假设约定为1，则此行可省略3//完毕状态的编号321//状态1的所有出去的转换。按字符集中的字符顺序给出，并在最左边加上一列关于的转换。-1表示出错状态。多个状态用逗号分隔。-11-1-134-1-13基本算法描述存储格式如上所示，程序开场时，从文件中读取数据以获得NFA中的各种信息。根据子集构造法，构造相应的函数。子集构造法伪代码如下：初始时,

ε-closure(S0)是Dstates中唯一的状态且未被标记;whileDstates中存在一个未标记的状态Tdobegin 标记T;for每个输入符号adobeginU:=

ε-closure(move(T,a));ifU没在Dstates中then将U作为一个未被标记的状态添加到Dstates.Dtran

[

T,

a

]

:=

U

end

endε-closure的计算将T中所有状态压入栈stack;将ε-closure(T)初始化为T;whilestack不空dobegin将栈顶元素t弹出栈;for每个这样的状态u：从t到u有一条标记为

ε的边doifu不在ε-closure(T)中dobegin 将u添加到ε-closure(T); 将u压入栈stack中endend子集构造法的流程图：实验三〔二〕DFA化简〔2小时〕一.问题描述DFA化简实验目的：学会编程实现等价划分法化简DFA。实验任务：先完善DFA，再化简DFA。实验内容：〔1〕准备3个以上测试DFA文件。〔2〕DFA手动完善。〔状态转换映射要是满映射〕〔3〕用C或JAVA语言编写用等价划分法化简DFA的程序。〔4〕经测试无误。测试不易。可求出两个DFA的语言集合的某个子集〔如长度小于某个N〕，再证实两个语言集合完全一样！〔5〕编写实验报告。要求同实验一，不再详述。二．算法描述1.DFA的化简得到新的DFA之后，并没有完成任务，因为通过NFA转化成DFA不一定是最简的，也就是说，有多余的状态可以被删除，而我们需要的是得到一个唯一的最简的DFA[12]，也就是说，NFA转化为DFA之后，还需要化简，也就是最小化。2.化简的理论基础DFA的化简是指：寻找一个状态数最少的DFAM，使得L〔M〕=L〔M’〕。化简的方法是消去DFAM中的多余状态〔或无用状态〕，合并等价状态。DFA中的多余状态是指这样的状态：从开场状态出发，读入任何输入串都不能到达的那个状态；或者从这个状态没有通路到达终态。两个状态S和T等价是指：如果从状态S出发能读出某个字W而停于终态，从T出发也能读出同样的字W而停于终态；反之，从T出发能读出同样的字W而停于终态，从S出发也能读出某个字W而停于终态。3.化简的基本思想化简DFA的基本思想是指导它的状态分成一些互不相交的子集，每一个子集中的状态都不是等价的，不同子集中的状态可以由某个输入串来区别，最后将不能区别的每个子集用一个状态来做代表[13-15]，这种方法称为“分割法〞。具体过程是：〔1〕将M的所有状态分成两个子集——终态集和非终态集；〔2〕考察每一个子集，假设发现某子集中的状态不等价，将其划分为两个集合；〔3〕重复第〔2〕步，继续考察已得到的每一个子集，直到没有任何一个子集需要继续划分为止。这时DFA的状态被分成假设干个互不相交的子集。〔4〕从每个子集中选出一个状态做代表即可得到最简的DFA。三．程序分析通过本设计所要求到达的目的是：充分理解和掌握NFA，DFA以及NFA确定化过程的相关概念和知识，理解和掌握子集法的相关知识和应用，现在需要编程实现对输入NFA转换成DFA输出的功能。程序总框图如下：功能图如下：运行结果实验问题及心得通过此次对从NFA到DFA的转化和DFA的化简的设计，使我更好的理解了NFA确定化过程的相关知识，很好的理解了子集法的演算过程。还有DFA的化简过程有了更好地理解。经过屡次试验，在正确输入相关数据的情况下，程序能正常运行，当错误操作或输入错误数据时，程序将应错误自动关闭。经过这次课程设计,也让我深刻的认识到实践才是最重要的。书本只能教给我们基础知识,要怎样运用,将那些知识真正吸收,转化为自己的智慧,只有通过实践才能到达。编译原理是一门实用性很强，对我们的专业很有帮助的科目,我将会继续努力,不断增加自己的知识面,把编译原理学习的更好。附录#include<iostream>#include<string>#defineMAXS100usingnamespacestd;stringNODE;//结点集合stringCHANGE;//终结符集合intN;//NFA边数structedge{ stringfirst; stringchange; stringlast;};structchan{ stringltab; stringjihe[MAXS];};voidkong(inta){ inti; for(i=0;i<a;i++) cout<<'';}//排序voidpaixu(string&a){ inti,j; charb; for(j=0;j<a.length();j++) for(i=0;i<a.length();i++) if(NODE.find(a[i])>NODE.find(a[i+1])) { b=a[i]; a[i]=a[i+1]; a[i+1]=b; }}voideclouse(charc,string&he,edgeb[]){ intk; for(k=0;k<N;k++) { if(c==b[k].first[0]) if(b[k].change=="*") { if(he.find(b[k].last)>he.length()) he+=b[k].last; eclouse(b[k].last[0],he,b); } }}voidmove(chan&he,intm,edgeb[]){ inti,j,k,l; k=he.ltab.length(); l=he.jihe[m].length(); for(i=0;i<k;i++) for(j=0;j<N;j++) if((CHANGE[m]==b[j].change[0])&&(he.ltab[i]==b[j].first[0])) if(he.jihe[m].find(b[j].last[0])>he.jihe[m].length()) he.jihe[m]+=b[j].last[0]; for(i=0;i<l;i++) for(j=0;j<N;j++) if((CHANGE[m]==b[j].change[0])&&(he.jihe[m][i]==b[j].first[0])) if(he.jihe[m].find(b[j].last[0])>he.jihe[m].length()) he.jihe[m]+=b[j].last[0];}//输出voidoutputfa(intlen,inth,chan*t){ inti,j,m; cout<<"I"; for(i=0;i<len;i++) cout<<'I'<<CHANGE[i]<<""; cout<<endl<<"-------------------------"<<endl; for(i=0;i<h;i++) { cout<<''<<t[i].ltab; m=t[i].ltab.length(); for(j=0;j<len;j++) { kong(8-m); m=t[i].jihe[j].length(); cout<<t[i].jihe[j]; } cout<<endl; }}voidmain(){ edge*b=newedge[MAXS]; inti,j,k,m,n,h,x,y,len; boolflag; stringjh[MAXS],endnode,ednode,sta; cout<<"请输入NFA各边信息〔起点条件[空为*]终点〕，以#完毕："<<endl; for(i=0;i<MAXS;i++) { cin>>b[i].first; if(b[i].first=="#") break; cin>>b[i].change>>b[i].last; } N=i; /*for(j=0;j<N;j++) cout<<b[j].first<<b[j].change<<b[j].last<<endl;*/ for(i=0;i<N;i++) { if(NODE.find(b[i].first)>NODE.length()) NODE+=b[i].first; if(NODE.find(b[i].last)>NODE.length()) NODE+=b[i].last; if((CHANGE.find(b[i].change)>CHANGE.length())&&(b[i].change!="*")) CHANGE+=b[i].change; } len=CHANGE.length(); cout<<"结点中属于终态的是："<<endl; cin>>endnode; for(i=0;i<endnode.length();i++) if(NODE.find(endnode[i])>NODE.length()) { cout<<"所输终态不在集合中，错误！"<<endl; return; } //cout<<"endnode="<<endnode<<endl; chan*t=newchan[MAXS]; t[0].ltab=b[0].first; h=1; eclouse(b[0].first[0],t[0].ltab,b);//求e-clouse //cout<<t[0].ltab<<endl; for(i=0;i<h;i++) { for(j=0;j<t[i].ltab.length();j++) for(m=0;m<len;m++) eclouse(t[i].ltab[j],t[i].jihe[m],b);//求e-clouse for(k=0;k<len;k++) { //cout<<t[i].jihe[k]<<"->"; move(t[i],k,b);//求move(I,a) //cout<<t[i].jihe[k]<<endl; for(j=0;j<t[i].jihe[k].length();j++) eclouse(t[i].jihe[k][j],t[i].jihe[k],b);//求e-clouse } for(j=0;j<len;j++) { paixu(t[i].jihe[j]);//对集合排序以便比较 for(k=0;k<h;k++) { flag=operator==(t[k].ltab,t[i].jihe[j]); if(flag) break; } if(!flag&&t[i].jihe[j].length()) t[h++].ltab=t[i].jihe[j]; } } cout<<endl<<"状态转换矩阵如下："<<endl; outputfa(len,h,t);//输出状态转换矩阵 //状态重新命名 string*d=newstring[h]; NODE.erase(); cout<<endl<<"重命名："<<endl; for(i=0;i<h;i++) { sta=t[i].ltab; t[i].ltab.erase(); t[i].ltab='A'+i; NODE+=t[i].ltab; cout<<'{'<<sta<<"}="<<t[i].ltab<<endl; for(j=0;j<endnode.length();j++) if(sta.find(endnode[j])<sta.length()) d[1]=ednode+=t[i].ltab; for(k=0;k<h;k++) for(m=0;m<len;m++) if(sta==t[k].jihe[m]) t[k].jihe[m]=t[i].ltab; } for(i=0;i<NODE.length();i++) if(ednode.find(NODE[i])>ednode.length()) d[0]+=NODE[i]; endnode=ednode; cout<<endl<<"DFA如下："<<endl; outputfa(len,h,t); //输出DFA cout<<"其中终态为："<<endnode<<endl;//DFA最小化 m=2; sta.erase(); flag=0; for(i=0;i<m;i++) { //cout<<"d["<<i<<"]="<<d[i]<<endl; for(k=0;k<len;k++) { //cout<<"I"<<CHANGE[k]<<endl; y=m; for(j=0;j<d[i].length();j++) { for(n=0;n<y;n++) { if(d[n].find(t[NODE.find(d[i][j])].jihe[k])<d[n].length()||t[NODE.find(d[i][j])].jihe[k].length()==0) { if(t[NODE.find(d[i][j])].jihe[k].length()==0) x=m; else x=n; if(!sta.length()) { sta+=x+48; } else if(sta[0]!=x+48) { d[m]+=d[i][j]; flag=1; d[i].erase(j,1); //cout<<d[i]<<endl; j--; } break; //跳出n } }//n }//j if(flag) { m++;flag=0; } //cout<<"sta="<<sta<<endl; sta.erase(); }//k }//i cout<<endl<<"集合划分："; for(i=0;i<m;i++) cout<<"{"<<d[i]<<"}"; cout<<endl; //状态重新命名 chan*md=new