计算理论复习课2习题---答案

a. {w | w至少含有3个1} 0, 

S→A1A1A1A 1, 1 A→0A|1A|

,1 ,1

b. {w | w以相同的符号开始和结束}

S→0A0|1A1 0, A→0A|1A| 1, 0,0,0

1,1,1

c. {w | w的长度为奇数} 0,

1, 0,

1,

,1 d.

e.

f.

g.

S→0A|1A A→0B|1B| B→0A|1A

{w | w的长度为奇数且正中间的符号为0} S→0S0|1S1|0S1|1S0|0 0,0,0

1,1,0

,0,,$

{w | w中1比0多} 1,0S→A1A

0,1A→0A1|1A0|1A|AA|

0,

1,,1

,,1,$

{w | w=wR}

S→0S0|1S1|1|0 0,0,0

1,1,1

1,

,0,,$ , 空集 S→S

3.6 给出产生下述语言的上下文无关文法： a． 字母表{a,b}上a的个数是b的个数的两倍的所有字符串组成的集合。 S→bSaSaS|aSbSaS|aSaSbS|

b．语言{anbn|n0}的补集。见问题3.25中的CFG: S→aSb|bY|Ta T→aT|bT|

c．{w#x | w, x{0,1}*且wR是x的子串}。 S→UV

U→0U0|1U1|W W→W1|W0|# V→0V|1V|

d．{x1#x2##xk|k1, 每一个xi{a,b}* , 且存在i和j使得xi＝xjR}。 S→UVW U→A|

A→aA|bA|#A|# V→aVa|bVb|#B|# B→aB|bB|#B|# W→B|

3.14

解：添加新起始变元S0, 去掉B

S0A S0A ABAB|B| ABAB|AB|BA|B| B00| B00

去掉A, 去掉AB S0A S0A ABAB|AB|BA|B|BB ABAB|AB|BA|00|BB B00 B00

去掉S0A, 添加新变元 S0BAB|AB|BA|00|BB S0VB|AB|BA|UU|BB ABAB|AB|BA|00|BB AVB|AB|BA|UU|BB B00 BUU VBA U0

3.15 证明上下文无关语言类在并,连接和星号三种正则运算下封闭---答案。

a. AB

方法一：CFG。设有CFG G1＝(Q1,,R1,S1)和G2=(Q2,,R2,S2)且L(G1)=A, L(G2)=B。构造CFG G=(Q,,R,S0)，其中

Q= Q1Q2{S0}, S0是起始变元，R= R1R2{S0 S1|S2}.

方法二：PDA。

设P1=(Q1,,1,1,q1,F1)识别A，P2=(Q1,,2,2,q2,F2)是识别B。 则如下构造的P=(Q,,,,q0,F)识别AB，其中 1) Q=Q1Q2{q0}是状态集， 2) ＝12，是栈字母表， 3) q0是起始状态，

4) F＝F1F2是接受状态集，

5) 是转移函数，满足对任意qQ, a,b

{(q1,),(q2,)},若qq0,ab,(q,a,b),若qQ,b(),111(q,a,b)=

(q,a,b),若qQ,b(),222,else.b. 连接AB

方法一：CFG。设有CFG G1＝(Q1,,R1,S1)和G2=(Q2,,R2,S2)且L(G1)=A, L(G2)=B。

构造CFG G=(Q,,R,S0)，其中

Q= Q1Q2{S0}, S0是起始变元，R= R1R2{S0 S1S2}.

方法二：PDA。

设P1=(Q1,,1,1,q1,F1)识别A，P2=(Q1,,2,2,q2,F2)是识别B，而且P1满足在接受之前排空栈(即若进入接受状态，则栈中为空)这个要求。 则如下构造的P=(Q,,,,q1,F)识别AB，其中 1) Q=Q1Q2是状态集，

2) ＝12，是栈字母表， 3) q1是起始状态，

4) F＝F1F2是接受状态集，

5) 是转移函数，满足对任意qQ, a,b

1(q,a,b),若qQ1F1,b(1),(q,a,b){(q,)},若qF1,ab,12(q,a,b)=1(q,a,b),若qF1,(a,b)(,),

2(q,a,b),若qQ2,b(2),,else.

c. A*

方法一：CFG。设有CFG G1＝(Q1,,R1,S1)，L(G1)=A。构造CFG G=(Q,,R,S0)，其中Q= Q1 {S0}, S0是起始变元，R= R1{S0S0S0|S1|}.

方法二：PDA。

设P1=(Q1,,1,1,q1,F1)识别A，而且P1满足在接受之前排空栈(即若进入接受

状态，则栈中为空)这个要求。

则如下构造的P=(Q,,,,q1,F)识别A*，其中 1) Q=Q1{q0}是状态集， 2) ＝1，是栈字母表， 3) q0是起始状态，

4) F＝F1{q0}是接受状态集，

5) 是转移函数，满足对任意qQ, a,b

1(q,a,b),若qQ1F1,(q,a,b){(q,)},若qF1,ab,11(q,a,b)=1(q,a,b),若qF1,(a,b)(,),

(q1,)若qq0,ab,,else.

第四章 图灵机

证明：要证这四种运算下图灵可识别语言类封闭，只需设计出图灵机来识别此种语言。设A和B是图灵可识别语言，A=L(M1)，B=L(M2)，M1和M2是两个图灵机。 a．M=“对于输入w：

1) 在输入w上并行运行M1和M2；

2) M1和M2中有一个停机且接受，则接受；若都停机且拒绝，则拒绝。” M识别A1A2。所以图灵可识别语言类对并运算是封闭的。

b. M＝“输入w，

1) 出所有将w分成两段的方式(|w|+1种). 2) 对于i=1,2,重复以下步骤：

3) 对于每一种分段方式，在第一段上运行M1i步，在第二段上运行M2

i步，或者直到停机。若都接受，则接受。”

M识别A1A2。所以图灵可识别语言类对连接运算是封闭的。

c．M＝“输入w，

1) 列出w的所有分段的方式(2|w|-1种). 2) 对于i=1,2,重复以下步骤： 3) 对于每一种分段方式，分别在每一段上运行M1 i步，或者直到停机。

若M1接受所有段，则接受。”

M识别A*。所以图灵可识别语言类对星号运算是封闭的。

d．M= “对于输入w：

1) 在输入w上运行M1。若M1接受，则转(2)；若M1拒绝，则拒绝。 2) 在w上运行M2。若M2接受，则接受；若M2拒绝，则拒绝。” M识别AB。所以图灵可识别语言类对并运算封闭。

第五章 可判定性

停机问题是不可判定的（第二版P111、第一版P115）：

证明：为证明B是不可数的，必须证明在B和N之间不存在对应。下面用反证法证之。假设在B和N之间存在对应f，现在的任务是证明它没有应有的性质。因为它是一个对应，必须能将N的所有元素与B的所有元素进行配对。如果能找到B中的一个x，它和N中的任何元素都不能配对，则找到了矛盾。 为此，实际构造出这样一个x。方法如下：在选择它的每一位数字时，都使得：x不同

于某个无限序列，且此无限序列已与N中的一个元素配对。这样就能保证x不同于任何已配对的无限序列。

用一个例子来说明这个思路。假设对应f存在，且设f(1) = 010101„，f(2) = 101010„，

f(3) =„等等。则f将1和010101„配对，将2和101010„配对，依此类推。

要保证对每个n都有x ≠ f(n)。为保证x ≠ f(1)，只要保证x的第一位数字不同于f(1)

= 010101„的第一位数字，即不是数字0，令它为1。为保证x ≠ f(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。

第六章 归约性