计算理论习题答案CHAP4new.docVIP

4.2 考虑DFA和正则表达式是否等价的问题。将这个问题表示为一个语言并证明它可判定。 解：设EQD-R={A,B|A是DFA,B是正则表达式，L(A)=L(B)}。构造如下TM， F=“对于输入A,B , A是DFA，B是正则表达式， 将正则表达式B转化为等价的DFA C。 检测A与C是否等价(EQDFA可判定)。 若等价，则接受；否则拒绝。” F判定EQD-R。 4.3 设ALLDFA={A | A是一个识别(*的DFA}。证明ALLDFA可判定。 证明： 方法一：设计一个使用标记算法的TM M, M=“对于输入A,其中A是一个DFA: 去掉除起始状态以外的所有无用状态。标记起始状态。 重复下列步骤，直到没有新的状态可被标记。 对于每一个未标记状态，如果有一个到达它的转移是从某个已被标记过的状态出发的，则将其标记。 如果所有的标记状态都是接受状态，则接受；否则拒绝” 方法二：构造DFA B，使得L(B)= (*。 M＝“对于输入A,其中A是一个DFA: 检测A,B是否等价(EQDFA可判定)。 若等价，则接受；若不等价，则拒绝。” 4.4 A(CFG={G | G是一个派生(的CFG}。证明A(CFG可判定。 证明：M=“输入G，G是一个CFG， 构造与G等价的Chomsky文法P。 若P的规则集中有S0(((其中S0为起始变元)，则接受；否则拒绝。” M判定A(CFG。 4.9 设INFTDFA={A|A是一个DFA，且LA)是一个无限语言}。证明INFTDFA是可判定的。要证一个DFA识别一个无限语言，只需证此DFA的状态图中有回路。???? M=对于输入A，其中A是一个DFA：若起始状态被去掉，则拒绝。 重复，直到没有新的状态被标记，如果没有到它的转移，则将其标记并去掉所有从出发的转若所有状态都被标记，则拒绝；否则接受。M|M是DFA，它不接受任何包含奇数个1的字符串}。证明A是可判定的。 证明：构造DFA N，使L(N)={含奇数个1的字符串}。构造图灵机 F=“对于输入M，其中M是DFA， 构造DFA D，使L(D)=L(M)∩L(N)。 检测L(D)是否为空。(EDFA可判定检测)。 若L(D)＝(，则接受；否则拒绝。” 4.12设A ={R，S｜R和S是正则表达式，且L(R)(L(S) }，证明A是可判定的。 解：T=“输入R，S，R和S是正则表达式, 构造DFA C，使。 用定理5.4检查L(C)是否为空。 若L(C)为空，则接受；否则拒绝。” T判定A。 4.13 “检查一个CFG是否派生1*中某个串问题” 解： LX={G|G是{0，1}*上的CFG，且1*∩L(G)≠(} 证明：构造TM T T＝“对于输入A，A为CFG 将终结符“1”和“(”做标记。 重复下列步骤，直至无可做标记的变元。 如G有规则A(U1U2…Un，且U1U2…Un中每个符号都已做过标记，则将A做标记，其中Ui为终结符或非终结符。 如果起始变元没有被标记则拒绝，否则接受。” T判定LX。 4.15 设A ={R｜R是正则表达式，其所描述的串中至少有一个串以111为子串}。证明A是可判定的。 证明：构造自动机B，使得L(B)={所有以“111”为子串的字符串}。 S=“在输入G上，其中G是一个正则表达式, 将G转化为与之等价的自动机A。 构造C，使得L(C)= L(A)( L(B)。 检测C是否为空(EDFA可判定)。 若C为空，则拒绝；若C不为空，则接受。” 4.16 检查两个DFA在长度小于或对于某个数的所有串上运行，并以此方法证明EQDFA是可判定的。计算一个这样的数。 证明：对于长度k，构造TM Mk=“输入A，B，A，B是DFA 1) 列出所有长度小于或等于k的串； 在这些串上分别运行A，B； 若A，B同时接受或拒绝，则M接受；若A，B不同时接受或拒绝，则M拒绝。” 因为所有长度(k的串是有限的，Mk一定是可以进入停机状态，所以Mk是一个判定器。而且Mk判定 {A,B | A,B是DFA,Ck={x((*| |x|(k},且L(A)(C=L(B) (C}。 构造TM M： M=“输入A，B，A，B是DFA 计算A和B的状态数p,q。 在A，B上运行Mpq。 若Mpq接受，则接受；否则拒绝。” 下面证明M判定EQDFA。 首先注意到A的任意状态与B的任意状态组成的不同状态对有p×q个。 对于(*上的任意串w=w1w2w3…wL，设在A上运行得到状态序列P1P2P3…PL 和在B上运行得到状态序列Q1Q2Q3…QL。若Lpq, 则在L个状态对(Pi, Qi),i=1,2,…,L, 中必有相同的。不妨设Pi＝Pj, Qi＝Qj, 且ij. 令u=w1w2…wiwj+1wj+2…wL。则有w(L(A)(u(L(A