计算理论模拟试题及答案
更新时间:2023-09-14 03:01:01 阅读量: 教学研究 文档下载
- 表象计算理论推荐度:
- 相关推荐
《计算理论》复习题
1、设语言A={w | w含有子串0101,即对某个x和y,w=x0101y},字母表为{0,1}
a. 画出识别A的DFA的状态图。
b. 画出识别A的NFA的状态图(规定状态数为5)。 解: a. b.
2、把下图的有穷自动机转换成正则表达式。
1 0 0 1 1 0 0 1 0,1 0,1 0 1 0 1 0,1 a b 1 b a 2 解: 1、加新的开始状态和新的结束状态
a b s 1 b a 2 a 2、删除状态1,通过状态1的转换有s→1→2、2→1→2
3、删除状态2
a∪ba*b s a*b 2 a s a*b(a∪ba*b)* a 3、设语言A={www | w∈{a,b}*},利用泵引理证明A不是正则语言。
证明:假设A是正则的。设p是泵引理给出的关于A的泵长度。 令S=ababab,
∵S是A的一个成员且S的长度大于p,所以泵引理保证S可被分成3段S=xyz且满足泵引理的3个条件。根据条件3,y中只含a,所以xyyz中第一个a的个数将比后两个a的个数多,故xyyz不是A2的成员。违反泵引理的条件1,矛盾。 ∴A不是正则的。
4、证明在3.1节开始部分给出的文法G2中,字符串the girl touches the boy with the flower 有两个不同的最左派生,叙述这句话的两个不同的意思。 解: G2如下:
<句子>→<名词短语><动词短语>
<名词短语>→<复合名词>|<复合名词><介词短语> <动词短语>→<复合动词>|<复合动词><介词短语> <介词短语>→<介词><复合名词> <复合名词>→<冠词><名词>
<复合动词>→<动词>|<动词><名词短语> <冠词>→a_|the_
<名词>→boy_|girl_|flower_ <动词>→touch_|1ikes_|Sees_ <介词>→with_
答:
p
p
p
1. 第一种最左派生
<句子>?<名词短语><动词短语>?<复合名词><动词短语>?<冠词><名词><动词短语> ?a_<名词><动词短语>?a_girl_<动词短语>?a_girl_<复合动词> ?a_girl_<动词>< 名词短语>?a_girl_touches_< 名词短语>
? a_girl_touches_<复合名词><介词短语>?a_girl_touches_<冠词><名词><介词短语> ?a_girl_touches_the_<名词><介词名词>?a_girl_touches_the_boy_<介词短语>
?a_girl_touches_the_boy_<介词><复合名词>?a_girl_touches_the_boy_with_<复合名词> ?a_girl_touches_the_boy_with_<冠词><名词>?a_girl_touches_the_boy_with_the_<名词>
?a_girl_touches_the_boy_with_the_flower 含义是 :女孩碰这个带着花的男孩 2. 第二种最左派生
<句子>?<名词短语><动词短语>?<复合名词><动词短语>?<冠词><名词><动词短语> ?a_<名词><动词短语>?a_girl_<动词短语>?a_girl_<复合动词><介词短语> ?a_girl_<动词>< 名词短语><介词短语>?a_girl_touches_< 名词短语><介词短语> ?a_girl_touches_<冠词><名词><介词短语>?a_girl_touches_the_< 名词><介词短语> ?a_girl_touches_the_boy_<介词短语>?a_girl_touches_the_boy_<介词><复合名词> ?a_girl_touches_the_boy_with_<复合名词>?a_girl_touches_the_boy_with_<冠词><名词> ?a_girl_touches_the_boy_with_the_<名词> ?a_girl_touches_the_boy_with_the_flower 含义是: 女孩用花碰这个男孩
5、有自动机M,接受语言L={WcW R | W∈{a,b}*∪c},请给出这台PDA的形式定义、状态图,并非形式地描述它的运行。
6、设语言A={01 01 | n≧0},利用泵引理证明A不是上下文无关的。 证明:假设A是上下文无关的。设p是泵引理给出的关于A的泵长度。
令字符串S=01 01,
∵S是A的一个成员且S的长度大于p,所以泵引理保证S可被分成5段S=uvxyz且满足泵引理的3个条件。 字串vxy一定横跨S的中点,否则,如果vxy位于S的前一半,把S抽成uv xy z时,1移到后一半的第一个位置,因此uv xy z不可能是A的成员。如果vxy位于S的后一半,把S抽成uv xy z时,0移到后一半的最后一个位置,因此uv xy z不可能是A的成员。如果字串vxy横跨S的中点,把S抽成u x y,它形如 01 01,其中i和j不可能等于p。于是,S不能被抽取,从而A不是上下文无关的。
7、设语言A={w | w至少含有3个1},字母表为{0,1}
p i
j p
2
2
2
2
2
2
2
2
p p
p p
n n
n n
a. 给出产生语言A的上下文无关文法。
b. 给出产生语言A的下推自动机的非形式描述和状态图。 解: a. S→A1A1A1A
A→0A|1A|?
读输入中的符号。每读一个1,把一个1推入栈,每读1个0,不读栈也不写栈。同时非确定性地转移,并把1个1弹出栈。如果能转移三次,共弹出三个1,则接受这个输入,并继续读输入符号直至结束。否则拒绝这个输入。
8、检查图灵机的形式定义,回答下列问题并解释你的推理:
a. 图灵机能在它的带子上写下空白字符吗? b. 图灵机能只包含一个状态吗? 解:a. 能。因为空白符属于带字母表?;
B. 不能。因为qaccept?qreject,至少应有两个状态。
9、证明正则语言类在并运算下封闭。
10、设INFINITEDFA={|A是一个DFA,且L(A)是一个无限语言}。证明INFINITEDFA是可判定的。
证明:设计一个判定INFINITEDFA的TM M即可。 M=“对于输入,其中A是一个DFA:
1) 按照引理2.32 证明中的构造方法,把DFA A转换成等价的正则表达式。 2) 扫描正则表达式,如果包含星号运算符*,则接受;否则拒绝。”。
11、设B是{0,1}上所有无限序列的集合,用对角化方法证明B是不可数的。
0, ???
1, ??1 ?,1?? ?,1?? 0, ??? 1, ??? ?,1?? 证明:为证明B是不可数的,必须证明在B和N之间不存在对应。下面用反证法证之。假设在B和N之间存在对应f,现在的任务是证明它没有应有的性质。因为它是一个对应,必须能将N的所有元素与B的所有元素进行配对。如果能找到B中的一个x,它和N中的任何元素都不能配对,则找到了矛盾。
为此,实际构造出这样一个x。方法如下:在选择它的每一位数字时,都使得:x不同
于某个无限序列,且此无限序列已与N中的一个元素配对。这样就能保证x不同于任何已配对的无限序列。
用一个例子来说明这个思路。假设对应f存在,且设f(1) = 010101…,f(2) = 101010…,
f(3) =…等等。则f将1和010101…配对,将2和101010…配对,依此类推。
要保证对每个n都有x ≠ f(n)。为保证x ≠ f(1),只要保证x的第一位数字不同于f(1)
= 010101…的第一位数字,即不是数字0,令它为1。为保证x ≠ f(2),只要保证x的第二位数字不同于f(2) = 101010…的第一位数字,即不是数字0,令它为1。以这种方法继续下去,就能够得到x的所有数字。不难知道,对任意n,x都不是f(n),因为x与f(n)在第n位上不同。
12、设EQCFG={
1)在输入
如果R判定EQCFG,则S判定ALLCFG。但由定理6.10,ALLCFG是不可判定的。故EQCFG也是不可判定的。
13、证明:如果A是图灵可识别的,且A≤mA,则A是可判定的。
证明:因为A≤mA <=>A≤m A 且A为图灵可识别的,根据定理6.22,A图灵可识别的。 根据5.16,由A和A都是图灵可识别的,所以A是可判定的。
14、证明所有的图灵可识别问题都映射可归约到ATM。
正在阅读:
计算理论模拟试题及答案09-14
新人教版小学数学五年级下册单元复习试卷全册 - 图文06-01
解剖章节练习题-05-10
九洲国际饭店托管保洁方案08-16
某生态保护治理植被恢复项目施工组织设计11-14
全国通用版2019版高考化学大一轮复习第十二章有机化学基础增分补课12有机信息题中的信息学案11-26
体育说课稿(水平二)04-21
2020人教版九年级语文上《话说千古风流人物》练习题11-29
在职研究生2023年度个人工作总结范文03-22
- 公务员上岸同学告诉你,怎样走出面试中常见的十大误区
- 作表率,我们怎么办(办公室主任)
- 乘务员安全责任书
- 增员面试流程
- 河南省焦作市规模以上租赁和商务服务业企业应付职工薪酬数据洞察报告2019版
- 最新4社区工作者面试题
- 个人简历表
- 男教工体检必检项目
- 河南省兰考县规模以上租赁和商务服务业企业应付职工薪酬数据洞察报告2019版
- 兼职译员测试稿
- 河南省开封市规模以上租赁和商务服务业企业应付职工薪酬数据洞察报告2019版
- 永州职业技术学院校园总体规划-永州职业学院
- 最新5、培训科长笔试题(答案)
- 2019雅商酒店境外人员登记培训稀有资料,不可错过
- 小学教师求职简历范文
- 红酒知识与礼仪
- 春节给领导拜年的短信拜年词
- 2019年上半年中小学教师资格证结构化面试真题1
- 20XX年县干部培训工作目标
- 硬笔试听课
- 模拟试题
- 答案
- 理论
- 计算
- 第八章黑龙江饮食文化
- 关于对特岗教师进行年度考核的通知
- 政府和社会资本合作(PPP)-自来水公司管理运营项目实施方案(编制大纲) - 图文
- 1ZR发动机故障排除 - 图文
- 蚌埠市人民政府关于推进农业百佳工程加快现代农业发展的实施意见
- 审计实训要求
- 职工医疗互助难点和对策的调研
- 煤化工发展现状简介
- 抗肿瘤药
- 新人教版 七年级数学上册 第一章《有理数》备课集锦(教案学案习题精选)
- 初2017级重庆中考数学 二次函数综合压轴题专练(无答案) - 图文
- 离散数学基础
- 农商银行信贷业务操作流程
- 中国构造运动表
- 希赛网络工程师27卷3
- 课堂管理PK机制
- 钢的热处理
- 英德市特色小镇投资建设研究报告(目录) - 图文
- 20种制度
- 第十四章 岩浆岩形成大地构造环境