计算理论复习课2习题答案.docx
《计算理论复习课2习题答案.docx》由会员分享，可在线阅读，更多相关《计算理论复习课2习题答案.docx（15页珍藏版）》请在冰点文库上搜索。
计算理论复习课2习题答案
第三章上下文无关语言与下推自动机
a.
{w|w至少含有3个1}
S→A1A1A1A
A→0A|1A|
b.{w|w以相同的符号开始和结束}
S→0A0|1A1
A→0A|1A|
c.
{w|w的长度为奇数}
S→0A|1A
A→0B|1B|
B→0A|1A
d.{w|w的长度为奇数且正中间的符号为0}
S→0S0|1S1|0S1|1S0|0
e.
{w|w中1比0多}
S→A1A
A→0A1|1A0|1A|AA|
f.{w|w=wR}
S→0S0|1S1|1|0
g.空集
S→S
3.6给出产生下述语言的上下文无关文法：
a．字母表{a,b}上a的个数是b的个数的两倍的所有字符串组成的集合。
S→bSaSaS|aSbSaS|aSaSbS|
b．语言{anbn|n0}的补集。
见问题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|k1,每一个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
S0AS0A
ABAB|B|ABAB|AB|BA|B|
B00|B00
去掉A,去掉AB
S0AS0A
ABAB|AB|BA|B|BBABAB|AB|BA|00|BB
B00B00
去掉S0A,添加新变元
S0BAB|AB|BA|00|BBS0VB|AB|BA|UU|BB
ABAB|AB|BA|00|BBAVB|AB|BA|UU|BB
B00BUU
VBA
U0
3.15证明上下文无关语言类在并,连接和星号三种正则运算下封闭---答案。
a.AB
方法一：
CFG。
设有CFGG1＝（Q1,,R1,S1）和G2=（Q2,,R2,S2）且L（G1）=A,L（G2）=B。
构造CFGG=（Q,,R,S0），其中
Q=Q1Q2{S0},S0是起始变元，R=R1R2{S0S1|S2}.
方法二：
PDA。
设P1=（Q1,,1,1,q1,F1）识别A，P2=（Q1,,2,2,q2,F2）是识别B。
则如下构造的P=（Q,,,,q0,F）识别AB，其中
1）Q=Q1Q2{q0}是状态集，
2）＝12，是栈字母表，
3）q0是起始状态，
4）F＝F1F2是接受状态集，
5）是转移函数，满足对任意qQ,a,b
（q,a,b）=
b.连接AB
方法一：
CFG。
设有CFGG1＝（Q1,,R1,S1）和G2=（Q2,,R2,S2）且L（G1）=A,L（G2）=B。
构造CFGG=（Q,,R,S0），其中
Q=Q1Q2{S0},S0是起始变元，R=R1R2{S0S1S2}.
方法二：
PDA。
设P1=（Q1,,1,1,q1,F1）识别A，P2=（Q1,,2,2,q2,F2）是识别B，而且P1满足在接受之前排空栈（即若进入接受状态，则栈中为空）这个要求。
则如下构造的P=（Q,,,,q1,F）识别AB，其中
1）Q=Q1Q2是状态集，
2）＝12，是栈字母表，
3）q1是起始状态，
4）F＝F1F2是接受状态集，
5）是转移函数，满足对任意qQ,a,b
（q,a,b）=
c.A*
方法一：
CFG。
设有CFGG1＝（Q1,,R1,S1），L（G1）=A。
构造CFGG=（Q,,R,S0），其中Q=Q1{S0},S0是起始变元，R=R1{S0S0S0|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）是转移函数，满足对任意qQ,a,b
（q,a,b）=
第四章图灵机
证明：
要证这四种运算下图灵可识别语言类封闭，只需设计出图灵机来识别此种语言。
设A和B是图灵可识别语言，A=L（M1），B=L（M2），M1和M2是两个图灵机。
a．M=“对于输入w：
1）在输入w上并行运行M1和M2；
2）M1和M2中有一个停机且接受，则接受；若都停机且拒绝，则拒绝。
”
M识别A1A2。
所以图灵可识别语言类对并运算是封闭的。
b.M＝“输入w，
1）出所有将w分成两段的方式（|w|+1种）.
2）对于i=1,2,重复以下步骤：
3）对于每一种分段方式，在第一段上运行M1i步，在第二段上运行M2i步，或者直到停机。
若都接受，则接受。
”
M识别A1
A2。
所以图灵可识别语言类对连接运算是封闭的。
c．M＝“输入w，
1）列出w的所有分段的方式（2|w|-1种）.
2）对于i=1,2,重复以下步骤：
3）对于每一种分段方式，分别在每一段上运行M1i步，或者直到停机。
若M1接受所有段，则接受。
”
M识别A*。
所以图灵可识别语言类对星号运算是封闭的。
d．M=“对于输入w：
1）在输入w上运行M1。
若M1接受，则转
（2）；若M1拒绝，则拒绝。
2）在w上运行M2。
若M2接受，则接受；若M2拒绝，则拒绝。
”
M识别AB。
所以图灵可识别语言类对并运算封闭。
第五章可判定性
停机问题是不可判定的（第二版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位上不同
见课本
证明：
构造DFAN，使L（N）={含奇数个1的字符串}。
构造图灵机
F=“对于输入，其中M是DFA，
1）构造DFAD，使L（D）=L（M）∩L（N）。
2）检测L（D）是否为空。
（EDFA可判定检测）。
3）若L（D）＝，则接受；否则拒绝。
”
证明：
构造如下TM：
D=“输入,
1）构造DFAM1使得L（M1）=L（M）R。
2）检测M1与M是否等价。
3）若等价，则接受；否则拒绝。
”
D判定S。
第六章归约性
升级会员 