麻省理工学院试卷习题 2004期末考试_Automata, Computability, and Complexity（自动化、可计算性与复杂性）.pdf_大学文库

6.045J/18.400J: Automata, Computability and Complexity Prof. Nancy Lynch 期末考试 (5.18 2004) 请在每一页的上面写上自己的名字. 问题 1：多项选择题（每题 4 分，共 40 分）：下面每一个选项都可能是正确的。 1、下面哪些已经知道是正确的： (A) 如果一个语言 A，能够被一个 NFA 识别，那么 A 的补也能被一个 NFA 识别。 (B) 所有的图灵机可判定的语言的补也是图灵机可判定的 (C) NP=co-NP (D) NL=co-NL 2、下面哪些说法是正确的： (A) 任意能够被一个 n 个状态的 DFA 识别的语言都能被一个 n 个状态的 NFA 识别。 (B) 任意能够被一个 n 个状态的 NFA 识别的语言都能被一个 n 个状态的 DFA 识别。 (C) 任意能够被长度为 n 的正则表达式表示的语言都能被一个 O(n)个状态的 NFA 识别。 (D) 两个语言 A 和 B 分别能够被两个 n 状态的 DFA 识别，那么语言 A∪B 能被一个状态最多为 2n+1 的 DFA 识别。 3、下面哪些语言是图灵机可识别的： (A) {|M 是一个(确定型)图灵机，并且 M 接受 010}。 (B) {|M 是一个非确定型图灵机，并且 M 接受 010}。 (C) {|M 是一个(确定型)图灵机，并且 M 不接受 010}。 (D) {|M 是一个(确定型)图灵机，并且 L(M)=∑*}。 4、下面哪些语言能够直接运用 Rice 定理来证明其是不可判定的。 (A){|M 是 DFA，并且 M 接受 010}。 (B){|M 是一个图灵机，并且 M 接受 010}。 (C){|M 是一个图灵机，并且 M 接受 010 但不接受 101}。 (D){|M 是一个最小的图灵机，就是说不存在和 M 识别相同的语言而且比 M 还小的图灵机}。 5、下列哪些相对PCP是可以判定的？(也就是说哪些是使用一个为PCP谕示的谕示图灵机所判定的)。 (A)和 PCP 有关的谕示图灵机的语言接受问题。就是判定一个语言是不是能被一个谕示图灵机接受。 (B) ATM。 (C) 判断 L(M)是不是包含 010 而不包含 101。 (D) 普通图灵机的空语言问题。(即判断 L(M)是不是等于空集) 6、下面哪些是正确的： (A)CLIQUE≤PVERTEX-COVER。 (B) CLIQUE≤P3SAT。 (C) TQBF≤PHAMCYCLE。 (D) PATH≤P{6045} 7、下面哪些已知是属于 NP 的： (A)L1-L2，条件是 L1 和 L2 都是在 NP 中。 (B) L1∩L2，条件是 L1 和 L2 都是在 NP 中。 (C) ATM的补。 (D) PATH 问题的补

