计算理论模拟试题及答案

《计算理论》复习题1、设语言A=｛w|w含有子串0101，即对某个x和y，w=x0101y｝，字母表为{0，1}a.画出识别A的DFA的状态图。b.画出识别A的NFA的状态图（规定状态数为5）。解:a．b．2、把下图的有穷自动机转换成正则表达式。解:1、加新的开始状态和新的结束状态2、删除状态1，通过状态1的转换有s→1→2、2→1→23、删除状态23、设语言A={|w∈{a,b}*}，利用泵引理证明A不是正则语言。bab12a0,110011010010,1010,1asa*b(a∪ba*b)*a*b2a∪ba*bsabab12asa证明：假设A是正则的。设p是泵引理给出的关于A的泵长度。令S=apbapbapb,∵S是A的一个成员且S的长度大于p，所以泵引理保证S可被分成3段S=xyz且满足泵引理的3个条件。根据条件3，y中只含a，所以xyyz中第一个a的个数将比后两个a的个数多，故xyyz不是A2的成员。违反泵引理的条件1，矛盾。∴A不是正则的。4、证明在3.1节开始部分给出的文法G2中，字符串thegirltouchestheboywiththeflower有两个不同的最左派生，叙述这句话的两个不同的意思。解:G2如下：＜句子＞→＜名词短语＞＜动词短语＞＜名词短语＞→＜复合名词＞|＜复合名词＞＜介词短语＞＜动词短语＞→＜复合动词＞|＜复合动词＞＜介词短语＞＜介词短语＞→＜介词＞＜复合名词＞＜复合名词＞→＜冠词＞＜名词＞＜复合动词＞→＜动词＞|＜动词＞＜名词短语＞＜冠词＞→a_|the_＜名词＞→boy_|girl_|flower_＜动词＞→touch_|1ikes_|Sees_＜介词＞→with_答：1.第一种最左派生句子名词短语动词短语复合名词动词短语冠词名词动词短语a_名词动词短语a_girl_动词短语a_girl_复合动词a_girl_动词名词短语a_girl_touches_名词短语a_girl_touches_复合名词介词短语a_girl_touches_冠词名词介词短语a_girl_touches_the_名词介词名词a_girl_touches_the_boy_介词短语a_girl_touches_the_boy_介词复合名词a_girl_touches_the_boy_with_复合名词a_girl_touches_the_boy_with_冠词名词a_girl_touches_the_boy_with_the_名词a_girl_touches_the_boy_with_the_flower含义是：女孩碰这个带着花的男孩2.第二种最左派生句子名词短语动词短语复合名词动词短语冠词名词动词短语a_名词动词短语a_girl_动词短语a_girl_复合动词介词短语a_girl_动词名词短语介词短语a_girl_touches_名词短语介词短语a_girl_touches_冠词名词介词短语a_girl_touches_the_名词介词短语a_girl_touches_the_boy_介词短语a_girl_touches_the_boy_介词复合名词a_girl_touches_the_boy_with_复合名词a_girl_touches_the_boy_with_冠词名词a_girl_touches_the_boy_with_the_名词a_girl_touches_the_boy_with_the_flower含义是：女孩用花碰这个男孩5、有自动机M，接受语言L={WcWR|W∈{a,b}*∪c}，请给出这台PDA的形式定义、状态图，并非形式地描述它的运行。6、设语言A={0n1n0n1n|n≧0}，利用泵引理证明A不是上下文无关的。证明：假设A是上下文无关的。设p是泵引理给出的关于A的泵长度。令字符串S=0p1p0p1p,∵S是A的一个成员且S的长度大于p，所以泵引理保证S可被分成5段S=uvxyz且满足泵引理的3个条件。字串vxy一定横跨S的中点，否则，如果vxy位于S的前一半，把S抽成uv2xy2z时，1移到后一半的第一个位置，因此uv2xy2z不可能是A的成员。如果vxy位于S的后一半，把S抽成uv2xy2z时，0移到后一半的最后一个位置，因此uv2xy2z不可能是A的成员。如果字串vxy横跨S的中点，把S抽成uxy，它形如0p1i0j1p，其中i和j不可能等于p。于是，S不能被抽取，从而A不是上下文无关的。7、设语言A={w|w至少含有3个1}，字母表为{0，1}a.给出产生语言A的上下文无关文法。b.给出产生语言A的下推自动机的非形式描述和状态图。解:a.S→A1A1A1AA→0A|1A|读输入中的符号。每读一个1，把一个1推入栈，每读1个0，不读栈也不写栈。同时非确定性地转移，并把1个1弹出栈。如果能转移三次，共弹出三个1，则接受这个输入，并继续读输入符号直至结束。否则拒绝这个输入。8、检查图灵机的形式定义，回答下列问题并解释你的推理：a.图灵机能在它的带子上写下空白字符吗？b.图灵机能只包含一个状态吗？解：a.能。因为空白符属于带字母表；B.不能。因为qacceptqreject，至少应有两个状态。9、证明正则语言类在并运算下封闭。10、设INFINITEDFA={A|A是一个DFA，且L(A)是一个无限语言}。证明INFINITEDFA是可判定的。证明：设计一个判定INFINITEDFA的TMM即可。M=“对于输入A，其中A是一个DFA：1)按照引理2.32证明中的构造方法，把DFAA转换成等价的正则表达式。2)扫描正则表达式，如果包含星号运算符*，则接受；否则拒绝。”。11、设B是{0，1}上所有无限序列的集合，用对角化方法证明B是不可数的。,11,10,,1,11,0,证明：为证明B是不可数的，必须证明在B和N之间不存在对应。下面用反证法证之。假设在B和N之间存在对应f，现在的任务是证明它没有应有的性质。因为它是一个对应，必须能将N的所有元素与B的所有元素进行配对。如果能找到B中的一个x，它和N中的任何元素都不能配对，则找到了矛盾。为此，实际构造出这样一个x。方法如下：在选择它的每一位数字时，都使得：x不同于某个无限序列，且此无限序列已与N中的一个元素配对。这样就能保证x不同于任何已配对的无限序列。用一个例子来说明这个思路。假设对应f存在，且设f(1)=010101…，f(2)=101010…，f(3)=…等等。则f将1和010101…配对，将2和101010…配对，依此类推。要保证对每个n都有x≠f(n)。为保证x≠f(1)，只要保证x的第一位数字不同于f(1)=010101…的第一位数字，即不是数字0，令它为1。为保证x≠f(2)，只要保证x的第二位数字不同于f(2)=101010…的第一位数字，即不是数字0，令它为1。以这种方法继续下去，就能够得到x的所有数字。不难知道，对任意n，x都不是f(n)，因为x与f(n)在第n位上不同。12、设EQCFG={G，H|G和H都是一个CFG，且L(A)=L(B)}，证明EQCFG是不可判定的。证明：设TMR判定EQCFG；如下构造判定的ALLCFGTMS：S＝“对于输入G，其中G是CFG；1）在输入G，G1上运行R，其中G1是派生所有可能的串CFG。2）如果R接受，则接受；如果R拒绝，则拒绝。”如果R判定EQCFG，则S判定ALLCFG。但由定理6.10，ALLCFG是不可判定的。故EQCFG也是不可判定的。13、证明：如果A是图灵可识别的，且A≤mA，则A是可判定的。证明：因为A≤mA=A≤mA且A为图灵可识别的，根据定理6.22，A图灵可识别的。根据5.16，由A和A都是图灵可识别的，所以A是可判定的。14、证明所有的图灵可识别问题都映射可归约到ATM。