本科生4.docVIP

湖南大学课程考试试卷 课程名称： 计算理论引论 ；试卷编号： ；考试时间：120分钟 题 号 一 二 三 四 五 六 七 八 九 十 总分 应得分 100 实得分 评分： 评卷人 一 单选或填空题（10*3 = 30％） 1.下列叙述正确的是（ ） A.如果DFA不接受任何字符串，则该机器识别的语言为{}. B.如果DFA不接受任何字符串，则该机器识别的语言为. C.一个DFA可以没有起始状态. D.一个DFA的起始状态不能和接受状态相同. 2.下述（目前为止）肯定不正确的是（ ） A． B. C.团问题是NP完全的 D.团问题是NP难的 3.下图中,存在的最大团顶点数为____ A.2 B.3 C.4 D.5 4.识别语言{0n1n | n ≥ 0}的文法为__________ 5.下述表达不正确的是（ ） A.所有的RL均是CFL B.所有的RL均是图灵可判定的 C.所有的CFL均是图灵可判定的 D.若语言A是图灵可判定的,则A和不全是图灵可识别的 6.背包问题:max: p1x1+p2x2+…+pnxn St: w1x1+w2x2+…wnxn m (xi = 0或1) 用动态规划在O(nm)时间解决，背包问题属于____问题. A. P B. NP C.NP完全 7.若判断某语言A的多带图灵机所花费的时间为n+log n,则判定问题A的时间复杂度为（ ）A. O(n) B. O(log n) C.O(2n) D.O(n2) 8.若有A ≤ mB,则下述叙述正确的是（ ） A.若B可判定，则A也可判定 B.若B可判定，则A也不可判定 C.若B不可识别,则A也不可识别 D.A和B间的可判定性不存在任何关系 9.若图灵机的当前格局为uaqibv,其状态转移函数为,则下一格局为_______. 10.若一个关系是自反,对称和传递的,则该关系为_____关系. 二 DFA的形式描述为({q1,q2,q3,q4},{u,d}, , q3,{ q3}),其中在下表中给出.试画出这台机器的状态图. (13%) u d q1 q1 q2 q2 q1 q3 q3 q2 q4 q4 q3 q1 三 (10%) 将下述公式转换为乔氏范氏 S→AA | 0 A→SS | 1 四 给出产生语言A={aibick | i≥0, k≥0}的上下文无关文法，并判断其是否歧义.(10%) 五 证明：单变量的Hibert(希尔伯特)的第十问题是可判定的（不要求对上界的存在性作证明）.(10%) 六 判断下述公式的可满足性，并说明原因.(13%) (x∨y)∧(x∨)∧(∨y) 七 令CONNECTED={G|G是连通的无向图},证明：CONNECTED.(7%) 八 证明： 若存在一接受语言L的NTM M1, 则L也被一台DTM M2接受(7%) 湖南大学教务处考试中心 湖南大学课程考试试卷 装订线（答题不得超过此线） 专业班级： 学号： 姓名： 考试中心填写： ____年___月___日 考 试 用