8、下列关于对数空间规约性的说法那些是己知正雨的： (A所有的对亚密的转段器的时何间复秋度挥是多项式的. (B)是可传递的。 (C)如果AB并且B后NL,那么A后NL (D)对于任意语言A和B,如米AB,果么A三，B。 9、下列关于萨维岗定理1 Savitch's theorem)及其证明的说法罪些是正痛的： (A)产雏奇定理培示了NSPACE(log n)-SPACE(loy n. (B)胪华奇定理暗示了NSPAC回n)是SPACE(n的子集 (C)在证明萨举☆定理定理的过程中，当核拟的灵机递归的计算CANYIELD时，它不商定的达抒中点配置。 (D)当核拟的图灵机递归的计算CANYIELD时，它使用的空间近似的停于那两个调用 CANYIELD的空向和的上界，丙如上存储中点配置的空问. 10、考虑语言【，以及一个顺率多项式时何图灵机M,使得M总是1.中的词汇，并且对于罪些不在L中的问汇W,M拒绝w的概率至少是/1O,下面厚些说法是正确的： (ALE BPP. (B)LERP. (C)LEc0-RP. (D)LENP 问题21正则语言(20分)解答下面各题，并且给出简单的论证： 1、按出两个在a,;上的正则语言L1和12，使得L1不是12的子集，L2也不是L1的子集，并山1IUL2=L1◆U12。 2、找出一个正则语言L1和一个非正则语言L2,使得L1门L2是丰正则语言而L1UL2是正则语言. 问题3：不可判定性(20分)设1.一{<M是一个基木的图灵机，并且其接受I1但不接受 00;。使用运归定理来证明L是不可判定的。填写下面的空来完成迁明。 F明：为了得出不所，我们假设D是一个判定器图灵机判定L,料是说D接受c,如奥M 液收字符11但是不接受00的话，而如果<M不接受11或者接受00的话，则拒绝M 然后我们定义一个新的图灵机R知下， R:在输入w:作知下的平1：通过运归定理包含它的自说明<R 在输上运行D 如果谈计算接受那么：知果罪么接受w 知果那么把花w 另一个方南。如果计算拒绝的话，影么有：知果那么接受w 如米那么拒范w 如果及那么D 而这个结论可以推出： ,很明暴这是不可能的：另一方而，假如R ，邦么这个可以推出下列轴论 ·这也是不可能的。这样武们或有了个才后，因此L是木可判定的。问题4：跳棋游戏(20分)考遮下而烧则的洗棋游戏-Solitaire。有一个m*:的糕盘，这样又mk个义义点，在每一个义叉点上可以为空。也可以被一个红标子或者蓝棋子给占据了。初

8、下列关于对数空间规约性的说法那些是已知正确的： (A)所有的对数空间的转换器的时间复杂度都是多项式的。 (B)≤L是可传递的。 (C)如果A≤LB并且B∈NL，那么A∈NL。 (D) 对于任意语言A和B，如果A≤PB，那么A≤LB。 9、下列关于萨维奇定理(Savitch’s theorem)及其证明的说法哪些是正确的： (A)萨维奇定理暗示了 NSPACE(log n)=SPACE(log n)。 (B)萨维奇定理暗示了NSPACE(n2 )是SPACE(n4 )的子集。 (C)在证明萨维奇定理定理的过程中，当模拟的图灵机递归的计算 CANYIELD 时，它不确定的选择中点配置。 (D) 当模拟的图灵机递归的计算 CANYIELD 时，它使用的空间近似的等于那两个调用 CANYIELD 的空间和的上界，再加上存储中点配置的空间。 10、考虑语言 L，以及一个概率多项式时间图灵机 M，使得 M 总是 L 中的词汇，并且对于那些不在 L 中的词汇 w，M 拒绝 w 的概率至少是 1/10。下面哪些说法是正确的： (A)L∈BPP。 (B) L∈RP。 (C) L∈c0-RP。 (D) L∈NP 问题 2：正则语言（20 分）解答下面各题，并且给出简单的论证： 1、找出两个在{a,b}上的正则语言 L1 和 L2，使得 L1 不是 L2 的子集，L2 也不是 L1 的子集，并且(L1∪L2)*=L1*∪L2*。 2、找出一个正则语言 L1 和一个非正则语言 L2，使得 L1∩L2 是非正则语言而 L1∪L2 是正则语言。问题 3：不可判定性（20 分）设 L={|M 是一个基本的图灵机，并且其接受 11 但不接受 00}。使用递归定理来证明 L 是不可判定的。填写下面的空来完成证明。证明：为了得出矛盾，我们假设 D 是一个判定器图灵机判定 L，就是说 D 接受，如果接收字符 11 但是不接受 00 的话，而如果不接受 11 或者接受 00 的话，则拒绝。然后我们定义一个新的图灵机 R 如下： R：在输入 w 上作如下的事情：通过递归定理包含它的自说明在输入____________________上运行 D 如果该计算接受那么：如果________________，那么接受 w 如果________________，那么拒绝 w 另一个方面，如果计算拒绝的话，那么有：如果________________，那么接受 w 如果________________，那么拒绝 w 如果 R____________________________，那么 D____________________________，而这个结论可以推出：__________________________________,很明显这是不可能的；另一方面，假如 R____________________________，那么_____________________________，这个可以推出下列结论__________________________________，这也是不可能的。这样我们就有了一个矛盾，因此 L 是不可判定的。问题 4：跳棋游戏（20 分）考虑下面规则的跳棋游戏-Solitaire。有一个 m*k 的棋盘，这样又 mk 个交叉点，在每一个交叉点上可以为空，也可以被一个红棋子或者蓝棋子给占据了。初

麻省理工学院 试卷习题 2004期末考试_Automata, Computability, and Complexity（自动化、可计算性与复杂性）

麻省理工学院试卷习题 2004期末考试_Automata, Computability, and Complexity（自动化、可计算性与复杂性）