发布时间 : 星期三 文章CHAP4new更新完毕开始阅读13576ec69ec3d5bbfd0a7456
4.2 考虑DFA和正则表达式是否等价的问题。将这个问题表示为一个语言并证明它可判定。
解：设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) 检测
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={
证明：构造DFA N，使L(N)={含奇数个1的字符串}。构造图灵机
F=“对于输入
1) 构造DFA D，使L(D)=L(M)∩L(N)。 2) 检测L(D)是否为空。(EDFA可判定检测)。 3) 若L(D)＝?，则接受；否则拒绝。”
4.12设A ={
解：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 ={
证明：构造自动机B，使得L(B)={所有以“111”为子串的字符串}。 S=“在输入
1) 将G转化为与之等价的自动机A。 2) 构造C，使得L(C)= L(A)? L(B)。 3) 检测C是否为空(EDFA可判定)。
4) 若C为空，则拒绝；若C不为空，则接受。”
4.16 检查两个DFA在长度小于或对于某个数的所有串上运行，并以此方法证明EQDFA是可判定的。计算一个这样的数。 证明：对于长度k，构造TM
Mk=“输入
1) 列出所有长度小于或等于k的串；
2) 在这些串上分别运行A，B；
3) 若A，B同时接受或拒绝，则M接受；若A，B不同时接受或拒绝，则
M拒绝。”
因为所有长度?k的串是有限的，Mk一定是可以进入停机状态，所以Mk是一个
判定器。而且Mk判定
{
构造TM M：
M=“输入
1) 计算A和B的状态数p,q。 2) 在
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的接受状态集。和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接受 此即M判定EQDFA。 4.17 设C是一个语言。证明C是图灵可识别的，当且仅当存在一个可判定语言D，使得C={ x | ?y ( (1) 首先证明必要性，即“若C是图灵可识别的，则存在一个可判定语言D，使得C={ x | ?y ( N=“对于输入 2) 若M接受，则接受；若M不接受，则拒绝。” （注：这里实际D={ (2) 下面证明充分性，即“若D是可判定语言，则存在图灵可识别语言C，满足C={x | ?y ( M=“输入串x， 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}。 3) 检测L(P1)是否为空。若L(P1)=?，则拒绝。 4) 若没有一个为空，则接受。” 4.28设A是由某些图灵机的描述构成的一个图灵可识别语言{ 证：设E是A的枚举器。考虑判定器F： F＝“对输入串x， 1) 初始化，令y＝?。 2) 运行E，每当E输出一个串(判定器)时，计算y按字典序的下一个串， 仍将此串记为y。若y?x,继续运行E。 3) 若y与x相同，则记E此时输出的判定器为