浙江大学 计算机 考博试题 计算理论及答案

《浙江大学 计算机 考博试题 计算理论及答案》由会员分享，可在线阅读，更多相关《浙江大学 计算机 考博试题 计算理论及答案（13页珍藏版）》请在金锄头文库上搜索。

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)(

3、R1R2),这里 R1 和 R2 是正则表达式5）(R10R2),这里 R1 和 R2 是正则表达式6）(R1*),这里 R1*是正则表达式一个语言是正则的当且仅当可以用正则表达式描述。一个语言是正则的当且仅当可以用正则表达式描述。20002000 年年 4 4 月月1、根据图灵机理论、根据图灵机理论,说明现代计算机系统的理论基础。说明现代计算机系统的理论基础。 1936 年，图灵向伦敦权威的数学杂志投了一篇论文，题为论数字计算在决断难题 中的应用 。在这篇开创性的论文中，图灵给 “可计算性”下了一个严格的数学定义，并 提出著名的 “图灵机”(Turing Machine)的设想。 “图灵机”

4、不是一种具体的机器，而是一 种思想模型，可制造一种十分简单但运算能力极强的计算机装置，用来计算所有能想像 得到的可计算函数。 这个装置由下面几个部分组成：一个无限长的纸带，一个读写头。 （中间那个大盒子） ，内部状态（盒子上的方块，比如 A,B,E,H） ，另外，还有一个程序对 这个盒子进行控制。这个装置就是根据程序的命令以及它的内部状态进行磁带的读写、移动。工作带被划分为大小相同的方格，每一格上可书写一个给定字母表上的符号。控制 器可以在带上左右移动，它带有一个读写出一个你期待的结果。这一理论奠定了整个现 代计算机的理论基础。“图灵机”更在电脑史上与 “冯诺依曼机”齐名，被永远载入计算 机的

5、发展史中。图灵机在理论上能模拟现代数字计算机的一切运算,可视为现代数字计算机的数学模型。实际上,一切“可计算“函数都等价于图灵机可计算函数,而图灵机可计算函数类又等价于一般递归函数类。2、说明按乔姆斯基分类，语言、文法、自动机的关系、说明按乔姆斯基分类，语言、文法、自动机的关系乔姆斯基将语言定义为，按一定规律构成的句子或符号串 string 的有限的或无限的集 合，记为 L。数目有限的规则叫文法，记为 G。刻画某类语言的有效手段是文法和自动机。 文法与自动机的关系:形式文法是从生成的角度来描述语言的,而自动机是从识别的角度来描 述语言的.文法和自动机是形式语言理论的基本内容。对某种语言来说,如

6、果存在一个该语言 的生成过程,就一定存在一个对于它的识别过程.就描述语言来讲,形式语言形式语言和自动机是统一 的.文法在形式上定义为四元组：G（VN,VT,S,P）,VN 是非终极符号，VT 是终极符号， S 是 VN 中的初始符号，P 是重写规则。文法是定义语言的一个数学模型，而自动机可看作是语言的识别系统。 对于一个文法产生的语言，可以构造相应自动机接受该语言：一个自动机接受的语 言，可以构造对应的文法产生该语言。一定类型的自动机和某种类型的文法具有等 价性。 2、乔姆斯基根据转换规则将文法分作 4 类。每类文法的生成能力与相应的语言自动 机（识别语言的装置）的识别能力等价，即 4 类文法

7、分别与 4 种语言自动机对应：类型文法自动机0 型无限制文法图灵机1 型上下文有关文法线性有界自动机2 型上下文无关文法后进先出自动机3 型有限状态的正则文法有限自动机最常见文法的分类系统是 诺姆乔姆斯基 于 1956 年 发展的 乔姆斯基谱系 ，这个 分类谱系把所有的文法分成四类型： 无限制文法 、 上下文相关文法 、 上下文无关文法 和 正规文法 。四类文法对应的语言类分别是 递归可枚举语言 、 上下文相关语言 、 上 下文无关语言 和 正规语言 。这四种文法类型依次拥有越来越严的产生式规则，同时文法所能表达的言也越来越少。尽管表达能力比无限文法和上下文相关文法要弱，但由于高效 率的实现，

