《浙江大学+计算机+考博试题+计算理论及答案.doc》由会员分享，可在线阅读，更多相关《浙江大学+计算机+考博试题+计算理论及答案.doc（13页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、【精品文档】如有侵权，请联系网站删除，仅供学习与交流浙江大学+计算机+考博试题+计算理论及答案.精品文档.计算理论 字母表：一个有穷的符号集合。字母表上的字符串是该字母表中的符号的有穷序列。一个字符串的长度是它作为序列的长度。连接 反转 Kleene星号 L* ，连接L中0个或多个字符串得到的所有字符串的集合。有穷自动机：描述能力和资源极其有限的计算机模型。有穷自动机是一个5元组M=(K,s,F),其中1）K是一个有穷的集合，称为状态集2）是一个有穷的集合，称为字母表3）是从KXK的函数，称为转移函数4）sK是初始状态5）FK是接收状态集M接收的语言是M接收的所有字符串的集合，记作L(M).对
2、于每一台非确定型有穷自动机，有一台等价的确定型有穷自动机有穷自动机接受的语言在并、连接、Kleene星号、补、交运算下是封闭的。每一台非确定型有穷自动机都等价于某一台确定型有穷自动机。一个语言是正则的当且仅当它被有穷自动机接受。正则表达式：称R是一个正则表达式，如果R是1）a，这里a是字母表中的一个元素。2），只包含一个字符串空串的语言3），不包含任何字符串的语言4)(R1R2),这里R1和R2是正则表达式5）(R10R2),这里R1和R2是正则表达式6）(R1*),这里R1*是正则表达式一个语言是正则的当且仅当可以用正则表达式描述。2000年4月1、根据图灵机理论,说明现代计算机系统的理论基
3、础。 1936年，图灵向伦敦权威的数学杂志投了一篇论文，题为论数字计算在决断难题中的应用。在这篇开创性的论文中，图灵给“可计算性”下了一个严格的数学定义，并提出著名的“图灵机”(Turing Machine)的设想。“图灵机”不是一种具体的机器，而是一种思想模型，可制造一种十分简单但运算能力极强的计算机装置，用来计算所有能想像得到的可计算函数。这个装置由下面几个部分组成：一个无限长的纸带，一个读写头。（中间那个大盒子），内部状态（盒子上的方块，比如A,B,E,H），另外，还有一个程序对这个盒子进行控制。这个装置就是根据程序的命令以及它的内部状态进行磁带的读写、移动。工作带被划分为大小相同的方格
4、，每一格上可书写一个给定字母表上的符号。控制器可以在带上左右移动，它带有一个读写出一个你期待的结果。这一理论奠定了整个现代计算机的理论基础。“图灵机”更在电脑史上与“冯诺依曼机”齐名，被永远载入计算机的发展史中。图灵机在理论上能模拟现代数字计算机的一切运算,可视为现代数字计算机的数学模型。实际上,一切可计算函数都等价于图灵机可计算函数,而图灵机可计算函数类又等价于一般递归函数类。2、说明按乔姆斯基分类，语言、文法、自动机的关系乔姆斯基将语言定义为，按一定规律构成的句子或符号串string的有限的或无限的集合，记为L。数目有限的规则叫文法，记为G。刻画某类语言的有效手段是文法和自动机。文法与自动
5、机的关系:形式文法是从生成的角度来描述语言的,而自动机是从识别的角度来描述语言的.文法和自动机是形式语言理论的基本内容。对某种语言来说,如果存在一个该语言的生成过程,就一定存在一个对于它的识别过程.就描述语言来讲,形式语言和自动机是统一的.文法在形式上定义为四元组：G（VN,VT,S,P）,VN是非终极符号，VT是终极符号，S是VN中的初始符号，P是重写规则。n 文法是定义语言的一个数学模型，而自动机可看作是语言的识别系统。n 对于一个文法产生的语言，可以构造相应自动机接受该语言：一个自动机接受的语言，可以构造对应的文法产生该语言。一定类型的自动机和某种类型的文法具有等价性。 2、乔姆斯基根据
6、转换规则将文法分作4类。每类文法的生成能力与相应的语言自动机（识别语言的装置）的识别能力等价，即4类文法分别与4种语言自动机对应：类型文法自动机0型无限制文法图灵机1型上下文有关文法线性有界自动机2型上下文无关文法后进先出自动机3型有限状态的正则文法有限自动机最常见文法的分类系统是 诺姆乔姆斯基 于 1956年 发展的 乔姆斯基谱系 ，这个分类谱系把所有的文法分成四类型： 无限制文法 、 上下文相关文法 、 上下文无关文法 和 正规文法 。四类文法对应的语言类分别是 递归可枚举语言 、 上下文相关语言 、 上下文无关语言 和 正规语言 。这四种文法类型依次拥有越来越严的产生式规则，同时文法所能
7、表达的言也越来越少。尽管表达能力比无限文法和上下文相关文法要弱，但由于高效率的实现，四类文法中最重要的上下文无关文法和正规文法。例如对下文无关语言存在算法可以生成高效的 LL 分析器 和 LR 分析器 。3、证明HALT(XR,X)不是可计算的。4、（1）、证明递归集都是递归可枚举集。 （2）、举例属于递归可枚举集但不是递归集的集合，并证明之。5、（1）、证明L(a,b)*|a,b的个数相同为上下文无关语言。 （2）、并证明其不是正则的。P56假设L是正则的，则根据在交下的封闭性，La*b*也是封闭的，而后者正好是L1= aibi:i0,假设L1是正则的，则存在满足泵引理的整数n。考虑字符串w
8、= anbnL。根据定理可以写成w=xyz使得|xy|n，且ye，即y=ai ，其中i0.但是xz= an-ibnL，与定理矛盾。2000年10月1、（1）给出图灵机的格局、计算及图灵机计算函数f的精确定义。(2 ) 对图灵机模型而言，church论题是什么？（3）当x是完全平方时值为3x，否则为3x+1证明其是原始递归函数。2、证明（X，X）是不可计算的。3、证明L=ambn|m,n0,mn是上下文无关的，但不是正则的。利用上下文无关语言在并、连接、Kleene星号下是封闭的。正则语言在交运算下封闭。4、A为有穷字母表，L是A*的无穷子集，（1）证明存在无穷序列0,1,2，它由L的所有字组成
9、，每个字恰好在其中只出现一次。（2）是否存在从L构造序列0,1,2,的算法（即i由计算i），为什么？2001年4月1、（1）当x是完全平方时值为2x，否则为2x+1证明其是原始递归函数。（2）对图灵机模型而言，church论题是什么？（3）通用图灵机的描述。2、（1）用有穷自动机构造正则语言，以a2b结尾的字符串组成的正则语言L（2）L=a3n bn|n0为上下文无关,但不是正则。3、A为字母表，L为A*上任意的语言。阐述其乔姆斯基层次及用可计算性表述它们的关系。4、证明不存在可计算函数h(x)，使(x,x)时h(x,x)= (x,x)+a,aN,(x,y)是编号为y输入为x时的程序。2001
10、年10月1、a，b上递归枚举语言是否可数？证明2、L=a，b，c数目相同的语言是否CFL（上下文无关）？证明p95证：不是上下文无关的。假设L是上下文无关的，则它与正则语言a* b* c* 的交也是上下文无关的。令L1=anbncn:n0假设L1是上下文无关语言。 取常数p，ap bp cp ,3pp 将写成uvxyz使得v或y不是空串且uvixyizL1 I=0,1,2其中xy1 且 xuyp.有两种可能他们都导致矛盾。如果vy中a、b、c三个符号都出现，则v和y中必有一个至少含有abc中的两个符号。于是uv2xy2z中abc的排列顺序不对，有的b在a前或c在a或b前。如果vy中只出现a、b
11、、c中的一个或两个符号，则uv2xy2z中a、b、c的个数不相等。 与L1是上下文无关语言假设矛盾。综上，L不是2型语言。3、被2，3整除的非负整数的十进制表示的集合是否正则。=1，2，9，L*，令L1是非负整数十进制表示的集合，容易看到L1=01，2，9*，由于L1是用正则表达式表示的，故它是一个正则语言。令L2是可以被2整除的非负整数的十进制表示的集合。L2正好是以0，2，4，6，8结尾的L1的成员组成的集合，即L2=L1*0，2，4，6，8，根据正则语言在交运算下封闭原则，故L2也是一个正则语言。令是可以被3整除的非负整数的十进制表示的集合.一个数可以被3整除当且仅当它的数字之和可以被3
12、整除。构造一台有穷自动机，用它的有穷控制器保存输入数字的模3和。L3是这台有穷自动机接受的语言与L1的交。最后L=L2L3，它一定是个正则语言。4、NonSelfAccepting是否递归集合2002年4月1 能被5整除的字符串是正则集吗2 用图灵机表示下列字符串。，e，a,a*3 s-ss, s-asb, s-abs, 证明由s推得的字符串不可能以abb开头。（可能记忆有误，具体形式就是这样）。 4 证明不是所有的递归可枚举集都是递归的。定理：语言不是递归的；所以，递归语言类是递归可枚举语言类的真子集。2002年10月1、 什么是计算？计算理论研究的内容和意义是什么？为什么要使用计算的抽象模
13、型？2、 请写出一个正则表达式，描述下面的语言：在字母表0,1上，不包含00子串且以1结尾。4、语言L=an:n是素数是不是正则语言，是不是上下文无关的？5、一个succ(n+1)的组合Turing机描述，说出它的作用。P1276、什么是Turing机的停机问题？它是可判定的么？为什么？ H=“M”“w”：Turing机M在输入w上停机，ATM |M是一个TM， 且M接受证明：假设ATM是可判定的，下面将由之导出矛盾。设H是ATM的判定器。 令M是一个TM， 是一个串。在输入上，如果M接受，则H就停机且接受；如果M不接受，则H也会停机，但拒绝。 换句话说，H是一个TM使得：接受如果M接受H()
14、=拒绝如果M不接受 现在来构造一个新的图灵机D，它以H作为子程序。当M被输入 它自己的描述是，TM D就调用H，以了解M将做什么。一旦 得到这个信息，D就反着做，即：如果M接受，它就拒绝；如果M 不接受，它就接受。下面是D的描述。D”对于输入，其中M是一个TM： 1) 在输入M,上运行H。 2) 输出H输出的相反结论，即，如果H接受，就拒绝； 如果H拒绝，就接受。”总而言之，接受如果M不接受D()=拒绝如果M接受当以D的描述作为输入来运行D自身时，结果会怎样呢？我们得到：接受如果D不接受D()=拒绝如果D接受不论D做什么，它都被迫相反地做，这显然是一个矛盾。所以，TM D和TM H都不存在。它
15、是不可判定的。假设H是递归的，那么H1=“M”：Turing机M在输入字符串“M”上停机也是递归的。H1表示对角化程序的halts（X，X）部分。假设存在判定H的Turing机M0，那么判定H1的TuringM1只需要把输入字符串检查一个图灵机是否接受一个给定的串问题。在证明之前，先来证明ATM是图灵可识别的。这样，定理5.9表面识别器确实比判定器更强大。要求TM在所以输入上都停机限制了它能够识别的语言种类。下面的图灵机U识别ATM.U=“对于输入,其中M是一个TM， 是一个串：1) 在输入上模拟M ；2) 如果M进入接受状态，则接受；如果M进入拒绝状态，则拒绝。”注意，如果M在上循环，则机器
16、U在输入上循环，这就是U不判定ATM的原因。假如M知道自己在上不停机，它能拒绝，但事实上，它不知道。所以ATM有时被称为停机问题。7、证明这个问题不可判定：一个Turing机半判定的语言等于这样的一个语言，这个语言是w和w的转置的连接。 定理：任何递归或递归可枚举语言，以及任何递归函数，分别可用随机存取Turing判定、半可判定和计算。1、判定下述语言是否正则：包含aaaaa子串的语言L。2、画出判定下述语言的图灵机：空集，e，a。3、用数学归纳法证明一个上下文无关语言不包含ab子串，语言的描述忘记啦。4、证明H是非递归的。2003年4月1、判断题目，好像有二十分左右，都是书上的概念，譬如：递
17、归语言是递归可枚举语言（错），一个语言如果是正则的，那么它一定是上下文无关语言（对），如果一个语言是图灵可识别的，那么、. （） 。后面的记不住了。2、证明题，第1个是要证某种语言是正则语言，第2个是证该语言是上下文无关语言，中间还有一个是要证明某种语言是非上下文无关语言（有可能是非正则语言）。最后一个是证明该语言是图灵可判语言。该题在上几届的考题中都曾变换个样式出现过。3、识图题，画了一个图，让写出该图所识别的语言是什么。我记得它是英文参考书上的一个例题，所识别的是：不全包含a,b,c中所有字符的字符串。该题6分。4、我没做，给出了一个式子，好像是y=a+b,让构造出计算该式的图灵机。这个题
18、目好像也是6分。2003年10月1、5个判断，比如例如： 1.也为正则语言。 2. 对于两个任意的正则表达式R1和R2，判断L(R1)=L(R2)为不可判定问题。 3、xy|x属于正则语言L，y属于其补是正则语言； 4、存在非递归的递归可枚举语言。2、（am）（bm）c（a2n）（b2n），m，nNm、n1，写出产生它的上下文无关文法和识别它的确定下推自动机。3、判断谓词是否递归;设P(x,y)为原始递归谓词，请证明 也是原始递归谓词。4、写出识别（0n）（1n）（2n） n0的图灵机，和anbncn类似，参考书的答案有问题！5）L = a 2n+1 | n =0 不是上下文无关语言，用泵引理
19、证明（其中，2为平方）n 在字母表T=a上，L = a 2n+1 | n =0 n 表示任意一对aa (包括0对) 后跟一个a的字符串。（即含有奇数个a的字符串。）6）L是一上下文无关文法，任给一正规文法R，LR可以判定吗，说明理由。2004年4月1、8个判断题2、证明（1）L1是正则语言，L2是非正则语言，若L1和L2的交为有限语言，则L1与L2的并为非正则语言。（2）L1是正则语言，L2是非正则语言，若L1和L2的交为无限语言，则L1与L2的并为正则语言。举例说明符合条件的L1和L23、有n个自然数 x1,x2,.,xn，问是否存在素数p使得x(p)p=x(1)+x(2)+.+x(p-1)
20、+x(p+1)+.+x(n)（式子类似这样的）给出算法的描述,复杂度,并证明属于P类4、给出图灵机的符号表示：该图灵机计算函数f(x) ;x为偶数 f(x)=x/2,x为奇数 f(x)=x+15、用泵定理证明语言L不是上下文无关的 L=w(a,b)*:w不同于WR2004年10月1、构造上下文无关文法来生成语言 L1=am bncp:m不等于n，且m、n、p 1L2=ambncp:n不等于p，且m、n、p 1,并证明a,b,c*-(L1L2)不是上下文无关的2、给出一个Turing包括转移关系等 根据给定的Turing的计算过程求出它所接受的语言L(M);并构造一个文法来生成L(M)3、一个有
21、关递归的判断题，并说出理由，有3句话。4、一个根据语言描述来判定两个语言之间关系的选择题。如1是2的真子集，2是1的真子集，1=2，1、2无任何关系。2005年4月1、判断题2、判定下列语言是否为正则语言，请具体说出理由L1=w1|wa,b* ,Na(w)-Nb(w) mod 3 0L2= w1|wa,b* ,Na(w)-Nb(w)0这里Na(w)、Nb(w)分别表示字符串w中a,b的个数3、给出上下文无关文法生成语言L3=xcy|2|x|=|y|,x,ya,b*证明L4=aibjcidj:i,jN, i,j 1不是上下文无关语言。4、证明语言L5=“M”|Turing在空串e上停机是非递归的
22、，其中M表示Turing M的编码。5、给定n个数，x1,x2,xn,判定是否存在不同的i1,i2ik,使满足下列两个条件： （1）Xi1+Xi2+Xik=(X1+X2+Xn)/2(2) Xi1+Xi2+Xik不是素数，给出一个算法，并估计其计算时间，说明这个问题属于NP类，是给算法描述即可。2006年4月1、设上下文无关语言L=a* （1）假设L为无限语言，且上下文无关文法G生成该语言，即L=L（G）。设K1为相对于文法G的泵定理常数，设r=k。证明下列结论：对于任意wL，如果|w|k，则wam |n0L（2）对于每个i（0ir）,设Li= an |anL，nk，n=I mod r，证明L=
23、 an |anL，nk Li （3）证明如果L a*为上下文无关语言，则L为正则语言2、设语言L1=uv，u、va，b*则，|v|u|2|v| （1）给出一个上下文无关的文法生成语言L1（2）给出一个下推自动机产生语言L13、分别给出满足条件的语言的例子，或说明其不存在(1)该语言是递归的，但是它的补语言非递归（2）该语言是递归可枚举的， 但是它的补语言是递归（3）该语言是递归可枚举的，它的补语言也是递归可枚举 不存在（4）该语言是递归可枚举的，它的补语言却非递归可枚举 若语言是递归的，则它是递归可枚举的。 如：L=anbncn:n0若L是递归语言则它的补也是递归的。若L是递归可枚举语言，则它
24、的补是非递归可枚举的。4、语言L称为前缀封闭（Prefix closed）定义如下：对于任意wL都有w的所有前缀均属于。利用停机问题的规约证明下列语言。“”（）为前缀封闭的、说明如下问题： |无向图i=(Vi,Ei)(i=1,2)同构是的。（只需要给出一个非形式化的描述）下面是ISO的验证机VV=“对输入2007年4月1、 判断题（简单） 如：字母表E上的语言是递归可枚举语言（） 2、 证明题 给定关系 uv 的定义 （1） 证明 uv 当且仅当vu （2） 证明具有这个关系的语言是正规的。 3、 给出一个语言，（ww*，其中w*和w的转置至少有一个字母不一样） （1） 证明该语言是CFL （
25、2） 给出PDA 4、 给出一个问题（） （1） 给出该问题的图灵算法 （2） 证明该问题是NPC（规约到顶点覆盖问题） 200年4月、和如果交正则，和是否均正则、设是上下文无关语言，为正则语言，属于是否可判定、存在能被图灵机计算的非原始递归函数、类问题aibjck| i+k j,写出该语言的上下文无关文法和下推自动机、判断下列语言是否是正则的（）语言（，），其中至少出现次（）语言（，），其中至多出现次、判断一些语言是否是递归语言，还是递归可枚举、一个图的问题多项式时间规约图灵机Turing Machine图灵机的模型掌握机器的构造方法：识别语言的装置，用上下文无关语言表示不了的语言，可以用图灵机来表示；用有限自动机和下推自动机表示的语言，可以改造成用图灵机表示递归&递归可枚举判定&半判定通用图灵机UTM文法及分类不可判定性，可判定，不可判定，停机问题，证明方法，关于TM的不可判定问题，关于文法的不可判定问题，Rice定理19、用归约说明L(M)=e不是递归的。20、21、找到一个数 Pn; 满足 PnXn（Xn的M次方，不会表达） P0X0P1X1 P（n1）X（n1）P（n1）X(n+1) + +PmXm;a） 计算时间复杂度；b） 证明这是个P问题。注：括号里表示下标。