




版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
1、实验六:DFA最小化 一:要求输入: DFA。输出: 最小化的DFA。二:实验目的1. 熟练掌握DFA及NFA的定义及有关概念。2. 理解并掌握确定的有穷自动机的最小化等算法。三:实验原理1.化简DFA关键在于把它的状态集分成一些两两互不相交的子集,使得任何两个不相交的子集间的状态都是可区分的,而同一个子集中的任何两个状态都是等价的,这样可以以一个状态作为代表而删去其他等价的状态,然后将无关状态删去,也就获得了状态数最小的DFA。2.DFA的化简算法:(1) 首先将DFA M的状态划分出终止状态集K1和非终止状态集K2。KK1K2 由上述定义知,K1和K2是不等价的。(2) 对各状态集每次按下
2、面的方法进一步划分,直到不再产生新的划分。设第i次划分已将状态集划分为k组,即:KK1(i)K2(i)Kk(i)对于状态集Kj(i)(j=1,2,k)中的各个状态逐个检查,设有两个状态Kj、 KjKj(i),且对于输入符号a,有:F(Kj,a)KmF(Kj,a)Kn如果Km和Kn属于同一个状态集合,则将Kj和Kj放到同一集合中,否则将Kj和Kj分为两个集合。(3) 重复第(2)步,直到每一个集合不能再划分为止,此时每个状态集合中的状态均是等价的。(4) 合并等价状态,即在等价状态集中取任意一个状态作为代表,删去其他一切等价状态。(5) 若有无关状态,则将其删去。根据以上方法就将确定有限自动机进
3、行了简化,而且简化后的自动机是原自动机的状态最少的自动机。四:数据结构与算法struct edge string first;/边的初始结点string condition;/边上的条件string last;/边的终点;string move(string collection,char ch,edge *b)/状态集合I的a弧转换int divide(edge *b,string change)/分割子集法进行DFA的最小化五:出错分析1:在数据结构的定义之中,字符与字符串的差别,本次实验室字符串而不是字符六:实验结果与分析七:源代码#include#includeusing namesp
4、ace std;#define max 100struct edge string first;/边的初始结点string condition;/边上的条件string last;/边的终点;int N;/NFA的边数string partmax;/分割子集string move(string collection,char ch,edge *b)/状态集合I的a弧转换int i,j;string s=;for(i=0;icollection.length();i+) for(j=0;jN;j+)if(bj.first0=collectioni&bj.condition0=ch) s=s+bj
5、.last;if(s=)return &;else return s;bool isexist(string s,string d)/判断子串是否存在在某一集合if(d!=&0=d.find(s)&d.find(s)=d.length()-1)return 1;else return 0;int divide(edge *b,string change)/分割子集法进行DFA的最小化int x,m,flag=2,flag0,i,j;string ss,part0max; flag0=flag;for(x=0;xchange.length();x+)for(m=0;mflag0;m+)for(i
6、=0;ipartm.length();i+)ss=move(partm.substr(i,1),changex,b);for(j=0;jflag;j+)if(isexist(ss,partj)part0j=part0j+partm.substr(i,1); if(ss=&)part0flag=part0flag+partm.substr(i,1);break;for(j=0;j=flag;j+)if(part0j!=&part0j!=partm)partflag+=part0j;part0j=;partm=;else part0j=;flag0=flag;return flag;void ma
7、in() int i,j,flag,x; string Condition;/边上的条件 string ss; edge *b=new edgemax; cout.编译原理实验六:DFA最小化.endl; cout请输入DFA各边信息:起点 条件(空用&表示) 终点 并以输入#结束。endl; for(i=0;ibi.first; if(bi.first=#)break; else cinbi.conditionbi.last; N=i; cout请输入该DFA的终态集合:part1; cout请输入该DFA的非终态集合:part0; cout请输入此DFA状态中的边上的条件:Conditio
8、n; flag=divide(b,Condition); coutDFA最小化划分的子集如下:endl; for(i=0;iflag;i+) if(parti!=)coutpartiendl; cout用状态A,B,C等代替子集:; for(i=0;iflag;i+) if(parti!=)coutparti,; coutendl则DFA最小化后的各边信息如下:endl; char lettersmax; char letter=A; for(i=0;iflag;i+) if(parti!=) lettersi=letter; +letter; for(i=0;iflag;i+) for(j=0;jCondition.length();j+) ss=move(parti,Conditionj,
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 2025至2030花卉种苗行业产业运行态势及投资规划深度研究报告
- 2025至2030鸟类食品配料行业发展趋势分析与未来投资战略咨询研究报告
- 2025安全生产工作思路
- 校园安全生产月工作总结
- 消防安全培训常用知识
- 汽修厂第二季度安全生产会议记录
- 新疆阿勒泰职业技术学院招聘事业编制专任教师考试真题2024
- 2025年福建省泉州市南安市高三一模物理试卷及答案
- 河北科技大学选聘考试真题2024
- 2025年虚拟现实技术在虚拟现实教育技术创新成果中的应用:教学设计效果分析报告
- 高考语文复习:各模块思维导图、例题
- 山东省济宁市(2024年-2025年小学四年级语文)统编版期末考试((上下)学期)试卷及答案
- 乐器设备供货项目实施方案及售后服务方案
- DL∕T 1901-2018 水电站大坝运行安全应急预案编制导则
- DL∕T 1076-2017 火力发电厂化学调试导则
- DB6101-T 3186-2024 物业服务评价技术规范
- 抖音红娘话术
- 创设生活化教学与情境模拟
- 砂石料供应、运输、售后服务方案
- 2023年安徽省公务员《申论》试题及答案解析(C卷)
- 血糖监测小讲课ppt
评论
0/150
提交评论