发布时间 : 2024/6/26 23:07:47 星期三 文章计算理论习题答案CHAP4new更新完毕开始阅读b33b5628453610661ed9f425

D，使得C={ x | ?y (?D)}”。

N=“对于输入，x是一个串，k是自然数且k≥1， 1) 在x上模拟M运行k步或直到停机。 2) 若M接受，则接受；若M不接受，则拒绝。” （注：这里实际D={ | x在k步之内被M接受}）

(2) 下面证明充分性，即“若D是可判定语言，则存在图灵可识别语言C，满足C={x | ?y (?D)}”。

M=“输入串x，

1) 取一个y，在上运行D；

2) 若D接受，则接受；若D不接受，则找下一个y(按字典序)，重复第一步。”

综上，命题得证。

4.18 设A和B是两个不交的语言。称语言C分离A和B，如果A?C且B?C。证明任意两个不交的补图灵可识别语言都可以由某个可判定语言分离。 证明：设识别A的补的TM为T，识别B的补的TM为S。注意到L(T)?L(S)= ?*。

D=“输入w，

1) 在w上分别运行T和S，直到有一个首先进入接受状态。 2) 若T进入接受状态，则拒绝；若S进入接受状态，则接受。”

D是判定器，而且A?L(D)，B?L(D)。

4.19 设S={ | M是DFA，且只要接受w，就接受wR}。证明S可判定。 证明：构造如下TM：

D=“输入,

1) 构造DFA M1使得L(M1)= L(M)R。 2) 检测M1与M是否等价。

3) 若等价，则接受；否则拒绝。”

D判定S。

4.22下推自动机的一个无用的状态是在任何输入上它都不会进入的状态。考虑检查一个下推自动机是否有无用状态问题。将这个问题形式化为一个语言，并证明它是可判定的。

证明：S={

| P是PDA，且没有无用状态}。构造如下判定器D：

D=“输入

，P=(Q,?,?,?,F)是PDA，

1) 对于P中的每一个状态q，重复以下步骤。 2) 3)

构造PDA P1=(Q,?,?,?,F1)，其中F1={q}。 检测L(P1)是否为空。若L(P1)=?，则拒绝。

4) 若没有一个为空，则接受。”

4.28设A是由某些图灵机的描述构成的一个图灵可识别语言{,,?}，其中每个Mi都是判定器。求证：存在可判定语言D，它不能由任何一个其描述在A中出现的判定器来判定。

证：设E是A的枚举器。考虑判定器F：

F＝“对输入串x，

1) 初始化，令y＝?。

2) 运行E，每当E输出一个串(判定器)时，计算y按字典序的下一个

串，仍将此串记为y。若y?x,继续运行E。 3) 若y与x相同，则记E此时输出的判定器为。 4) 对串x运行Mi，若Mi接受则拒绝；若Mi拒绝则接受。” L(F)即为所求语言。