一 单选或填空题（10*3 = 30） 1.下列叙述正确的是（ ）A.如果DFA不接受任何字符串，则该机器识别的语言为.B.如果DFA不接受任何字符串，则该机器识别的语言为.C.一个DFA可以没有起始状态.D.一个DFA的起始状态不能和接受状态相同.2.下述（目前为止）肯定不正确的是（ ）A B. C.SAT是NP完全的 D.SAT是NP难的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%) udq1q1q2q2q1q3q3q2q4q4q3q1三 (10%) 将下述公式转换为乔氏范氏 SAA | 0 ASS | 1四 给出产生语言A=aibick | i0, k0的上下文无关文法，并判断其是否歧义.(10%)五 证明：若A和均为图灵可识别的，则A为图灵可判定的.(10%)六 判断下述公式的可满足性，并说明原因.(13%) (xy)(x)(y)七 令CONNECTED=|G是连通的无向图,证明：CONNECTED.(7%)八 证明：上下文无关文法（或语言）在交运算下不封闭.(7%)