湖南大学-计算理论实验
更新时间:2023-09-15 06:18:01 阅读量: 资格考试认证 文档下载
- 湖南大学绩点计算推荐度:
- 相关推荐
目录
实验A---- ADFA的可判定性 ......................................................................................... 2
1、 问题描述 ...................................................................................................... 2 2、 算法设计思路 .............................................................................................. 3 3、 实验总结 ...................................................................................................... 3 4、 AC代码 ......................................................................................................... 3 实验B----CFG是P成员 ................................................................................................ 4
1、 问题描述 ...................................................................................................... 4 2、 算法设计思路 .............................................................................................. 5 3、 实验总结 ...................................................................................................... 5 4、 AC代码 ......................................................................................................... 5 实验C----NFA转换为DFA ............................................................................................. 8
1、 问题描述 ...................................................................................................... 8 2、 算法设计思路 .............................................................................................. 9 3、 实验总结 ...................................................................................................... 9 4、 AC代码 ......................................................................................................... 9 实验D----两个数的互素判定 ..................................................................................... 12
1、问题描述 ........................................................................................................ 12 2、算法设计思路 ................................................................................................ 13 3、实验总结 ........................................................................................................ 13 4、AC代码 ........................................................................................................... 13 实验E----可判定的DFA的空问题 ............................................................................. 14
1、问题描述 ........................................................................................................ 14 2、算法设计思路 ................................................................................................ 15 3、实验总结 ........................................................................................................ 15 4、 AC代码 ....................................................................................................... 15
实验A---- ADFA的可判定性
1、
Problem description ADFA={< B,w >|B是DFA,w是串,B接收w}证明:ADFA是可判定的。 实验方法:编写一个算法/程序,对于任意给定的输入,可以判定ADFA。 Input 问题描述
有多个测试序列,测试结束于测试文件结束; 每个测试序列的第一行为几个正整数n m t a分别表示有n个状态,从a开始m个小写字母组成的字符集,第一个状态默认为起始状态。t个接受状态和a个测试串,接下来为一个n行m列的矩阵S,其中S[i][j]表示第i行第j列,意义为状态i经过字母j到达状态S[i][j]。接下来有t个数字,表示t个接受状态值,然后是a行,每行一个串表示待测试的串。 Output 对于每个字符串输出YES表示该DFA接受该串,NO表示不接受。 Sample Input 3 3 1 2 2 3 2 3 3 3 3 3 3 2 a b Sample Output YES NO
2、 算法设计思路
A:首先将输入的状态转移矩阵保存在S数组中,其中其中S[i][j]表示第i行第j列,意义为状态i经过字母j到达状态S[i][j]。
B:对每一个输入的串W,从after(after表示每次转换后的状态,初始为起始状态)开始,按照每一个字符,得到相应的后继状态,保存在after中。
C:最后判断accept[after]的值,即串在DFA上运行之后最终状态是否可接受。
3、 实验总结
总的来说这一题比较容易(有点太水了),只要把输入串的每一个字符按照前面的状态得到后继状态,并不断的走下去,直到串的最后一个字符,就可以得到最后的状态,再根据其是否处在接受态,给出相应的输出
4、 AC代码
#include
long s[1000][1000]; //存储转移矩阵 long accept[1000]; //存储接受状态 int main(){
while(cin>>n>>m>>t>>a){ memset(s,0,sizeof(s));
memset(accept,0,sizeof(accept)); for(int i = 1;i<=n;i++){ for(int j = 1;j<=m;j++) cin>>s[i][j]; }
for(int i = 0;i
accept[temp] = 1; }
while(a--){
string temps; cin>>temps;
int after = 1;
for(int i = 0;i if(accept[after]==1) cout<<\ else cout<<\ }} return 0; } 实验B----CFG是P成员 1、 问题描述 Problem description 上下文无关文法CFG G是否派生某个串W。采用动态规划(Dynamic Programming)设计一个一个多项式时间的验证算法。 Input 输入第一行为一个正整数n,接下来n行为一个满足乔姆斯基范式的文法描述。然后一个正整数m,接下来m行为m个小写字母组成的字符串(长度小于100) 表示m个待测试的串。 Output 对于每一个测试串返回\或者\,表示该串是否能被文法派生出来。 Sample Input 4 S->AB A->AB|a B->BC|b C->CA|CC|c 3 ab ac bc Sample Output yes no no 2、 算法设计思路 A: 找出所有A->b型规则 B: 找出所有A->BC型规则 C: 考察每一个长为1的子串 D: 考察L长度的子串 E: 检查起始变元是否在table[0][n]中 3、 实验总结 (1)刚开始用栈和转移矩阵来进行状态的切换,想要先把CFG转换为一个PDA,在根据PDA接受串的情况来判断(因为题目要求线性时间复杂度),后来发现转换成PDA的时候,每一个转移矩阵里应该是一个状态的集合。 (2)原本定义一个set 4、 AC代码 #include int n,m; 串 while(cin>>n) { string *cfg; cfg=new string[n]; for(int i=0;i //n行满足乔姆斯基范式的文法描述, m行待测字符 //CFG文法描述 //输入CFG文法 //输入待测字符串数量 //待测字符串
正在阅读:
湖南大学-计算理论实验09-15
2019年整理入党积极分子关于3.14西藏暴乱事件思想汇报09-17
张村镇中心学校素质教育开放周活动方案03-11
读《活着》有感02-22
武威市餐厨垃圾处理管理实施方案06-02
菊花颂作文350字07-11
数据结构(c语言版)复习资料02-01
乡镇上半年产业发展工作计划08-02
描写和你回家的散文03-30
- 梳理《史记》素材,为作文添彩
- 2012呼和浩特驾照模拟考试B2车型试题
- 关于全面推进施工现场标准化管理实施的通知(红头文件)
- 江西省房屋建筑和市政基础设施工程施工招标文件范本
- 律师与公证制度第2阶段练习题
- 2019-2020年最新人教版PEP初三英语九年级上册精编单元练习unit6训练测试卷内含听力文件及听力原文
- 小升初数学模拟试卷(十四) 北京版 Word版,含答案
- 认识创新思维特点 探讨创新教育方法-精选教育文档
- 00266 自考 社会心理学一(复习题大全)
- 多媒体在语文教学中的运用效果
- 派出所派出所教导员述职报告
- 低压电工作业考试B
- 18秋福建师范大学《管理心理学》在线作业一4
- 中国铝业公司职工违规违纪处分暂行规定
- 13建筑力学复习题(答案)
- 2008年新密市师德征文获奖名单 - 图文
- 保安员培训考试题库(附答案)
- 银川市贺兰一中一模试卷
- 2011—2017年新课标全国卷2文科数学试题分类汇编 - 1.集合
- 湖北省襄阳市第五中学届高三生物五月模拟考试试题一
- 湖南大学
- 理论
- 实验
- 计算
- 六国论学案(学生版)
- 射线检测计算公式总结
- 2015年二级建造师考试真题及答案解析《机电实务》网友版1
- 2008年5月同济大学授予博士学位名单 - 图文
- 浙大远程公司金融作业集
- 2017年高中地理学考、选考“双考”模拟试卷(2)
- 工程及材料供方管理作业指引 - 附表
- 金洞子滑坡勘查报告 - 图文
- 2015年河南省高考对口升学汽车类基础课试题卷
- 2011全国高校市场营销大赛
- 探究仁和中学教室日光灯安置的合理性-杭州余杭区临平第三中学 - 图文
- 形状和位置公差与检测
- 货场课程设计指导书
- 【复习参考】2019届高三历史复习 模块四英国的制度创新和北美大陆上的新体制 学案 word版含答案 -
- 吉林大学第一医院历年授予硕士学位名录
- 译林英语4A知识点汇总
- 英国伦敦的大学学院有春季入学吗,申请要求及优劣势是怎样的?
- 关于进一步加强企业安全生产工作的实施意见
- 接触网设备技术要求 - 图文
- 项目法人单位-安全生产标准化考试试题