文档下载 文档下载导航
设为首页 | 加入收藏
搜索 请输入内容:  
 导航当前位置: 文档下载 > 所有分类 > 高等教育 > 工学 > 计算理论试题及答案
侵权投诉

计算理论试题及答案

对于打算攻读计算机博士学位的有参考价值

《计算理论》 试题答案(2007级)

一、 证明:设M是一台识别语言B的DFA,交换M的接受状态与非接受状态得到一台新的DFA,则这台新DFA识别B的补集。因而,正则语言类在补运算下封闭。(8分)

参考答案:

设M’是一台将DFA M 的接受态与非接受态交换后的DFA,接下来证明M识别B语言,则M’识别B的补集:

假定M’识别x ,则对于x 在M’上运行将结束于M’的一个接受态,因为M和M’交换了接受态与非接受态,因此对于x运行于M,将会结束于一个非接受态,所以x∈/ B。类似地,如果x不被M’接受,则它一定被M接受。故M’恰好接受所有不被M接受的那些串,因此M’识别B的补集。

既然B是任意的正则语言,且我们已构造出一台自动机识别它的补集,它表明任何正则语言的补也是正则的。因此,正则语言类在补运算下封闭。

二、 令∑={0,1,+,=}和ADD={x=y+z | x,y,z是二制整数,且x是y与z的和},证明ADD不是正则的。(8分)

参考答案:

假定ADD是正则的。让P作为泵引理中的泵长度,选择S的串形式为1P=0P+1P作为ADD的一个成员。因为S有长度大于P,由泵引理保证它能分割成形如:S=xyz的三部分,满足泵引理的条件。泵引理的第三个条件有|xy|≤P,《它表明对于K≥1,y就是1K。这是xy2z是串1P+K=OP+1P,而它不是ADD的成员,由泵引理导出矛盾,因此ADD不是正则的。

三、 请将下述CFG转换成等价的乔姆斯基范式文法。(8分)

A→BAB|B|ε

B→00|ε

参考答案:

S0→AB|CC|BA|BD|BB|ε

A→AB|CC|BA|BD|BB

B→CC

C→0

D→AB

四、 请用泵引理证明语言A={ 0n#02n#03n | n≥0 }不是上下文无关的。(8分)

参考答案:

由泵引理,让P作为泵长度,s=0p#02p#03p ,接下来证明s=uvxyz不能进行泵抽取。

v和y都不能包含#,否则,xv2wy2z将超过2个#s ,因此,如果我们按#’s将s分成三段如:0p,02p,03p,至少有一段不包含v或y。因此,由于段之间的1:2:3的比例不再维持,xv2wy2z也不语言A中。故语言A={ 0n#02n#03n | n≥0 }不是上下文无关。的

第1页

你可能喜欢

  • 形式语言与自动机理论
  • 计算复杂性理论
  • 上下文无关
  • 形式语言与自动机答案
  • 快速排序
  • 图灵机模型
  • 计算理论基础 课件
  • 算法与程序设计

热门文档

相关文档

  • 计算理论试题及答案

    计算理论试题及答案_从业资格考试_资格考试/认证_教育专区 暂无评价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

    计算理论课后题及答案2_计算机软件及应用_IT/计算机_专业资料。计算理论课后题及答案第三章 上下文无关语言 3.1 略。 3.2 a. 利用语言 A={ambn cn m,...

  • 全国计算机一级 理论考试试题汇总及答案解析(2014)

    全国计算机一级 理论考试试题汇总及答案解析(2014)_IT认证_资格考试/认证_教育...它首次采用存储程序和程序控制使计算机自动工作 D、它主要用于弹道计算 答案:(C...

站点地图 | 文档上传 | 侵权投诉 | 手机版
本站所有资源均来自互联网,本站只负责收集和整理,均不承担任何法律责任,如有侵权等其它行为请联系我们.
文档下载 Copyright 2013 doc.guandang.net All Rights Reserved.  -  email