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

计算理论 ,s,F),其中 1）K是一个有穷的集合，称为状态集 2）∑是一个有穷的集合，称为字母表 3）是从KX∑→K的函数，称为转移函数 4）s∈K是初始状态 5）FK是接收状态集 M接收的语言是M接收的所有字符串的集合，记作L(M). 对于每一台非确定型有穷自动机，有一台等价的确定型有穷自动机 有穷自动机接受的语言在并、连接、Kleene星号、补、交运算下是封闭的。 每一台非确定型有穷自动机都等价于某一台确定型有穷自动机。 一个语言是正则的当且仅当它被有穷自动机接受。 正则表达式：称R是一个正则表达式，如果R是 1）a，这里a是字母表∑中的一个元素。 2），只包含一个字符串空串的语言 3），不包含任何字符串的语言 4)(R1∪R2),这里R1和R2是正则表达式 5）(R10R2),这里R1和R2是正则表达式 6）(R1*),这里R1*是正则表达式 一个语言是正则的当且仅当可以用正则表达式描述。 2000年4月 1、根据图灵机理论,说明现代计算机系统的理论基础。 1936年，图灵向伦敦权威的数学杂志投了一篇论文，题为《论数字计算在决断难题中的应用》。在这篇开创性的论文中，图灵给“可计算性”下了一个严格的数学定义，并提出著名的“图灵机”(Turing Machine)的设想。“图灵机”不是一种具体的机器，而是一种思想模型，可制造一种十分简单但运算能力极强的计算机装置，用来计算所有能想像得到的可计算函数。工作带被划分为大小相同的方格，每一格上可书写一个给定字母表上的符号。控制器可以在带上左右移动，它带有一个读写出一个你期待的结果。这一理论奠定了整个现代计算机的理论基础。“图灵机”更在电脑史上与“冯·诺依曼机”齐名，被永远载入计算机的发展史中。图灵机在理论上能模拟现代数字计算机的一切运算,可视为现代数字计算机的数学模型。实际上,一切可计算函数都等价于图灵机可计算函数,而图灵机可计算函数类又等价于一般递归函数类。2、说明按乔姆斯基分类，语言、文法、自动机的关系文法与自动机的关系:形式文法是从生成的角度来描述语言的,而自动机是从识别的角度来描述语言的.对某种语言来说,如果存在一个该语言的生成过程,就一定存在一个对于它的识别过程.就描述语言来讲,形式语言和自动机是统一的.最常见文法的分类系统是 诺姆·乔姆斯基 于 1956年 发展的 乔姆斯基谱系 ，这个分类谱系把所有的文法分成四类型： 无限制文法 、 上下文相关文法 、 上下文无关文法 和 正规文法 。四类文法对应的语言类分别是 递归可枚举语言 、 上下文相关语言 、 上下文无关语言 和 正规语言 。这四种文法类型依次拥有越来越严的产生式规则，同时文法所能表达的言也越来越少。尽管表达能力比无限文法和上下文相关文法要弱，但由于高效率的实现，四类文法中最重要的上下文无关文法和正规文法。例如对下文无关语言存在算法可以生成高效的 LL 分析器 和 LR 分析器 。、证明HALT(X,X)不是可计算的。、1）、证明递归集都是递归可枚举集。 2）、举例属于递归可枚举集但不是递归集的集合，并证明之。、1）、证明L＝{(a,b)*|a,b的个数相同}为上下文无关语言。 2）、并证明其不是正则的。Pa*b*也是封闭的，而后者正好是L1={ aibi:i≧0},假设L1是正则的，则存在满足泵引理的整数n。考虑字符串w= anbn∈L。根据定理可以写成w=xyz使得|xy|≦n，且y≠e，即y=ai ，其中i＞0.但是xz= an-ibnL，与定理矛盾。 2000年10月 1、（1）给出图灵机的格局、计算及图灵机μ计算函数f的精确定义。(2 ) 对图灵机模型而言，church论题是什么？（3）当x是完全平方时值为3x，否则为3x+1证明其是原始递归函数。2、证明φ（X，X）是不可计算的。3、证明L={ambn|m,n0,m≠n}是上下文无关的，但不是正则的。4、A为有穷字母表，L是A*的无穷子集，（1）证明存在无穷序列ω0,ω1,ω2…，它由L的所有字组成，每个字恰好在其中只出现一次。（2）是否存在从L构造序列ω0,ω1,ω2…,的算法（即i由计算ωi），为什么？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时的程序。、 b* c*