计算机考博试题计算理论及答案

千里之行，始于足下让知识带有温度。第第2页/共2页精品文档推荐计算机考博试题计算理论及答案计算理论

字母表：一个有穷的符号集合。

字母表上的字符串是该字母表中的符号的有穷序列。

一个字符串的长度是它作为序列的长度。

衔接反转Kleene星号L*，衔接L中0个或多个字符串得到的全部字符串的集合。

有穷自动机：描述能力和资源极其有限的计算机模型。

有穷自动机是一个5元组M=(K,∑,?,s,F),其中

1）K是一个有穷的集合，称为状态集

2）∑是一个有穷的集合，称为字母表

3）?是从KX∑→K的函数，称为转移函数

4）s∈K是初始状态

5）F?K是接收状态集

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年，图灵向伦敦权威的数学杂志投了一篇论文，题为《论数字计算在决断难题中

的应用》。在这篇开创性的论文中，图灵给“可计算性”下了一个严格的数学定义，并

提出闻名的“图灵机”(TuringMachine)的设想。“图灵机”不是一种详细的机器，而是一种思想模型，可创造一种非常容易但运算能力极强的计算机装置，用来计算全部能想像得到的可计算函数。这个装置由下面几个部分组成：一个无限长的纸带，一个读写头。（中间那个大盒子），内部状态（盒子上的方块，比如A,B,E,H），另外，还有一个程序对这个盒子举行控制。这个装置就是按照程序的命令以及它的内部状态举行磁带的读写、移动。工作带被划分为大小相同的方格，每一格上可书写一个给定字母表上的符号。控制器可以在带上左右移动，它带有一个读写出一个你期盼的结果。这一理论奠定了囫囵

现

代计算机的理论基础。“图灵机”更在电脑史上与“冯·诺依曼机”齐名，被永久载

入计算机的进展史中。

图灵机在理论上能模拟现代数字计算机的一切运算,可视为现代数字计算机的数学模型。实际上,一切可计算函数都等价于图灵机可计算函数,而图灵机可计算函数类又等价于普通递归函数类。

2、说明按乔姆斯基分类，语言、文法、自动机的关系

乔姆斯基将语言定义为，按一定逻辑构成的句子或符号串string的有限的或无限的集合，记为L。数目有限的规章叫文法，记为G。刻画某类语言的有效手段是文法和自动机。文法与自动机的关系:形式文法是从生成的角度来描述语言的,而自动机是从识别的角度来描述语言的.文法和自动机是形式语言理论的基本内容。对某种语言来说,假如存在一个该语言的生成过程,就一定存在一个对于它的识别过程.就描述语言来讲,形式语言和

自动机是统一的.文法在形式上定义为四元组：G＝（VN,VT,S,P）,VN是非终极符号，VT是终极符号，S是VN中的初始符号，P是重写规章。

?文法是定义语言的一个数学模型，而自动机可看作是语言的识别系统。

?对于一个文法产生的语言，可以构造相应自动机接受该语言：一个自动机接受的语言，可以构造对应的文法产生该语言。一定类型的自动机和某种类型的文法具有等价性。

2、乔姆斯基按照转换规章将文法分作4类。每类文法的生成能力与相应的语言自动机（识别语言的装置）的识别能力等价，即4类文法分离与4种语言自动机对应：

类型文法自动机

0型无限制文法图灵机

1型上下文有关文法线性有界自动机

2型上下文无关文法后进先出自动机

3型有限状态的正则文法有限自动机

最常见文法的分类系统是诺姆·乔姆斯基于1956年进展的乔姆斯基谱系，这个分类谱系把全部的文法分成四类型：无限制文法、上下文相关文法、上下文无关文法和

正规文法。四类文法对应的语言类分离是递归可枚举语言、上下文相关语言、上下文无关语言和正规语言。这四种文法类型依次拥有越来越严的产生式规章，同时文法所能表达的言也越来越少。尽管表达能力比无限文法和上下文相关文法要弱，但因为高效率的实现，四类文法中最重要的上下文无关文法和正规文法。例如对下文无关语言存在算法可以生

成高效的LL分析器和LR分析器。

3、证实HALT(XR,X)不是可计算的。

4、（1）、证实递归集都是递归可枚举集。

（2）、举例属于递归可枚举集但不是递归集的集合，并证实之。

5、（1）、证实L＝{(a,b)*|a,b的个数相同}为上下文无关语言。

（2）、并证实其不是正则的。P56

假设L是正则的，则按照在交下的封闭性，L∩a*b*也是封闭的，而后者正巧是L1={aibi:i≧0},假设L1是正则的，则存在满足泵引理的整数n。考虑字符串w=anbn∈L。按照定

理可以写成w=xyz使得|xy|≦n，且y≠e，即y=ai，其中i＞0.但是xz=an-ibn?L，与定

理冲突。

2000年10月

1、

（1）给出图灵机的格局、计算及图灵机μ计算函数f的精确定义。

(2)对图灵机模型而言，church论题是什么？

（3）当x是彻低平方时值为3x，否则为3x+1证实其是原始递归函数。2、证实φ（X，X）是不行计算的。

3、证实L={ambn|m,n>0,m≠n}是上下文无关的，但不是正则的。

利用上下文无关语言在并、衔接、Kleene星号下是封闭的。

正则语言在交运算下封闭。

4、A为有穷字母表，L是A*的无穷子集，

（1）证实存在无穷序列ω0,ω1,ω2…，它由L的全部字组成，每个字恰好在其中只浮现一次。

（2）是否存在从L构造序列ω0,ω1,ω2…,的算法（即i由计算ωi），为什么？

2022年4月

1、（1）当x是彻低平方时值为2x，否则为2x+1证实其是原始递归函数。

（2）对图灵机模型而言，church论题是什么？

（3）通用图灵机的描述。

2、（1）用有穷自动机构造正则语言，以a2b结尾的字符串组成的正则语言L（2）L={a3nbn|n>0}为上下文无关,但不是正则。

3、A为字母表，L为A*上随意的语言。阐述其乔姆斯基层次及用可计算性表述它们的关系。

4、证实不存在可计算函数h(x)，使φ(x,x)↓时h(x,x)=φ(x,x)+a,a∈N,φ(x,y)是编号为y输入为x时的程序。

2022年10月

1、{a，b}上递归枚举语言是否可数？证实

2、L={a，b，c数目相同的语言}是否CFL（上下文无关）？证实p95

证：不是上下文无关的。假设L是上下文无关的，则它与正则语言a*b*

c*

的交也是上下文无关的。令L1={anbncn:n≧0}

假设L1是上下文无关语言。

取常数p，ω＝apbpc