文档下载 文档下载导航
设为首页 | 加入收藏
搜索 请输入内容:  
 导航当前位置: 文档下载 > 所有分类 > 资格考试/认证 > 从业资格考试 > 2008级_计算理论_试卷答案
侵权投诉

2008级_计算理论_试卷答案

一、一台DFA M的状态图如右:(8分)

1、请指出M的起始状态是什么?

2、请指出M的接受状态集是什么?

3、对输入aabb,M经过的状态序列是什么?

4、请给出机器M的形式描述。

参考答案:

1、q1

2、{q2}

3、q1,q2,q3,q1,q1

4、M=({q1,q2,q3},{a,b},δ, q1,{q2}).

转换函数δ

2008级_计算理论_试卷答案

五、上下文无关文法CFG=(V,∑,R,E),其中V={E,T,F},∑={a,+,×,(,)},规则为:

E→E+T|T

T→T×F|F

F→(E)|a

请给出如下字符串的派生: (8分)

1、a+a

2、((a))

参考答案:

1、E=>E+T=>T+T=>F+T=>F+F=>a+F=>a+a

2、E=>T=>F=>(E)=>(T)=>(F)=>((E))=>((T))=>((F))=>((a))

六、语言A={w|w所包含的0的个数不是1的个数的二倍}是字母表{0,1}上的语言,请以实现描述水平级给出判定该语言的图灵机:(8分)

参考答案:

对于输入串w

扫描带子且标记第一个没有被标记的0,如果没有未被标记的0,则到第5步

继续标记下一个没有被标记的0,如果没有,则接受,否则,将指针移到带子的最前端

扫描带子且标记第一个没有被标记的1,如果没有,则接受

将指针移到带子的最前端,重复第1步

将指针移到带子的最前端,扫描 带子,看是否有未被标记的1,如果没有则拒绝,否则接受。

八、设A={<R,S>|R和

2008级_计算理论_试卷答案

S是正则表达式,且L(R)

参考答案: L(S)},证明A是可判定的。(8分)

当且仅当如下的TM X判定A

X=“对于输入< R,S>,R,S是正则表达式

依据定理4.4,对于输入<E>运行TM T ,T判定EDFA

如果T接受,则接受。否则T拒绝,则拒绝。

1

第1页

你可能喜欢

热门文档

相关文档

  • 2008级_计算理论_试卷答案

    2008级_计算理论_试卷答案_工学_高等教育_教育专区 暂无评价0人阅读0次下载举报文档 2008级_计算理论_试卷答案_工学_高等教育_教育专区。 ...

  • 2008级_计算理论_试卷答案

    《计算理论》试卷答案(2008 级) 计算理论》试卷答案( 答案一、一台 DFA M 的状态图如右:(8 分) 1、请指出 M 的起始状态是什么? 2、请指出 M 的接受...

  • 理论试卷答案

    国际贸易理论试卷答案 2页 1下载券 2008级_计算理论_试卷答... 4页 免费 ...理论试卷 共 40 分) 1、你在调试计算机时,你在 A 机器上给 B 机器发消息...

  • 计算理论习题答案CHAP1new

    计算理论习题答案CHAP4new 6页 1财富值 计算理论习题答案CHAP3new 11页 1财富值 计算理论习题答案 CHAP2 n... 9页 1财富值 2008级_计算理论_试卷答案 4...

  • 08级《计算机组成原理》期末考试卷(A卷)参考答案与评分...

    08级《计算机组成原理》期末考试卷(A卷)参考答案与评分标准 隐藏>> 计算机科学学院 学年度第二 计算机科学学院 2009-2010 学年度第二学期 级本科《计算机组成...

  • 计算理论试题及答案

    《计算理论》 试题答案(2007 级) 计算理论》 试题答案(一、 证明:设 M 是一台识别语言 B 的 DFA,交换 M 的接受状态与非接受状 态得到一台新的 DFA,则这...

  • 合肥学院2008级-计算机辅助化工计算试卷-参考答案

    合肥学院2008级-计算机辅助化工计算试卷-参考答案_其它考试_资格考试/认证_教育专区。合肥学院2008级-计算机辅助化工计算试卷-参考答案...

  • 2008级计算机科学概论试卷(答案)

    2008级计算机科学概论试卷(答案)_韩语学习_外语学习_教育专区。2008级计算机科学概论试卷(答案),考试作弊将带来严重后果! 华南理工大学期末考试 2008级《计算机科学...

  • 2008级研究生高等电磁场理论期末试卷期末试卷参考答案

    2008 级高等电磁场理论期末考试参考答案 1、答: (1)麦克斯韦方程组的四种形式:...积分形式也可以用于各种情况,但是计算复杂,适用于推导固定的和移动的边界条件,...

  • 2008初级维修电工理论试卷.答案

    2008初级维修电工理论试卷.答案_从业资格考试_资格考试/认证_教育专区。初级维修... 2014一级建造师考试 一级建造师《建设工程项目管理》 《建设工程经济》计算题...

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