湖南大学计算理论引论期末试题2007.doc

诚信应考,考试作弊将带来严重后果！ 湖南大学课程考试试卷 课程名称：计算理论引论；课程编码：08233试卷编号： A ；考试时间：120分钟 题 号 一 二 三 四 五 六 七 八 九 十 总分 应得分 １０ １０ ｝(0S1|ε，则文法的语言L(G)为（ ）。 (A) ｛01｝不全是图灵可识别的 8.若有A ≤ pB,则下述叙述正确的是（ ） A.若B可判定，则A也可判定 B.若B可判定，则A也不可判定 C.若B不可识别,则A也不可识别 D.A和B间的可判定性不存在任何关系 9.若图灵机的当前格局为uaqibv,其状态转移函数为,则下一格局为_______. 10. 有理数集合是_______集，无理数集是_______集（填可数或不可数） 二、判断题（每题2分，共10分，如正确请在括号内打勾√，错误请打叉×） 1．每台NFA都有一个等价的DFA。 ( )２．图灵机只有进入接受状态才能停机。 （ ） ３．如果某串ω在上下文无关文法G中有两棵不同的分析树，则文法G是歧义的。 （ ） ４．设上下文无关文法G:S(ａS|ε，则ａａ∈L(G)。 （ ） ５．如果一个语言能被某一图灵机判定，则该语言一定是图灵可识别的。（ ） 三、解答或证明题（共70分） 1、20分(1) 利用教材上证明定理时所用的方法，构建字符串a(b(a)*b对应的非确定型自动N（7分）。 (2) 将该自动机转换为确定型有穷自动机D（注意：只给出D的可达状态）（7分）。 (3) 给出确定型自动机D判断字符串aaaabbb时的状态变迁过程(6分)。 2、以下文法是歧义的，并据此给出“Yan miss the girl in the office”各种可能的语法分析树，并给出每棵语法分析的相应的最左推导（1分）。 S(NP VP NP(NP PP| Det NP|N VP(V NP PP| V NP PP( Prep NP N( Yan| girl| office V(miss Prep(in Det (the 3 证明：若A ≤ m B，且B可判定，则A也可判定. (10分) 4 判断下述公式的可满足性，并说明原因.(%) (x∨y)∧(x∨)∧(∨y) ∧(∨z) 5写出下述图灵机的形式定义即7元组的表示形式，并给出字符串aabbccaa的计算过程，即给出格局序列。(分)。 说明：下图中B是为空白符，这是由于教材上的空白符打印不出来 6背包问题:max: p1x1+p2x2+…+pnxn St: w1x1+w2x2+…wnxn m (xi = 0或1) 试证明该问题是NP问题 （4分） 该问题还可用动态规划在O(nm)的时间内使用单带图灵机解决，该问题是P问题吗？为什么？（4分）  第 1 页 （共 页） 考试中心填写： ____年___月___日 考 试 用 专业班级： 学号： 姓名： 装订线（题目不得超过此线） 湖南大学课程考试试卷 湖南大学教务处考试中心 1 2 a(B,R a,y(R 3 b(y,R b,z(R qreject c,z(R 4 c(z,L z,b,y,a(L 5 x,B(R a(x,R b(R y,z(R qaccept B(R 装订线（题目不得超过此线） 湖南大学课程考试试卷 湖南大学教务处考试中心