8、四类文法中最重要的上下文无关文法和正规文法。例如对下文无关语言存在算 法可以生成高效的 LL 分析器 和 LR 分析器 。3、证明、证明 HALT(XR,X)不是可计算的。不是可计算的。4、 （1） 、证明递归集都是递归可枚举集。、证明递归集都是递归可枚举集。 （2） 、举例属于递归可枚举集但不是递归集的集合，并证明之。、举例属于递归可枚举集但不是递归集的集合，并证明之。5、 （1） 、证明、证明 L(a,b)*|a,b 的个数相同的个数相同为上下文无关语言。为上下文无关语言。 （2） 、并证明其不是正则的。、并证明其不是正则的。P56假设 L 是正则的，则根据在交下的封闭性，La*b*也是封

9、闭的，而后者正好是 L1= aibi:i0,假设 L1 是正则的，则存在满足泵引理的整数 n。考虑字符串 w= anbnL。根据 定理可以写成 w=xyz 使得|xy|n，且 ye，即 y=ai ，其中 i0.但是 xz= an-ibnL，与定 理矛盾。20002000 年年 1010 月月1、 （1）给出图灵机的格局、计算及图灵机 计算函数 f 的精确定义。(2 ) 对图灵机模型而言，church 论题是什么？ （3）当 x 是完全平方时值为 3x，否则为 3x+1 证明其是原始递归函数。2、证明 （X，X）是不可计算的。3、证明、证明 L=ambn|m,n0,mn是上下文无关的，但不是正则

10、的。是上下文无关的，但不是正则的。 利用上下文无关语言在并、连接、利用上下文无关语言在并、连接、Kleene 星号下是封闭的。星号下是封闭的。 正则语言在交运算下封闭。正则语言在交运算下封闭。4、A 为有穷字母表，L 是 A*的无穷子集， （1）证明存在无穷序列 0,1,2，它由 L 的所有字组成，每个字恰好在其中只出现一 次。 （2）是否存在从 L 构造序列 0,1,2,的算法（即 i 由计算 i） ，为什么？20012001 年年 4 4 月月1、 （1）当 x 是完全平方时值为 2x，否则为 2x+1 证明其是原始递归函数。 （2）对图灵机模型而言，church 论题是什么？ （3）通用

11、图灵机的描述。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 时的程序。20012001 年年 1010 月月1、a，b上递归枚举语言是否可数？证明上递归枚举语言是否可数？证明2、L=a，b，c 数目相同的语言数目相同的语言是否是否 CFL（上下文无关）？证明（上下文无关）？证明p9

12、5证：不是上下文无关的。假设 L 是上下文无关的，则它与正则语言 a* b* c* 的交也是上下文无关的。令L1=anbncn:n0假设 L1 是上下文无关语言。取常数 p，ap bp cp ,3pp将 写成 uvxyz 使得 v 或 y 不是空串且uvixyizL1I=0,1,2其中xy1 且 xuyp.有两种可能他们都导致矛盾。如果 vy 中 a、b、c 三个符号都出现，则 v 和 y 中必有一个至少含有 abc 中的两个符号。于是 uv2xy2z 中 abc 的排列顺序不对，有的 b 在 a 前或 c 在 a 或 b 前。如果 vy 中只出现 a、b、c 中的一个或两个符号，则uv2xy

13、2z 中 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 整除 的非负整

14、数的十进制表示的集合 .一个数可以被 3 整除当且仅当它的数字之和可以 被 3 整除。构造一台有穷自动机，用它的有穷控制器保存输入数字的模3 和。L3 是这台有穷自动机接受的语言与L1 的交。最后 L=L2L3，它一定是个正则语言。4、NonSelfAccepting 是否递归集合是否递归集合20022002 年年 4 4 月月1 能被 5 整除的字符串是正则集吗 2 用图灵机表示下列字符串。，e，a,a* 3 s-ss, s-asb, s-abs, 证明由 s 推得的字符串不可能以 abb 开头。 （可能记忆有误，具体形式就是这样） 。 4 证明不是所有的递归可枚举集都是递归的。 定理：语言

15、不是递归的；所以，递归语言类是递归可枚举语言类的真子集。20022002 年年 1010 月月1、 什么是计算？计算理论研究的内容和意义是什么？为什么要使用计算的抽象模型？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()=拒绝如果 M 不接受 现在来构造一个新的图灵机 D，它以 H 作为子程序。当 M 被输入它自己的描述是，TM D 就调用 H，以了解 M 将做什么。一 旦得到这个信息，D 就反着做，