对于打算攻读计算机博士学位的有参考价值
五、 下面的语言都是字母表{0,1}上的语言,请以实现描述水平级给出判定这些语言的图灵机:(8分)
1、A={w|w包含相同个数的0和1}。
2、B={w|w所包含的0的个数是1的个数的二倍}。
参考答案:
1、对于输入串w
1)、扫描带子且标记第一个没有被标记的0,如果没有未被标记的0,则跳到第4步,否则,将指针移到带子的最前端。
2)、扫描带子且标记第一个没有被标记的1,如果没有未被标记的1,则拒绝。
3)、将指针移到带子的最前端且重复第1步
4)、将指针移到带子的最前端,扫描带子看是否还有未被标记的1,如果没有则接受,否则拒绝。
2、略
六、 只写一次图灵机是一个单带图灵机,它在每个带方格上最多只能改变其内容一次(包括带上的输入区)。证明图灵机模型的这个变形等价于普通的图灵机模型。(8分)
参考答案:
我们首先模拟一个可以写两次的普通图灵机,这个写两次的图灵机相当于一个单带图灵机通过将整带内容考贝到带子已用部分的右边来实现。考贝过程通过一个一个字符地操作,标记已考贝的字符。这个过程改变带子两次,一次是写字符,另一次是标记它被考贝。标记在带子上,当在标记位置考贝时,带子的内容按照图灵机更新。
为了便于写一次图灵机模拟,除每个格子用两个格子代替外,其它操作如前面一致。第一个用来写原始内容,第二个用来写标记内容。这样就可以模拟写两次图灵机,依此类推,可以模拟写N次图灵机。因此图灵机模型的这个变形等价于普通的图灵机模型。
七、 设A={<M>|M是DFA,它不接受任何包含奇数个1的串},证明A是可判定的。(8分)
参考答案:
如下的TM X 判定A
X=“ 对于输入<M>,M是DFA
构造一个DFA O ,接受任何包含奇数个1的串
构造DFA B 使
依据定理4.4,对于输入<B>运行TM T, T判定EDFA
如果T接受,则接受。否则T拒绝,则拒绝。
八、 设C是一个语言。证明C是图灵可识别的,当且仅当存在一个可判定语言D,使得C={x| y (<x,y>∈D)}。(8分)
参考答案:
要求从两个方向证明。首先,我们假定D是存在的,TM识别C对于输入x ,查找y 使得<x,y>∈D。如果y 找到则接受,否则继续找。
另一方向,假定C被图灵机M 识别。定义一语言B为 {<x,y>|x在|y|内接受X}。语言B是可判定的,
计算理论试题及答案_从业资格考试_资格考试/认证_教育专区 暂无评价0人阅读0次下载举报文档 计算理论试题及答案_从业资格考试_资格考试/认证_教育专区。 ...
研究生 计算机理论题库《计算理论》复习题 1、设语言 A={w w 含有子串 0101,即对某个 x 和 y,w=x0101y} ...
统计学原理计算题试题及答案(最新整理)_经管营销_专业资料。统计学原理计算题试题及答案(最新整理) 牛人制作,大学生必看电大专科统计学原理计算题试题及答案 计算...
职称计算机考试理论模拟试题及答案_其它考试_资格考试/认证_教育专区。职称计算机...版式 D.样式 22.Excel2000 中函数(D)计算选定的单元格区域内数值的最大值。...
国民收入核算理论试题及答案_其它考试_资格考试/认证_教育专区。2章 二.判断...6.用支出法计算的 GNP 包括消费支出、投资支出、政府支出和净出口的 总和 7....
计算机理论考试试题答案 暂无评价0人阅读0次下载举报文档计算机理论考试试题考号: 姓名: 分数: 一、 填空题(每题...
11页 免费 计算机理论基础试题及答案 14页 10财富值 计算理论试题及答案 3页 免费 计算机基础知识试题详解 10页 免费 计算理论课件打印 72页 1财富值...
计算机考试理论部分试题及答案_其它考试_资格考试/认证_教育专区。一、单项选择(第 1-172 题,选择一个正确的答案,将相应的 字母填入题入题内的括号中。每题 ...
计算理论课后题及答案2_计算机软件及应用_IT/计算机_专业资料。计算理论课后题及答案第三章 上下文无关语言 3.1 略。 3.2 a. 利用语言 A={ambn cn m,...
全国计算机一级 理论考试试题汇总及答案解析(2014)_IT认证_资格考试/认证_教育...它首次采用存储程序和程序控制使计算机自动工作 D、它主要用于弹道计算 答案:(C...
热门文档