1、计算理论复习课2习题答案第三章 上下文无关语言与下推自动机a. w | w至少含有3个1SA1A1A1AA0A|1A|b. w | w以相同的符号开始和结束S0A0|1A1A0A|1A|c. w | w的长度为奇数S0A|1AA0B|1B|B0A|1Ad. w | w的长度为奇数且正中间的符号为0S0S0|1S1|0S1|1S0|0e. w | w中1比0多SA1AA0A1|1A0|1A|AA|f. w | w=wRS0S0|1S1|1|0g. 空集SS3.6 给出产生下述语言的上下文无关文法：a 字母表a,b上a的个数是b的个数的两倍的所有字符串组成的集合。 SbSaSaS|aSbSaS|a
2、SaSbS|b语言anbn|n0的补集。见问题3.25中的CFG:SaSb|bY|TaTaT|bT|cw#x | w, x0,1*且wR是x的子串。SUVU0U0|1U1|WWW1|W0|#V0V|1V|dx1#x2#xk|k1, 每一个xia,b* , 且存在i和j使得xixjR。SUVWUA|AaA|bA|#A|#VaVa|bVb|#B|#BaB|bB|#B|#WB|3.14解：添加新起始变元S0, 去掉BS0A S0AABAB|B| ABAB|AB|BA|B|B00| B00去掉A, 去掉ABS0A S0AABAB|AB|BA|B|BB ABAB|AB|BA|00|BBB00 B00去掉
3、S0A, 添加新变元S0BAB|AB|BA|00|BB S0VB|AB|BA|UU|BBABAB|AB|BA|00|BB AVB|AB|BA|UU|BBB00 BUU VBA U03.15 证明上下文无关语言类在并,连接和星号三种正则运算下封闭-答案。a. AB方法一：CFG。设有CFG G1(Q1,R1,S1)和G2=(Q2,R2,S2)且L(G1)=A, L(G2)=B。构造CFG G=(Q,R,S0)，其中Q= Q1Q2S0, S0是起始变元，R= R1R2S0 S1|S2.方法二：PDA。设P1=(Q1,1,1,q1,F1)识别A，P2=(Q1,2,2,q2,F2)是识别B。则如下构造
4、的P=(Q,q0,F)识别AB，其中1) Q=Q1Q2q0是状态集，2) 12，是栈字母表，3) q0是起始状态，4) FF1F2是接受状态集，5) 是转移函数，满足对任意qQ, a,b(q,a,b)= b. 连接AB方法一：CFG。设有CFG G1(Q1,R1,S1)和G2=(Q2,R2,S2)且L(G1)=A, L(G2)=B。构造CFG G=(Q,R,S0)，其中Q= Q1Q2S0, S0是起始变元，R= R1R2S0 S1S2.方法二：PDA。设P1=(Q1,1,1,q1,F1)识别A，P2=(Q1,2,2,q2,F2)是识别B，而且P1满足在接受之前排空栈(即若进入接受状态，则栈中为
5、空)这个要求。则如下构造的P=(Q,q1,F)识别AB，其中1) Q=Q1Q2是状态集，2) 12，是栈字母表，3) q1是起始状态，4) FF1F2是接受状态集，5) 是转移函数，满足对任意qQ, a,b(q,a,b)= c. A*方法一：CFG。设有CFG G1(Q1,R1,S1)，L(G1)=A。构造CFG G=(Q,R,S0)，其中Q= Q1 S0, S0是起始变元，R= R1S0S0S0|S1|.方法二：PDA。设P1=(Q1,1,1,q1,F1)识别A，而且P1满足在接受之前排空栈(即若进入接受状态，则栈中为空)这个要求。则如下构造的P=(Q,q1,F)识别A*，其中1) Q=Q1
6、q0是状态集，2) 1，是栈字母表，3) q0是起始状态，4) FF1q0是接受状态集，5) 是转移函数，满足对任意qQ, a,b(q,a,b)= 第四章 图灵机证明：要证这四种运算下图灵可识别语言类封闭，只需设计出图灵机来识别此种语言。设A和B是图灵可识别语言，A=L(M1)，B=L(M2)，M1和M2是两个图灵机。aM=“对于输入w：1) 在输入w上并行运行M1和M2；2) M1和M2中有一个停机且接受，则接受；若都停机且拒绝，则拒绝。”M识别A1A2。所以图灵可识别语言类对并运算是封闭的。b. M“输入w，1) 出所有将w分成两段的方式(|w|+1种).2) 对于i=1,2,重复以下步骤
7、：3) 对于每一种分段方式，在第一段上运行M1i步，在第二段上运行M2 i步，或者直到停机。若都接受，则接受。”M识别A1A2。所以图灵可识别语言类对连接运算是封闭的。cM“输入w，1) 列出w的所有分段的方式(2|w|-1种).2) 对于i=1,2,重复以下步骤：3) 对于每一种分段方式，分别在每一段上运行M1 i步，或者直到停机。若M1接受所有段，则接受。”M识别A*。所以图灵可识别语言类对星号运算是封闭的。dM= “对于输入w：1) 在输入w上运行M1。若M1接受，则转(2)；若M1拒绝，则拒绝。2) 在w上运行M2。若M2接受，则接受；若M2拒绝，则拒绝。”M识别AB。所以图灵可识别语
8、言类对并运算封闭。第五章 可判定性停机问题是不可判定的（第二版P111、第一版P115）：证明：为证明B是不可数的，必须证明在B和N之间不存在对应。下面用反证法证之。假设在B和N之间存在对应f，现在的任务是证明它没有应有的性质。因为它是一个对应，必须能将N的所有元素与B的所有元素进行配对。如果能找到B中的一个x，它和N中的任何元素都不能配对，则找到了矛盾。为此，实际构造出这样一个x。方法如下：在选择它的每一位数字时，都使得：x不同于某个无限序列，且此无限序列已与N中的一个元素配对。这样就能保证x不同于任何已配对的无限序列。用一个例子来说明这个思路。假设对应f存在，且设f(1)=010101，f
9、(2)=101010，f(3)=等等。则f将1和010101配对，将2和101010配对，依此类推。要保证对每个n都有xf(n)。为保证xf(1)，只要保证x的第一位数字不同于f(1)=010101的第一位数字，即不是数字0，令它为1。为保证xf(2)，只要保证x的第二位数字不同于f(2)=101010的第一位数字，即不是数字0，令它为1。以这种方法继续下去，就能够得到x的所有数字。不难知道，对任意n，x都不是f(n)，因为x与f(n)在第n位上不同见课本证明：构造DFA N，使L(N)=含奇数个1的字符串。构造图灵机F=“对于输入，其中M是DFA，1) 构造DFA D，使L(D)=L(M)L(N)。2) 检测L(D)是否为空。(EDFA可判定检测)。3) 若L(D)，则接受；否则拒绝。”证明：构造如下TM： D=“输入,1) 构造DFA M1使得L(M1)= L(M)R。2) 检测M1与M是否等价。3) 若等价，则接受；否则拒绝。”D判定S。第六章 归约性
