对于打算攻读计算机博士学位的有参考价值
《计算理论》 试题答案(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 }不是上下文无关。的
计算理论试题及答案_从业资格考试_资格考试/认证_教育专区 暂无评价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...
热门文档