发布时间 : 星期一 文章2、正则语言练习更新完毕开始阅读98da486825c52cc58bd6beac
第4章、丘奇-图灵论题习题解答 - 练习
4.1、此练习和TM M2有关，例4.4给出了它的描述和状态图，它判定语言A?{02|n?0}。在下列每个输入串上，给出M2所进入的格局序列：
a. 0 b. 00 c.
000
nd. 000000 答： a.
q10
、 q2 、 q20
、 qaccept 、 x q3
、 q5x
、q5 x
、 q2 x
b. q100
x q2
c.
q1000
、 x qaccept 、 q200
、 x q30 、 x0q4 、 x0qreject 、 x0q4000 、 x0xq50x 、 q2x0x0x
、 x0xq300 、 x0q5x0x 、 xq20x0x
d. q1000000
x0x0q40
xq50x0x xxq3x0x
、 q200000
x0x0xq3
、 xq30000 、 x0x0q5x 、q5 x0x0x
、 q5x0x0x
xxxq30x
、 xxx0q4x 、 xxx0xq4
xxx0x qreject
25
4.2、此练习和TM M1有关，例4.5给出了它的描述和状态图，它判定语言B={w#w|w?{0,1}*}。在下列每个输入串上，给出M1所进入的格局序列：
a. 11 b. 1#1 c.
1##1
d. 10#11 e.
10#10
答： a.
q111
、 q31 b. q11#1
、 q3#1
q7 #1 、 q9#1 #q14x 、 #xq14 c.
q11##1 、 q3##1
d. q110#11 、 q30#11
0#1q71 、 0#q711 0q9#11、 0#q1111 xq8#x1、 x#q10x1
e.
q110#10 、 q30#10 0#1q70 、 0#q710
1q3 、 1qreject #q51 、 #1q5
、 # q71
、 q7#1
#q111 、 q12# x 、q12 # x 、q13 # x
#x qaccept #q5#1 、 #qreject #1
0q3#11 、 0#q511 、 0#1q51
、 0#11q5
0q7#11 、 q70#11 、q7 0#11 、 q90#11 0q12#x1
、 q120#x1
、q12 0#x1 、 q130#x1
x#xq101 、 x#xqreject1 0q3#10 、 0#q510 、 0#1q50
、 0#10q5
0q7#10
、 q70#10 、q7 0#10 、 q90#10
26
、、、、、、、、、、、0q9#10、 0#q1110 xq8#x0、 x#q10x0
、 0q12#x0 、 q120#x0 、q12 0#x0 、 q130#x0
、 q12x#xx 、 x#xxq14
、 x#xq100 、 x#q12xx 、 xq12#xx
、 x#q14xx 、 x#xq14x
q12 x#xx、 q13x#xx 、 xq13#xx x#xx qaccept
4.3 修改定理4.10以得到推论4.12的证明，即证明一个语言是可判定的当且仅当有非确定型TM判定它。（可以假设关于树的下列定理成立：如果一个树中的每个结点只有有限多个子结点，且此树的每一个分枝只有有限多个结点，则此树本身只有有限个结点）。 证明：
定理4.10为：每个非确定型图灵机都有一个与之等价的确定型图灵机。 修改定理4.10为：每个非确定性判定器都有与之等价的确定型判定器。
现在设N是一个非确定性判定器，N 对所有输入，所有分枝都停机。构造一个与之等价的确定型判定器D。D有三个带：一个输入带，一个模拟带，一个地址带。D按“宽度优先”策略搜索N的不确定计算分枝树。
M= “输入w，
1) 开始时，输入带包含输入w, 模拟带和地址带都是空的。 2) 把输入带的内容复制到模拟带上。
3) 在模拟带上模拟N在输入w上的非确定性计算树的某个分枝。
a) 在N的每一步动作之前，查询地址带上的下一个数字，以决定在N的转移函数所允许
的选择中作何选择。
b) 如果地址带上下一个数字是空白，则放弃这个分枝，转到第四步。 c) 如果这个非确定性的选择是无效的，则放弃这个分枝，转到第四步。 d) 如果遇到拒绝格局，则放弃这个分枝，转到第四步。 e) 如果遇到接受格局，则接受这个输入。
4) 按照字典顺序取下一个地址串。根据假设非确定性计算树只有有限的结点，所以地址串有
一个上界Amax。
a) 如果下一个地址串已经超过Amax，则说明已经搜索了所有分枝，那么拒绝这个输入。 b) 否则用下一个地址串来替代原有的串。转到第二步，以模拟N的计算的下一个分枝。” 如果有一个非确定性判定器判定语言，根据上述证明，必有与之等价的确定型判定器判定该语言，则该语言是可判定的。
如果一个语言是可判定的，则有一个确定性判定器判定该语言。确定性判定器自然是非确定型
27
判定器，所以必有非确定型判定器判定它。
4.4 给出枚举器的形式定义。可将其看作一种双带图灵机，用它的第二个带子作为打印机。包括它所枚举的语言的定义。
解：枚举器E=(Q，?，?，?，q0，qaccept，qreject), 其中转移函数?为：
?：Q×?→Q×?×{L,R}×?×{R} ? (q，a)=(r，b，s1，c，R)
表示若E处于状态q，且在工作带上读到a，则状态转移到r，当前格改写为b并按s1所指示的
方向移动读写头，打印带上写下c并向右移动读写头。
4．5 检查图灵机的形式定义，回答下列问题并解释你的推测： a． 图灵机能在它的带子上写下空白符吗？ b．带字母表?和输入字母表?能相同吗？
c．图灵机的读写头能在连续的两步中处于同一个位置吗？ d．图灵机能只包含一个状态吗？ 解： a.
能。因为空白符属于带字母表?； 另外E的起始格局只能是q0?。 L(E)={w|w是枚举器E打印出的串}
b. 不能。因为空白符不属于输入字母表?； c.
能。当读写头处于左端点时，如果转移是向左转移，因为不准机器从带的左端点移出，所以下一个格局读写头仍在左端点。
d. 不能。因为qaccept?qreject，至少应有两个状态。
4．6 定理4.13证明了一个语言是图灵可识别的当且仅当有枚举器枚举它。为什么不能用下列更简单的算法作为证明？像以前一样，s1，s2，。。。是∑*中所有的串。 E=“忽略输入，
1) 对于i=1，2，3，… 重复下列步骤。 2) 在si上运行M。
3) 如果它接受，则打印出si。”
答：因为M不一定是判定器，可能会在运行某个si时不停机，则L(M)中按字典序的序数大于si的
28