一、一台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}).
转换函数δ

五、上下文无关文法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和

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
2008级_计算理论_试卷答案_工学_高等教育_教育专区 暂无评价0人阅读0次下载举报文档 2008级_计算理论_试卷答案_工学_高等教育_教育专区。 ...
《计算理论》试卷答案(2008 级) 计算理论》试卷答案( 答案一、一台 DFA M 的状态图如右:(8 分) 1、请指出 M 的起始状态是什么? 2、请指出 M 的接受...
国际贸易理论试卷答案 2页 1下载券 2008级_计算理论_试卷答... 4页 免费 ...理论试卷 共 40 分) 1、你在调试计算机时,你在 A 机器上给 B 机器发消息...
计算理论习题答案CHAP4new 6页 1财富值 计算理论习题答案CHAP3new 11页 1财富值 计算理论习题答案 CHAP2 n... 9页 1财富值 2008级_计算理论_试卷答案 4...
08级《计算机组成原理》期末考试卷(A卷)参考答案与评分标准 隐藏>> 计算机科学学院 学年度第二 计算机科学学院 2009-2010 学年度第二学期 级本科《计算机组成...
《计算理论》 试题答案(2007 级) 计算理论》 试题答案(一、 证明:设 M 是一台识别语言 B 的 DFA,交换 M 的接受状态与非接受状 态得到一台新的 DFA,则这...
合肥学院2008级-计算机辅助化工计算试卷-参考答案_其它考试_资格考试/认证_教育专区。合肥学院2008级-计算机辅助化工计算试卷-参考答案...
2008级计算机科学概论试卷(答案)_韩语学习_外语学习_教育专区。2008级计算机科学概论试卷(答案),考试作弊将带来严重后果! 华南理工大学期末考试 2008级《计算机科学...
2008 级高等电磁场理论期末考试参考答案 1、答: (1)麦克斯韦方程组的四种形式:...积分形式也可以用于各种情况,但是计算复杂,适用于推导固定的和移动的边界条件,...
2008初级维修电工理论试卷.答案_从业资格考试_资格考试/认证_教育专区。初级维修... 2014一级建造师考试 一级建造师《建设工程项目管理》 《建设工程经济》计算题...
热门文档