若N要将当前格由a改为b且右移，则照此动作；
若N要将当前格由a改为b且左移，则将当前格由a改为b#且复位： a) 以~标记当前位，右移一格；
b) 若当前位没有标记#，则复位，右移直到找到标记有~的字符，去掉此标记，右移一格转步(a); c) 若当前位有标记#，则去掉标记#并复位，右移或直到找到标记有~的字符，去掉此标记； 2) 若N进入接受状态，则接受；若进入拒绝状态，则拒绝；否则转第一步。” L(E)=L(N)。因此左复位的图灵机识别图灵可识别语言类。
3.13 以停留代替左移的图灵机识别什么语言类？
解：正则语言类。首先一个DFA可以被一个以停留代替左移的图灵机模拟。下面证明一个以停留代替左移的图灵机S=(Q,?,?,?,q1,qaccept,qreject)，可以被一个NFA M=(Q1,?,?1,q0,F)模拟。
M的构造如下：
令Q1= Q×???{qend}， F={qend}，q0=(q1,?), 1) 对任意q?Q-{qaccept,qreject}, a??,令
?1( (q,?) , a )={(q,a)};
2) 对任意q?Q-{qaccept,qreject}, a??,
若有转移?(q,a)=(r,b,R)，则令?1( (q,a), ? )={(r, ?)}; 若有转移?(q,a)=(r,b,S)，则令?1( (q,a), ? )={(r,b)}; 3) 对任意a???, b??，
令?1( (qaccept,a) , b )={(qaccept, ?)};
4) 对任意q?Q，令Sq=(Q,?,?,?,q,qaccept,qreject),
若??L(Sq)，则令?1( (q,?) , ? )={qend}。 其中第一类转移是用来读字符的。
第二类转移是用来模拟S的读写头的移动的。由于S没有左移，所以右移一格之前改写的内容b可以舍去。
第三类转移用来处理当S已进入接受状态，但是字符串还没有读完的情况的。即先由?1( (qaccept,a) , b )={ (qaccept,?) }读完所有剩余字符，再由第四类转移中的?1((qaccept,?),?)={qend}进入接受状态。
第四类转移用来处理S的读写头移出输入区域的情况的，在这种情况下，S是进入接受状态，还是进入拒绝状态，还是不停机，完全取决于进入空白区域时的状态q：即若??L(Sq)，则S最终会进入接受状态；若??L(Sq)，则S最终会进入拒绝状态或不停机。
3.15 证明可判定语言类在下列运算下封闭。
a. 并。
证明：设M1，M2为识别可判定语言A1,A2的判定器。构造图灵机M： M＝“输入w，
1) 分别在w上运行M1和M2，每运行一步M1就运行一步M2。 2) 若M1和M2中有一个接受，则接受。
若都拒绝，则拒绝。”
M为识别A1?A2的判定器。所以可判定语言类对并运算封闭。 b. 连接。
证明：设M1，M2为识别可判定语言A1,A2的判定器。构造图灵机M： M＝“输入w，
1) 列出所有将w分成两段的方式(|w|+1种).
2) 对于每一种分段方式，在第一段上运行M1，在第二段上运行M2。若都接受，则接受。 3) 若没有一种分段方式被接受则拒绝。”
- 26 -
M为识别A1?A2的判定器。所以可判定语言类对连接运算封闭。 c. 星号。
证明：设M1为识别可判定语言A的判定器。
M＝“输入w，
1) 列出w的所有分段的方式(2|w|-1种)。 2) 对于每一种分段方式，重复下列步骤：
3) 分别在每一段上运行M1，若每一段都能被M1接受，则接受。 4) 若没有一种分段方式被接受则拒绝。”
M为识别A*的判定器。所以可判定语言类对星号运算封闭。 d. 补。
证明：设M1=(Q,?,?,?,q0, q1, q2)为识别可判定语言A的判定器，其中q1为接受状态，q2为拒绝状态。令M=(Q,?,?,?,q0, q2, q1)，其中q2为接受状态，q1为拒绝状态。则M为识别A的判定器。所以可判定语言类对补运算是封闭的。 e. 交。
证明：设M1，M2为识别可判定语言A1,A2的判定器。构造图灵机M： M＝“输入w，
1) 分别在w上运行M1和M2，每运行一步M1就运行一步M2。 2) 若M1和M2中都接受，则接受。
若M1和M2中有一个拒绝，则拒绝。”
M为识别A1?A2的判定器。所以可判定语言类对交运算是封闭的。
3.16 证明图灵可识别语言类在下列运算下封闭： a．并 b．连接 c．星号 d．交
证明：要证这四种运算下图灵可识别语言类封闭，只需设计出图灵机来识别此种语言。设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：
4.2 考虑DFA和正则表达式是否等价的问题。将这个问题表示为一个语言并证明它可判定。 解：设EQD-R={|A是DFA,B是正则表达式，L(A)=L(B)}。构造如下TM，
- 27 -
F=“对于输入 , A是DFA，B是正则表达式，
1) 将正则表达式B转化为等价的DFA C。 2) 检测A与C是否等价(EQDFA可判定)。 3) 若等价，则接受；否则拒绝。” F判定EQD-R。
4.3 设ALLDFA={ | A是一个识别?*的DFA}。证明ALLDFA可判定。 证明：
方法一：设计一个使用标记算法的TM M,
M=“对于输入,其中A是一个DFA:
1) 去掉除起始状态以外的所有无用状态。标记起始状态。 2) 重复下列步骤，直到没有新的状态可被标记。 3) 对于每一个未标记状态，如果有一个到达它的转移是从某个已被标记过的状态出发的，
则将其标记。
4) 如果所有的标记状态都是接受状态，则接受；否则拒绝”
方法二：构造DFA B，使得L(B)= ?*。
M＝“对于输入,其中A是一个DFA:
1) 检测是否等价(EQDFA可判定)。 2) 若等价，则接受；若不等价，则拒绝。”
4.4 A?CFG={
1) 构造与G等价的Chomsky文法P。
2) 若P的规则集中有S0??(其中S0为起始变元)，则接受；否则拒绝。”
M判定A?CFG。
4.9 设INFTYDFA={|A是一个DFA，且L(A)是一个无限语言}。证明INFTYDFA是可判定的。 证明：要证一个DFA识别一个无限语言，只需证此DFA的状态图中有回路。 M=“对于输入，其中A是一个DFA：
1) 若无接受状态则拒绝。
2) 去掉A中所有无用状态(没有从它出发到达任何接受状态的路径)。
若起始状态被去掉，则拒绝。
3) 重复下一步，直到没有新的状态被标记。 4) 考察每一个未标记的状态，如果没有到它的转移(射入的箭头)，则将其标记并去掉所有从
它出发的转移(射出的箭头)。
5) 若所有状态都被标记，则拒绝；否则接受。”
4.11 设A={
F=“对于输入
1) 构造DFA D，使L(D)=L(M)∩L(N)。 2) 检测L(D)是否为空。(EDFA可判定检测)。 3) 若L(D)＝?，则接受；否则拒绝。”
4.12设A ={
- 28 -
解：T=“输入
1) 构造DFA C，使L(C)＝L(R)?L(S)。
2) 用定理5.4检查L(C)是否为空。 3) 若L(C)为空，则接受；否则拒绝。”
T判定A。
4.13 “检查一个CFG是否派生1*中某个串问题”
解： LX={
T＝“对于输入，A为CFG
1) 将终结符“1”和“?”做标记。
2) 重复下列步骤，直至无可做标记的变元。 3) 如G有规则A?U1U2…Un，且U1U2…Un中每个符号都已做过标记，则将A做标记，其中
Ui为终结符或非终结符。
4) 如果起始变元没有被标记则拒绝，否则接受。” T判定LX。
4.15 设A ={
1) 将G转化为与之等价的自动机A。 2) 构造C，使得L(C)= L(A)? L(B)。 3) 检测C是否为空(EDFA可判定)。
4) 若C为空，则拒绝；若C不为空，则接受。”
4.16 检查两个DFA在长度小于或对于某个数的所有串上运行，并以此方法证明EQDFA是可判定的。计算一个这样的数。
证明：对于长度k，构造TM
Mk=“输入，A，B是DFA
1) 列出所有长度小于或等于k的串；
2) 在这些串上分别运行A，B；
3) 若A，B同时接受或拒绝，则M接受；若A，B不同时接受或拒绝，则M拒绝。”
因为所有长度?k的串是有限的，Mk一定是可以进入停机状态，所以Mk是一个判定器。而且Mk判定
{ | A,B是DFA,Ck={x??*| |x|?k},且L(A)?C=L(B) ?C}。
构造TM M：
M=“输入，A，B是DFA
1) 计算A和B的状态数p,q。 2) 在上运行Mpq。
3) 若Mpq接受，则接受；否则拒绝。” 下面证明M判定EQDFA。
首先注意到A的任意状态与B的任意状态组成的不同状态对有p×q个。 对于?*上的任意串w=w1w2w3?wL，设在A上运行得到状态序列P1P2P3?PL 和在B上运行得到状态序列Q1Q2Q3?QL。若L>pq, 则在L个状态对(Pi, Qi),i=1,2,?,L, 中必有相同的。不妨设Pi＝Pj, Qi＝Qj, 且i 令u=w1w2?wiwj+1wj+2?wL。则有w?L(A)?u?L(A)，因为这都取决于PL是否属于A的接受状态集。 - 29 - 和w?L(B)?u?L(B)，因为这都取决于QL是否属于B的接受状态集。 若|u|>pq，则按此方法继续减小长度，最后会得到存在v (|v|?pq), w?L(A)?v?L(A)和w?L(B)?v?L(B)。 即L(A)=L(B)?[L(A)?Cpq]=[L(B) ?Cpq]。于是 M接受?[L(A)?Cpq]=[L(B) ?Cpq] ? L(A)=L(B)， 此即M判定EQDFA。 4.17 设C是一个语言。证明C是图灵可识别的，当且仅当存在一个可判定语言D，使得C={ x | ?y ( 证明：设M是识别语言C的图灵机，N是语言D的判定器，即C=L(M)，D=L(N)； (1) 首先证明必要性，即“若C是图灵可识别的，则存在一个可判定语言D，使得C={ x | ?y ( N=“对于输入 2) 若M接受，则接受；若M不接受，则拒绝。” （注：这里实际D={ (2) 下面证明充分性，即“若D是可判定语言，则存在图灵可识别语言C，满足C={x | ?y ( 1) 取一个y，在 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={ 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) 构造PDA P1=(Q,?,?,?,F1)，其中F1={q}。 - 30 -