版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
学号:******班级:******姓名:******日期:2023目录题目及需求分析……………3设计分析……………………3调试分析……………………7用户手册……………………7测试结果……………………7总结…………7源代码………8题目:NFA转换为等价的DFA实习时间:【问题描述】以定理“设L为一个由不确定的有穷自动机接受的集合,则存在一个接受L的确定的有穷自动机”为理论基础,设计算法实现将不确定的有穷自动机(NFA)转换为与之等价的确定的有穷自动机(DFA)。【基本要求】确定能够表示FA的合适的结构,以便FA的输入和输出设计的算法既要成功实现题目要求的功能,又要高效、鲁棒程序中的函数、变量等命名要规则,可读性要强(易懂)需求分析(1)要将以状态转换图表示的NFA转换为DFA,首先应设计一个结构来表示FA,以便图形式的FA便于输入和输出。(2)设计合适的算法来实现NFA的确定化,这里用子集法来构造等价的DFA。(3)测试数据:课本P59例4.8转换前的NFA转换后的DFA2.设计//Triad(三元组):S→aB即(S,a,B)//Triad(三元组):S→aB即(S,a,B)structTriad{charstart;charedge;charend;};集合与栈使用库里面的标准集合、栈。即包含头文件set、stack文件结构程序不是很复杂,加之使用到的数据结构是标准库里的,文件只有一个N2D.cpp,其中有#include<set>和#include<starck>。程序基本框架概览structTriad{};//FA的基本组成结构structTriad{};//FA的基本组成结构intmain(){初始化工作;determined();//确定化}e_closure(){}//求ε闭包move(){ }//求集合的x弧转换determined(){}//确定化主要函数的实现伪代码具有简明扼要的特点,利用伪代码子来表示程序流程有利于理解和后续实现。子集法伪代码:s0s0←NFA的开始状态集合T←e-closure(s0)把T加入到子集簇C(未标记)while(集合U←在C中找到一个未标记的集合){标记U;for(对于每一种输入即a、b......){U←e-closure(move(T,a))if(U不是C的子集)把U加入到子集簇C(未标记)有T→aU}}此外,求ε的传递闭包要利用栈这一数据结构做辅助,其伪代码如下://求e-closure(T)的伪代码//求e-closure(T)的伪代码将T中的所有状态全都压入栈S、集合Uwhile(S非空){t←取栈顶元素;for(每个从t状态能通过空串转换得到的状态s)if(s不在U中){把状态s加入U;把状态s压入S;}}returnU;//集合U即为所求的ε闭包再在伪代码的基础上来编写这些核心函数就方便多了,具体代码如下:set<char>e_closure(set<char>T,TriadG[],intN)set<char>e_closure(set<char>T,TriadG[],intN)//求ε的传递闭包{ set<char>U=T;//U用来存放T中元素的ε闭包 stack<char>S;//辅助栈 set<char>::iteratorit;//用于集合遍历的迭代器 for(it=U.begin();it!=U.end();it++)//将U中的元素全部压栈 S.push(*it); chart; while(!S.empty())//栈非空 { t=S.top();//栈顶元素 S.pop(); for(inti=0;i<N;i++)//查找元素的ε闭包 { if(G[i].start==t&&G[i].edge=='*')//找到元素的ε闭包 { U.insert(G[i].end);//将其放入集合U S.push(G[i].end);//将其压栈 } } } returnU;}voiddetermined(TriadG[],intN,char*input,intn){voiddetermined(TriadG[],intN,char*input,intn){//确定化函数的实现 cout<<endl<<"确定后的DFA:"<<endl; boolmarked[MAX_NODES];//用于标示集合 for(inti=0;i<MAX_NODES;i++) marked[i]=false; set<char>C[MAX_NODES];//存放确定化过程中产生的集合 chars0=G[0].start; set<char>T0,T1; T0.insert(s0); T1=e_closure(T0,G,N);//始态的ε闭包 C[0]=T1; i=0; while(!C[i].empty()&&marked[i]==false&&i<MAX_NODES){ marked[i]=true; for(intj=0;j<n;j++){ if(input[j]!='*'){ set<char>U=e_closure(move(C[i],input[j],G,N),G,N); if(!U.empty()){ boolinC=false; intk=0; while(!C[k].empty()&&k<MAX_NODES){ if(U==C[k]){ inC=true; break; } k++; } if(!inC){ k=0; while(!C[k].empty()&&k<MAX_NODES){ k++; } C[k]=U; } cout<<i<<"→"<<input[j]<<k<<endl; } } } i++; } //下面求出确定化后的终态 cout<<"终态为:"; i=0; while(!C[i].empty()){ boolis_final_state=false; set<char>::iteratorit; for(it=C[i].begin();it!=C[i].end();it++){ if(*it=='#'){ is_final_state=true; break; } } if(is_final_state)cout<<i<<","; i++; } cout<<endl;}调试分析优点分析:NFA的输入只要求输入边的条数即可开始输入组成FA的基本结构(即三元组),而有多少引起状态转换的输入都交给程序自己去完成,这一点就显得很简洁,对于用户来说也便捷!缺点分析:没有可视化,整个程序的输入输出是通过控制台完成的。解决办法:可合适的使用MFC可视化编程完成(这个有余力可以考虑一下)。用户手册该程序的使用十分简单,直接按要求输入相应数据就是。测试数据及测试结果课本P59例4.8:总结优点通过这次的实习,对编译原理NFA、DFA及之间的等价转换有了更加深刻的理解,也学会了利用伪代码来设计程序,由框架到细节的实现,这种设计相当便利高效。团队成员之间交流思想取长补短也让我学到了好多思想和方法。7.源代码#include<set>#include<stack>};set<char>e_closure(set<char>,Triad[],int);set<char>move(set<char>,char,Triad[],int);voiddetermined(Triad[],int,char*,int);constintMAX_NODES=20;intmain(){ intN; cout<<"请输入边数:"<<endl; cin>>N; Triad*G=newTriad[N]; cout<<"请输入正规文法(*代表ε,#代表终态,约定输入时先输入以始态开始的三元组):"<<endl; for(inti=0;i<N;i++){ cin>>G[i].start>>G[i].edge>>G[i].end; } set<char>Edge; for(intj=0;j<N;j++){ Edge.insert(G[j].edge); } intn=Edge.size(); char*input=newchar[n]; set<char>::iteratorit; j=0; for(it=Edge.begin();it!=Edge.end();it++){ input[j]=*it; j++; } determined(G,N,input,n); return0;}set<char>e_closure(set<char>T,TriadG[],intN){ set<char>U=T; stack<char>S; set<char>::iteratorit; for(it=U.begin();it!=U.end();it++) for(inti=0;i<N;i++) { if(G[i].start==t&&G[i].edge=='*') { U.insert(G[i].end); S.push(G[i].end); } } } returnU;}set<char>move(set<char>I,chara,TriadG[],intN){ set<char>U; set<char>::iteratorit; for(it=I.begin();it!=I.end();it++) for(inti=0;i<N;i++){ if(G[i].start==*it&&G[i].edge==a) U.insert(G[i].end); } returnU;}voiddetermined(TriadG[],intN,char*input,intn){ cout<<endl<<"确定后的DFA:"<<endl; boolmarked[MAX_NODES]; for(inti=0;i<MAX_NODES;i++) marked[i]=false; set<char>C[MAX_NODES]; chars0=G[0].start; set<char>T0,T1; T0.insert(s0); T1=e_closure(T0,G,N); C[0]=T1; i=0; while(!C[i].empty()&&marked[i]==false&&i<MAX_NODES){ marked[i]=true; //下面被注释代码可用于输出图中求出来的集合 /* */ for(intj=0;j<n;j++){ if(input[j]!='*'){ set<char>U=e_closure(move(C[i],input[j],G,N),G,N); if(!U.empty()){ boolinC=false; intk=0; while(!C[k].empty()&&k<MAX_NODES){ if(U==C[k]){ inC=true; break; } k++; } if(!inC){ k=0; while(!C[k].empty()&&k<MAX_NODES){ k++; }
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
评论
0/150
提交评论