首页 范文大全 古典文学 职场知识 中国文学 公文书信 外国名著 寓言童话 百家讲坛 散文/诗歌 美文欣赏 礼仪知识 民俗风情
  • 工作总结
  • 工作计划
  • 心得体会
  • 竞聘演讲
  • 会议发言
  • 爱国演讲
  • 就职演说
  • 开业开幕
  • 思想学习
  • 征文演讲
  • 经验材料
  • 述职报告
  • 调研报告
  • 工作汇报
  • 年终总结
  • 申报材料
  • 学习体会
  • 企划方案
  • 活动方案
  • 技巧经验
  • 模板范例
  • 思想宣传
  • 经济工作
  • 工作报告
  • 组织人事
  • 反腐倡廉
  • 慰问贺电
  • 先进事迹
  • 思想汇报
  • 入党申请书
  • 党会发言
  • 先进性教育
  • 入团申请书
  • 个人简历
  • 演讲稿
  • 调查报告
  • 实习报告
  • 和谐社会
  • 观后感
  • 读后感
  • 作文范文
  • 自我鉴定
  • 讲话稿
  • 自查报告
    • 蒲公英阅读网 > 范文大全 > 活动方案 > 正文

    不确定有穷自动机确定化编译原理实验报告

    时间：2020-10-07 12:02:29 来源：蒲公英阅读网 本文已影响人 蒲公英阅读网手机站

    相关热词搜索：自动机 不确定 编译

    　编译原理实验报告

    　 实验名称

    　不确定有穷自动机的确定化

    　实验时间_____

    　2014 年 4 月 10 日_______

    　院

    　系_______管理信息工程学院_______

    　班

    　级_______11 计算机科学与技术____

    　学

    　号______201101020109____________

    　姓

    　名________姜高__________________

    　1、 、 实验目的 不确定有穷自动机的确定化

    　2、 、 实验原理 用子集构造算法构造子集加入子集族中直到收敛（所有构造的子集都已存在于子集族）为止。如原来不确定有穷自动机的五元组形式为：M=（K，&，F，S，Z），其中 K 为状态集，&为字母表，F为转换函数，S 为初始态，Z 为终态集。用子集族S 代替 K，新的转换函数 D 代替 F，形成新的五元组 M=（S，&，D，S，Z）即将原不确定有穷自动机转换为确定有穷自动机。

    　3、 、 实验内容 （1）

    　闭包计算：closure(I) （2）

    　转换函数：move(I,a)

    　4、 、 伪 伪 代码

    　假定构造的子集族为 S=（T1，T2。。。。。。），

    　 K 为状态集：

    　（1）

    　开始，令 closure(K0)为 S 中唯一成员，并且未被标记 （2）

    　WHILE（C 中存在尚未被标记的子集 T）

    　DO { 标记 T; For 每输入字母 a

    　DO { U:=closure(move(T,a)); If U 不在 S 中

    　then 将 U 作为未被标记的子集加在 S 中

    　} }

    　5. 代码实现 #include<iostream>

    　#include<string>

    　#define MAXS 100

    　using namespace std;

    　string NODE; //结点集合

    　string CHANGE; //终结符集合

    　 int N; //NFA 边数

    　 struct edge{

    　string first;

    　string change;

    　string last;

    　};

    　 struct chan{

    　string ltab;

    　 string jihe[MAXS];

    　};

    　 void kong(int a)

    　{

    　int i;

    　 for(i=0;i<a;i++)

    　cout<<" ";

    　}

    　 //排序

    　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(a[i])>NODE.find(a[i+1]))

    　{

    　 b=a[i];

    　a[i]=a[i+1];

    　a[i+1]=b;

    　}

    　}

    　void eclouse(char c,string &he,edge b[])

    　{

    　int k;

    　 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);

    　}

    　}

    　}

    　 void move(chan &he,int m,edge b[])

    　{

    　 int i,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];

    　}

    　 //输出

    　void outputfa(int len,int h,chan *t)

    　{

    　 int i,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;

    　}

    　}

    　 void main()

    　{

    　 edge *b=new edge[MAXS];

    　int i,j,k,m,n,h,x,y,len;

    　bool flag;

    　 string jh[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=new chan[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=new string[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 chan[m];

    　NODE.erase();

    　 cout<<endl<<"重命名："<<endl;

    　for(i=0;i<m;i++)

    　{

    　 md[i].ltab="A"+i;

    　NODE+=md[i].ltab;

    　 cout<<"{"<<d[i]<<"}="<<md[i].ltab<<endl;

    　}

    　 for(i=0;i<m;i++)

    　for(k=0;k<len;k++)

    　for(j=0;j<h;j++)

    　{

    　 if(d[i][0]==t[j].ltab[0])

    　{

    　 for(n=0;n<m;n++)

    　{

    　 if(!t[j].jihe[k].length())

    　break;

    　else

    　 if(d[n].find(t[j].jihe[k])<d[n].length())

    　{

    　 md[i].jihe[k]=md[n].ltab;

    　break;

    　}

    　}

    　 break;

    　}

    　}

    　 ednode.erase();

    　for(i=0;i<m;i++)

    　 for(j=0;j<endnode.length();j++)

    　 if(d[i].find(endnode[j])<d[i].length()&&ednode.find(md[i].ltab))

    　ednode+=md[i].ltab;

    　endnode=ednode;

    　 cout<<endl<<"最小化 DFA 如下："<<endl;

    　outputfa(len,m,md);

    　cout<<"其中终态为："<<endnode<<endl;

    　}

  • 150mw激光笔的危害_50mw的激光笔
  • [描写秋天美景的古诗大全精选]描写美景的古
  • [学院2017上半年工作总结范文] 2017科室工
  • 1993年属鸡的五行是什么_1993年属鸡是什么五行
  • 【秋天景色的古诗句精选大全】描写夏天景色
  • 【自制中药减肥方法】 瘦千金中药减肥加盟
  • 离别留言心酸的句子【给高中朋友写的离别留
  • 鼻塞的治疗方法【日常防止鼻塞的方法预防鼻
  • 欢庆课后反思总结:心理活动课后总结反思
    • 范文大全
    • 职场知识
    • 精美散文
    • 名著
    • 讲坛
    • 诗歌
    • 礼仪知识
    最新文章

    推荐访问

    大反思大讨论活动 保安全” 筑防线 “查思想 贡献伟大时代” “以青春之我 工作评议报告 创建活动综述 市社保局党支部 自述报告 “党员先锋示范岗” 党建德育工作 达标创星活动 “星级党支部”创建 评星定级管理 社会组织党支部 第四巡察组 新进年轻干部 委厅机关 党性教育培训班 履职能力建设专题培训班 新考录社区工作者 “头雁领航”重点培训班 党组织业务培训 能力提升培训会 赋能经济高质量发展 “五好”园区 三年攻坚行动 行政管理能力建设提升班 高质量发展能力提升培训班 市疾控系统 中基层管理人员 专业能力提升专题培训班 新发展预备党员 进驻工作 迎接审计组 讲评推进大会 “三抓三促”行动动员 “永不过时的红岩精神” 市委党史研究室 科学绿化现场会 深化以案促改 一体推进不敢腐不能腐不想腐 奋斗精神 专题辅导讲稿 坚守使命追求 涉密 《党史学习教育工作条例》 百年新征程 “百年定位” 党课教育

    本文不确定有穷自动机确定化编译原理实验报告由蒲公英阅读网整理提供，版权归原作者、原出处所有。

    Copyright © 蒲公英阅读网 All Rights Reserved.