浙江大学研究生计算理论11年真题及答案概要1.docVIP

这是我们（32舍388）参考老师的课堂内容整理的11年的答案，附带解析。由于时间仓促，错误必定不少，请各位见谅并吐槽指正。 G版 F 不一定。因为假设A是{Σ*}，B是{M在“M”上不停机}，符合题目要求，B不是可判定的。 T 如果A可以归约到B，根据归约的定义，x∈A的时候t(x)∈B，反之，x?A，即x∈A的补的时候t(x)?B，即t(x)∈B的补。 F 因为DFA总有停机的时候，对于一个DFA输入“M”，这个DFA总会读完所有的字符然后给出yes或者no，因此这个语言是递归的。老师课堂上说DDFA是非正则的，这是可以用对角化定理证明DDFA和每个正则语言都不一样，证明和课本165页中间的相似。 T 这个非递归可枚举的语言就是课本164下面那个H1的补，{M在“M”上不停机} T He可以用通用图灵机半判定，但是无法判定。停机问题，即图灵机M在某个输入w上是否停机，无法判定，这里让w=e即可。 F 根据定理5.4.1，因为H不是递归的，所以L也不递归了。因为H≤L补，所以H补≤L。如果L是递归可枚举的，那么H补也是递归可枚举，那么H就不是递归可枚举的了，这和H本身是递归可枚举的事实是相悖的，因此L不是递归可枚举的。 T 假设M1半判定A，M2半判定B，M3半判定A∪B的补。对于输入w，交给M1、M2和M3一起做。如果M1接受，那么w∈A，M2接受，那么w∈B，如果M3接受，那么w?(A∪B)，即不是A也不是B。因为A和B是不相交的，因此M1、M2和M3的合体可以判定A或者B，因此A和B都是可判定的，递归的。 T 后面的是NTIME，应该是不确定性计算的所需时间。所以，我们把nk看作一体的，称为a，那么确定计算时间是指数ca，非确定计算只要a，也就是nk了。 T B是P，A可以多项式时间归约到B，所以A也是P，P对补封闭，所以命题正确。 F 假设A是这样一个问题，给定一个整数集合和整数k，求是否存在k个元素和大于C。直观看我们可以用随机抽取k个元素然后算和然后如果其中一次大于C就接受。但是我们也可以通过，例如多项式时间的冒泡排序，把集合的整数降序排序，归约到问题B，前k个元素的和是否大于C，显然B是P的。所以，只能说如果B是NP的，A可以归约到B，那么A也是NP的。 T 这个表述有点纠结，我们尚且给个T。因为NPC是可计算的，有算法可解的，是递归的，当然也是递归可枚举的。 F 我们直观点看，NPC是所有NP问题都可以多项式归约到的问题，如果命题是正确的，那么NP=NPC了，所有NP问题都可以归约到任意一个NP问题上。如果这样，数学家不用花那么多精力寻找更多的NPC问题了。所以这么看命题是错误的。其实这个题目应该是个陷进，把L和SAT的位置换一下就对了。 解析：是正则的。因为这相当于要求xy中a的个数是偶数就可以了，所以可以构造DFA来接受。 解析：非正则。可以用泵定理证明。 解析：其实这是正则的，只有首尾字母不同并且长度是偶数就可以了。 G=（V，Σ，R，S） V={a，b，S，S1，S2} Σ={a，b} R= 下推自动机M=（K，Σ，Γ，Δ，s，F） K={p，q} Σ={a，b} Γ={a，b，S，S1，S2} Δ={ ((q,a,a),(q,e)) ((q,b,b),(q,e)) } S={p} F={q} 好像还是第一次考乔姆斯基范式。 生成乔姆斯基范式有三个阶段，把右面是大于2的分解掉，把右面是e的消掉变成右面是1个的，最后把右面是1个的消掉…… 实在是太烦了，还要求闭包，这显然是给机器做的通用做法。大家不如用人脑只能直接凑一下吧，反正不是每年常考的题目…… 这是双带图灵机，字符右上角标记表示在第几条带操作，诸如ab这样的表示第一条带带头下是a，第二条的是b。 思路是，首先把c前面的内容复制到第二条带。然后第一条带带头到最左边，两条带同时移位检查c前面的内容是否对称。 如果对称了，那么检查后面。图上的小修改是因为n是0也可以，因此要先判断c后面是不是a，如果是空格那么也是可以的。 如果输入字串的c后面是a，那么把所有a复制到第二条带上，然后第一条带上读到b的时候开始检查a和b的数量是否相同。 解析：composite numbers 就是合数。 Φ（x,y）= (1~prime(x))(1~prime(y))exp(x+1,y) 其中prime(x)就是判断x是否是质数，exp就是求指数，~是非负减法。 Rem是求余的函数，equals是判断是否相等的函数，都是原始递归的，所以prime原始递归的 其中multi是乘法函数，所以exp也是原始递归的。 原始递归函数的合成也是原始递归的，所以原函数是原始递归的。 设这个语言是L，L是递归可枚举但非递归的，我们可以用通用图灵机M半判定L。 为了找到M1和M2都可以停机