《计算机考博试题》由会员分享，可在线阅读，更多相关《计算机考博试题（15页珍藏版）》请在金锄头文库上搜索。
1、计算理论字母表： 一个有穷的符号集合。字母表上的 字符串 是该字母表中的符号的有穷序列。 一个字符串的 长度 是它作为序列的长度。连接 反转 Kleene 星号 L* ，连接 L 中0个或多个字符串得 到的所有字符串的集合。有穷自动机： 描述能力和资源极其有限的计算机模型。有穷自动机是一个5元组M=(K,刀,s,F ),其中1) K 是一个有穷的集合，称为状态集2) 刀是一个有穷的集合，称为字母表3) 是从KXS K的函数，称为转移函数4) s K是初始状态5) F K是接收状态集M接收的语言是M接收的所有字符串的集合，记作 L(M). 对于每一台非确定型有穷自动机， 有一台等价的确定型有穷自
2、动机 有穷自动机接受的语言在并、连接、 Kleene 星号、补、交运算下 是封闭的。每一台非确定型有穷自动机都等价于某一台确定型有穷自动机。 一个语言是正则的当且仅当它被有穷自动机接受。正则表达式：称R是一个正则表达式，如果 R是1) a,这里a是字母表刀中的一个元素。2) ，只包含一个字符串空串的语言3) ，不包含任何字符串的语言4) (R1 u R2),这里R1和R2是正则表达式5) (R10R2),这里R1和R2是正则表达式* *6) (R1 ),这里R1是正则表达式一个语言是正则的当且仅当可以用正则表达式描述2000年4月1、根据图灵机理论，说明现代计算机系统的理论基础1936年，图灵
3、向伦敦权威的数学杂志投了一篇论文，题为论数字计算在决断难题中的应用。在这篇开创性的论文中，图灵给可计算性”下了一个严格的数学定义，并提出著名的图灵机”(TuringMachine)的设想。图灵机”不是一种具体的机器，而是一种思想模型，可制造一种十分简单但运算能力极强的计算机装置，用来计算所有能想 像得到的可计算函数。这个装置由下面几个部分组成：一个无限长的纸带，一个读写头。(中间那个大盒子)，内部状态(盒子上的方块，比如A,B,E,H)，另外，还有一个程序对这个盒子进行控制。这个装置就是根据程序的命令以及它的内部状态进行磁带的读写、移动。工作带被划分为大小相同的方格，每一格上可书写一个给定字母
4、表上的符号。控制器 可以在带上左右移动，它带有一个读写出一个你期待的结果。这一理论奠定了整个现代计算机的理论基础。图灵机”更在电脑史上与冯诺依曼机”齐名，被永远载入计算机的发展史中。图灵机在理论上能模拟现代数字计算机的一切 运算,可视为现代数字计算机的数学模型。实际上 一切可计算函数都等价于图灵机可计算函数，而图灵机可计算函数类又等价于一般递归函数类。2、说明按乔姆斯基分类，语言、文法、自动机的关系乔姆斯基将语言定义为，按一定规律构成的句子或符号串string的有限的或无限的集合，记为L。数目有限的规则叫文法，记为G。刻画某类语言的有效手段是文法和自动机。文法与自动机的关系：形式文法是从生成的
5、角度来描述语言的，而自动机是从识别的角度来描述语言的.文法和自动机是形式语言理论的基本内容。对某种语言来说，如果存在一个该语言的生成过程，就一定存在一个对于它的识别过程.就描述语言来讲，形式语言 和自动机是统一的.文法在形式上定义为四元组：G=（ VN,VT,S,P ） ,VN是非终极符号，VT是终极符号，S是VN中的初始符号，P是重写规则。自动机（接收机）图灵机线性有界自动机下推式存贮自动机有限自动机形式语言图1*1形式语害和自动机的关联归类图文法是定义语言的一个数学模型，而自动机可看作是语言的识别系统。对于一个文法产生的语言，可以构造相应自动机接受该语言：一个自动机接受的语 言，可以构造对
6、应的文法产生该语言。一定类型的自动机和某种类型的文法具有等 价性。2、乔姆斯基根据转换规则将文法分作4类。每类文法的生成能力与相应的语言自动机（识别语言的装置）的识别能力等价，即4类文法分别与4种语言自动机对应:类型文法自动机0型无限制文法图灵机1型上下文有关文法线性有界自动机2型上下文无关文法r后进先出自动机3型有限状态的正则文法有限自动机最常见文法的分类系统是诺姆乔姆斯基于1956年发展的乔姆斯基谱系，这个分类谱系把所有的文法分成四类型：无限制文法、上下文相关文法、上下文无关文法和正规文法。四类文法对应的语言类分别是递归可枚举语言、上下文相关语言、上下文无关语言和正规语言。这四种文法类型依
7、次拥有越来越严的产生式规则，同时文法所能 表达的言也越来越少。尽管表达能力比无限文法和上下文相关文法要弱，但由于高效率的实现，四类文法中最重要的上下文无关文法和正规文法。例如对下文无关语言存在算法可以生成高效的LL分析器和LR分析器3、证明HALT(X R,X)不是可计算的4、(1)、证明递归集都是递归可枚举集。(2) 、举例属于递归可枚举集但不是递归集的集合，并证明之。5、(1)、证明L = (a,b)*|a,b的个数相同为上下文无关语言。(2)、并证明其不是正则的。P56假设L是正则的，则根据在交下的封闭性，L n a*b*也是封闭的，而后者正好是L1= aibi:i 仝0,假设L1是正则
8、的，则存在满足泵引理的整数 n。考虑字符串w= a%n L。根据定理可 以写成w=xyz使得|xy| w n,且 沪e,即y=ai ,其中i 0.但是xz= an-ibn L,与定理矛盾。2000年10月1、(1) 给出图灵机的格局、计算及图灵机计算函数f的精确定义。(2 )对图灵机模型而言，church论题是什么？(3 )当x是完全平方时值为 3x，否则为3x+1证明其是原始递归函数。2a-+ 1if= Qelse2.设当时心 小层、的所右囚子王fll*O. 试汕叫1 er饵是碌始通归的*wiieie.设佝是小r等尸兀的索数的个数：试证明拓(力是原始递归的。if Xj O,m丰n是上下文无关
9、的，但不是正则的。 利用上下文无关语言在并、连接、Kleene星号下是封闭的。正则语言在交运算下封闭。4、A为有穷字母表，L是A*的无穷子集，(1 )证明存在无穷序列3 0, 3 1, 3 2；它由L的所有字组成，每个字恰好在其中只出现一次。(2) 是否存在从L构造序列3 0, 3 1, 3 2的算法(即i由计算3 i ,为什么？2001年4月1、( 1)当x是完全平方时值为 2x，否则为2x+1证明其是原始递归函数。(2) 对图灵机模型而言，church论题是什么？(3) 通用图灵机的描述。2、 (1)用有穷自动机构造正则语言，以a2b结尾的字符串组成的正则语言L(2) L=a3n bn |
10、n0为上下文无关，但不是正则。3、A为字母表，L为A*上任意的语言。阐述其乔姆斯基层次及用可计算性表述它们的关系。4、证明不存在可计算函数 h(x)，使0 (x,x)盹h(x,x)=0 (x,x)+a,a N, 0 (x,y)是编号为y输入为x时的程序。2001年10月1、a, b上递归枚举语言是否可数？证明2、 L=a , b, c数目相同的语言是否CFL (上下文无关)？证明p95证：不是上下文无关的。假设L是上下文无关的，则它与正则语言a b* c*的交也是上下文无关的。令L1= anbncn:n 0假设L1是上下文无关语言。取常数 p ,3= ap bp cp ,丨3丨=3p p将3写
11、成3= uvxyz使得v或y不是空串且uvixyize liI=0,1,2其中 I xy l 1 且 I xuy lss, s-asb, s-abs,证明由s推得的字符串不可能以 abb开头。（可能记忆有误，具体形式就是这样）。4证明不是所有的递归可枚举集都是递归的。定理：语言H = W J : Turing Machine M halts on input string 3 不是递归的；所以，递归语言类是递归可枚举语言类的真子集。2002年10月1、型？什么是计算？计算理论研究的内容和意义是什么？为什么要使用计算的抽象模2、请写出一个正则表达式，描述下面的语言：在字母表0,1 上，不包含 0
12、0 子串且以1 结尾。4、语言 L=a n:n 是素数 是不是正则语言，是不是上下文无关的？5、一个succ(n+1)的组合Turing机描述，说出它的作用。P1276、什么是 Turing 机的停机问题？它是可判定的么？为什么？H= “M”“w”：Turing 机 M 在输入 w 上停机 ，ATM = |M 是一个 TM , 且 M 接受 3 证明：假设 ATM 是可判定的，下面将由之导出矛盾。设 H 是 ATM 的判定器。 令 M 是一个 TM ， 3是一个串。在输入 上，如果 M 接受 3，则 H 就停机且接受3；如果 M 不接受3，则 H 也会停机，但拒绝3。 换句话说，H是一个TM使得：接受 如果M接受3H()=拒绝 如果 M 不接受3现在来构造一个新的图灵机 D，它以H作为子程序。当M被输入 它自己的描述是，TM D就调用H，以了解M将做什么。一 旦得到这个信息， D 就反着做，即：如果 M 接受，它就拒绝；如果M不接受，它就接受。下面是 D 的描述。D=”对于输入，其中M是一个TM :1) 在输入 M, 上运行 H。2) 输出 H 输出的相反结论，即，如果 H 接受，就拒绝；如果 H 拒绝，就接受。 ”总而言之，接受 如果 M 不接受 D(
