计算理论模拟试题及答案汇编

1、学习-好资料计算理论复习题1、设语言A= w | w含有子串0101,即对某个x和y, w=x0101y,字母表为0 , 1a.画出识别A的DFA的状态图。b.更多精品文档2、把下图的有穷自动机转换成正则表达式。解：1、加新的开始状态和新的结束状态2、删除状态1,通过状态1的转换有s一 1 一 2、2一 1 一2*3、删除状态2a b（a ba b）3、设语言A=www | wC a,b ,利用泵引理证明 A不是正则语言。证明：假设 A是正则的。设p是泵引理给出的关于 A的泵长度。令 S=a ba ba b, S是A的一个成员且 S的长度大于p,所以泵引理保证 S可被分成3段S=xyz且 满足

2、泵引理的3个条件。根据条件3, y中只含a,所以xyyz中第一个a的个数将比 后两个a的个数多，故xyyz不是A2的成员。违反泵引理的条件 1,矛盾。A不是正则的。4、证明在3.1节开始部分给出的文法G2中，字符串the girl touches the boy with the flower 有两个不同的最左派生，叙述这句话的两个不同的意思。解：G2如下:（句子一名词短语动词短语名词短语一复合名词|复合名词介词短语动词短语一复合动词|复合动词介词短语介词短语一介词复合名词v复合名词一 v冠词 名词复合动词一动词|v动词名词短语冠词 一 a_|the_ 名词 一 boy_|girl_|flow

3、er_动词 一 touch_|1ikes_|Sees_介词 一 with_答：1 .第一种最左派生句子 =名词短语 动词短语=复合名词 动词短语 =冠t名词 动词短语= 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_介词 复合

4、名词 =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

5、_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=WcW R | W C

6、a,b* U c,请给出这台PDA的形式定义、状 态图，并非形式地描述它的运行。6、设语言A=0 n1 n 0n1 n | n皂0,利用泵引理证明 A不是上下文无关的。证明：假设 A是上下文无关的。设 p是泵引理给出的关于 A的泵长度。令字符串S=0P1p 0p1 p,S是A的一个成员且 S的长度大于p,所以泵引理保证 S可被分成5段S=uvxyz且满足泵 引理的3个条件。 字串vxy 一定横跨S的中点，否则，如果 vxy位于S的前一半，把S抽 成uv xy z时，1移到后一半的第一个位置，因此 uv xy z不可能是A的成员。如果vxy 位于S的后一半，把S抽成uv2xy2 z时，0移到后一

7、半的最后一个位置，因此 uv 2 xy 2 z不 可能是A的成员。如果字串 vxy横K夸S的中点，把S抽成u x y ,它形如001 i oji p,其中i 和j不可能等于p。于是，S不能被抽取，从而 A不是上下文无关的。7、设语言A=w | w至少含有3个1,字母表为0,1学习-好资料a.给出产生语言 A的上下文无关文法。b.给出产生语言A的下推自动机的非形式描述和状态图。解：a.S-A1A1A1AA f0A|1A| z读输入中的符号。每读一个1,把一个1推入栈，每读1个0,不读栈也不写栈。同时非确定性地转移，并把 1个1弹出栈。如果能转移三次，共弹出三个 1,则接 受这个输入，并继续读输入

8、符号直至结束。否则拒绝这个输入。0,二二0,二8、检查图灵机的形式定义，回答下列问题并解释你的推理：a.图灵机能在它的带子上写下空白字符吗？b.图灵机能只包含一个状态吗？解：a.能。因为空白符属于带字母表；B.不能。因为qaccepfqreject,至少应有两个状态。9、证明正则语言类在并运算下封闭。10、设 INFINITE dfa=<A>|A 是一个 DFA ,且 L(A)是一个无限语言。证明 INFINITE dfa 是 可判定的。证明：设计一个判定 INFINITE dfa的TM M 即可。M= "对于输入<A> ,其中A是一个 DFA:1)按照引理2

9、.32证明中的构造方法，把 DFA A转换成等价的正则表达式。2)扫描正则表达式，如果包含星号运算符*,则接受；否则拒绝。B是不可数的。11、设B是0, 1上所有无限序列的集合，用对角化方法证明证明：为证明B是不可数的，必须证明在 B和N之间不存在对应。下面用反证法证之。假 设在B和N之间存在对应f,现在的任务是证明它没有应有的性质。因为它是一个对应， 必须能将N的所有元素与 B的所有元素进行配对。如果能找到B中的一个x,它和N中的任何元素都不能配对，则找到了矛盾。为此，实际构造出这样一个 x。方法如下：在选择它的每一位数字时，都使得：x不同于某个无限序列，且此无限序列已与N中的一个元素配对。

10、这样就能保证 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是不可判定的。证明：设TM R判定EQcfg；如下构造判定的 ALL cfgTM S :S= "对于输入<G>,其中G是CFG;1)在输入<G, G 1>上运行R,其中G1是派生所有可能的串 CFG。2)如果R接受，则接受；如果 R拒绝，则拒绝。”如果R判定EQcfg,则S判定ALL cfg°但由定理6.10, ALL cfg是不可判定的。