计算理论复习课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。

第六章 归约性

本文来源：https://www.bwwdw.com/article/qj6a.html