计算理论模拟试题及答案

计算理论复习题1、语言A=w | w包含子字符串0101，即，x和y，w=x0101y，并且字母被设置为 0，1 a .描绘识别a的DFA的状态图。b .画出识别a的NFA的状态图(规定状态数为5 )。 0，110011010解除： a010，1010，1乙组联赛2 .将下图中的贫穷机器人转换为正则表达式。乙组联赛a.a乙组联赛12a.a解：1，加上新的开始状态和新的结束状态乙组联赛a.a乙组联赛12a.asa.a2、删除状态1，在状态1的转移中，变为s12、212a*b2aba*bsa.a3 .删除状态2a.asa*b(aba*b)*3、设定语言A=www | wa，b*，利用泵的引理证明a不是正规语言。证明：假设a是正规的。 设p为泵引导给出的关于a的泵长。当S=apbapbapb时，由于s是a的成员，s的长度大于p，因此泵引理可以将s分为三个段S=xyz，满足泵引理的三个条件。 根据条件3，由于y仅包括a，因此xyyz的前a的数量大于之后两个a的数量，因此xyyz不是a-2的成员。 泵引导的条件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=WcW R | Wa，b*c，显示该PDA的形式定义、状态图，没有形式记述其运行。6、设语言A=0n1 n 0n1 n | n0，通过泵引导证明a与上下文无关。证明：假设a与上下文无关。 设p为泵引导给出的关于a的泵长。如果字符串S=0p1 p 0p1 p由于s是a的成员，s的长度大于p，所以泵引理可以将s分成5个段S=uvxyz，满足泵引理的3个条件。 字符串vxy一定跨越s的中点。 否则，当vxy位于s的前半部分时，uv2- xy2z不是a的成员，因为当s被提取到uv2- xy2z时，1将移动到后半部分的第一位置。 如果vxy在s的后半部分中，那么uv 2 xy 2 z不可能是a的成员，因为如果将s提取到uv 2 xy 2 z中，那么0将移动到后半部分中的最后一个位置。 如果字符串vxy跨越s的中点，则提取s为uy。 这类似于0p1 i 0j1 p，I和j不等于p。 于是，由于不提取s，所以a不依赖于上下文。7、语言A=w | w至少包含3个1，将字母设为 0，1 a .给出生成语言a的语境依赖语法。b .给出生成语言a的下推机器人的非形式记述和状态图。解： a. SA1A1A1Aaa0a|1a|e读取输入中的符号。 每读1，就把1按入堆栈，每读0，堆栈也不写。 同时不确定转移，把一个从堆栈中排出。 跳过3次，共跳出3个1次后，接受该输入，继续读取输入符号直到最后。 否则，此输入将被拒绝。e，1e1，e10，eee，1ee，1e1，ee0，ee8、检查图灵机器的形式定义，回答以下问题，说明你的推论a图灵可以在那盘磁带上写空白字母吗？b .图灵功能是否只包括一种状态？解： a .能。 因为空白字母带有字母的gb .不行。 qacceptqreject至少需要两种状态。9 .证明正规语言类在并行计算中关闭。10、INFINITEDFA=|A为DFA，L(A )为无限语言。 证明INFINITEDFA是可判断的。证明：只要设计判定INFINITEDFA的TM M即可。M=“如果输入，则a为DFA :1 )引理2.32按照证书的构造方法将DFA变换为等价的正则表达式。2 )扫描正则表达式，如果包含星号运算符*，则接受；否则拒绝。 中所述情节，对概念设计中的量体体积进行分析。将11，b作为 0，1 以上的所有无限序列的集合，证明用对角化方法b是不可能的。证明：为了证明b是不可能的，必须证明b和n之间没有对应。 下面用反证法证明。 假设对应于b和n之间的f存在，现在的任务就是证明它不具有应有的性质。 因为这是一个贴图，所以n的所有元素必须与b的所有元素配对。 如果找到了b的x，和n的要素不成对的话就会发现矛盾。因此，实际构建这样的x。 方法在选择各个数字时，x不同于无限序列，这个无限序列已经与n的元素配对。 这确保了配对的无限序列和x不同。用一个例子说明这个想法。 假设f存在，则f(1)=、f(2)=、f(3)=等。 f是1和成对，2和成对，以下相同。保证每n有一个x f(n )。 为了保证x f(1)，x的第一位与f(1)=的第一位不同，即设为1而不是数字0。 为了保证x f(2)，x的第二位的数字与f(2)=的第一位的数字不同，即设为1而不是数字0。 用这种方法继续下去，就能得到x的全部数字。 因为x和f(n )在第n位不同，所以对于任何n，x显然不是f(n )。12、EQCFG=|G和h都是CFG，且L(A)=L(B)，证明EQCFG不能判定。证明： ALLCFGTM S通过以下结构确定，TM R要确定EQCFG :S=输入时，g为CFG；1 )在输入上执行r，G1导出所有可能的字符串CFG。2 )如果r接受，则接受；如果r拒绝，则拒绝。 他说当r确定EQCFG时，s确定ALLC