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

千里之行，始于足下让知识带有温度。第第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类。每类文法的生成能力与相应的语言自动机

最常见文法的分类系统是诺姆·乔姆斯基于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-ibnL，与定理冲突。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，ω＝apbpcp,∣ω∣＝3p≥p

将ω写成ω＝uyz使得v或y不是空串且uvixyiz∈L1I=0,1,2……其中∣xy∣≥1且∣xuy∣≤p.

有两种可能他们都导致冲突。

假如vy中a、b、c三个符号都浮现，则v和y中必有一个至少含有abc中的两个符号。于是uv2xy2z中abc的罗列挨次不对，有的b在a前或c在a或b前。

假如vy中只浮现a、b、c中的一个或两个符号，则uv2xy2z中a、b、c的个数不相等。

∴与L1是上下文无关语言假设冲突。

综上，L不是2型语言。

3、被2，3整除的非负整数的十进制表示的集合是否正则。

∑={1，2，……9}，L∑*，令L1是非负整数十进制表示的集合，简单看到

L1=0∪{1，2，……9}∑*，因为L1是用正则表达式表示的，故它是一个正则语言。令L2是可以被2整除的非负整数的十进制表示的集合。L2正巧是以0，2，4，6，8结尾的L1的成员组成的集合，即L2=L1∩∑*{0，2，4，6，8}，按照正则语言在交运算下封闭原则，故L2也是一个正则语言。令是可以被3整除的非负整数的十进制表示的集合.一个数可以被3整除当且仅当它的数字之和可以被3整除。构造一台有穷自动机，用它的有穷控制器保存输入数字的模3和。L3是这台有穷自动机接受的语言与L1的交。最后L=L2∪L3，它一定是个正则语言。

4、NonSelfAccepting是否递归集合

2022年4月

1．能被5整除的字符串是正则集吗

2．用图灵机表示下列字符串。Φ，e，{a},{a}*

3．s->ss,s->asb,s->abs,证实由s推得的字符串不行能以abb开始。（可能记忆有误，详细形式就是这样）。

4证实不是全部的递归可枚举集都是递归的。

定理：语言

不是递归的；所以，递归语言类是递归可枚举语言类的真子集。

2022年10月

1、什么是计算？计算理论讨论的内容和意义是什么？为什么要使用计算的抽象模型？

2、请写出一个正则表达式，描述下面的语言：在字母表{0,1}上，不包含00子串且以1结尾。

4、语言L={an:n是素数}是不是正则语言，是不是上下文无关的？

5、一个succ(n+1)的组合Turing机描述，说出它的作用。P127

6、什么是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被输入

它自己的描述是，TMD就调用H，以了解M将做什么。一旦

得到这个信息，D就反着做，即：假如M接受，它就否决；假如M

不接受，它就接受。下面是D的描述。

D＝”对于输入，其中M是一个TM：

1)在输入>上运行H。

2)输出H输出的相反结论，即，假如H接受，就否决；

假如H否决，就接受。”

总而言之，接受假如M不接受

D()=

否决假如M接受

当以D的描述作为输入来运行D自身时，结果会怎样呢？我们得到：

接受假如D不接受

D()=

否决假如D接受

不论D做什么，它都被迫相反地做，这明显是一个冲突。所以，TMD和

TMH都不存在。

它是不行判定的。

假设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在ω上循环，则机器U在输入上循环，这就是U不判定ATM的缘由。如果M知道自己在ω上不停机，它能否决ω，但事实上，它不

知道。所以ATM有时被称为停机问题。

7、证实这个问题不行判定：一个Turing机半判定的语言等于这样的一个语言，这个语言是w和w的转置的衔接。

定理：任何递归或递归可枚举语言，以及任何递归函数，分离可用随机存取Turing判定、半可判定和计算。

1、判定下述语言是否正则：包含aaaaa子串的语言L。

2、画出判定下述语言的图灵机：空集，e，a。

3、用数学归纳法证实一个上下文无关语言不包含ab子串，语言的描述遗忘啦。

4、证实H是非递归的。

2022年4月

1、推断题目，好似有二非常左右，都是书上的概念，譬如：递归语言是递归可枚举语言（错），一个语言假如是正则的，那么它一定是上下文无关语言（对），假如一个语言是图灵可识别的，那么、、、.（）。后面的记不住了。

2、证实题，第1个是要证某种语言是正则语言，第2个是证该语言是上下文无关语言，中间还有一个是要证实某种语言是非上下文无关语言（有可能是非正则语言）。最后一个是证实该语言是图灵可判语言。该题在上几届的考题中都曾变换个样式浮现过。

3、识图题，画了一个图，让写出该图所识别的语言是什么。我记得它是英文参考书上的一个例题，所识别的是：不全包含{a,b,c}中全部字符的字符串。该题6分。

4、我没做，给出了一个式子，好似是y=a+b,让构造出计算该式的图灵机。这个题目好似也

是6分。

2022年10月

1、5个推断，比如

例如：

1.也为正则语言。

2.对于两个随意的正则表达式R1和R2，推断L(R1)=L(R2)为不行判定问题。

3、｛xy|x属于正则语言L，y属于其补｝是正则语言；

4、存在非递归的递归可枚举语言。

2、｛（a^m）（b^m）c（a^2n）（b^2n），m，n∈N∩m、n≧1｝，写出产生它的上下文无关文法和识别它确实定下推自动机。

3、推断谓词是否递归;设P(x,y)为原始递归谓词，请证实也是原始递归谓词。

4、写出识别｛（0^n）（1^n）（2^n）n≧0｝的图灵机，和a^nb^nc^n类似，参考书的答案有问题！

5）L={a2n+1|n>=0}不是上下文无关语言，用泵引理证实（其中，2为平方）

?在字母表T={a}上，L={a2n+1|n>=0}

?表示随意一对aa(包括0对)后跟一个a的字符串。（即含有奇数个a的字

符串。）

6）L是一上下文无关文法，任给一正规文法R，L∈R可以判定吗，说明理由。

2022年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)+x(p+1)+...+x(n)（式子类似这样的）

给出算法的描述,复杂度,并证实属于P类

4、给出图灵机的符号表示：该图灵机计算函数f(x);x为偶数f(x)=x/2,x为奇数f(x)=x+1

5、用泵定理证实语言L不是上下文无关的L={w∈(a,b)*:w不同于WR}

2022年10月

1、构造上下文无关文法来生成语言

L1={ambncp:m不等于n，且m、n、p>1}

L2={ambncp:n不等于p，且m、n、p>1},并证实{{a,b,c}*-(L1∪L2)}不是上下文无关的

2、给出一个Turing包括转移关系等

按照给定的Turing的计算过程求出它所接受的语言L(M);并构造一个文法来生成L(M)

3、一个有关递归的推断题，并说出理由，有3句话。

4、一个按照语言描述来判定两个语言之间关系的挑选题。如1是2的真子集，2是1的真子集，1=2，1、2无任何关系。

2022年4月

1、推断题

2、判定下列语言是否为正则语言，请详细说出理由

L1={w1|w∈{a,b}*,Na(w)-Nb(w)mod3≠0}

L2={w1|w∈{a,b}*,Na(w)-Nb(w)≠0}这里Na(w)、Nb(w)分离表示字符串w中a,b的个数

3、给出上下文无关文法生成语言L3=｛xcy|2|x|=|y|,x,y∈{a,b}*｝

证实L4={aibjcidj:i,j∈N,i,j≧1}不是上下文无关语言。

4、证实语言L5={“M”|Turing在空串e上停机}是非递归的，其中M表示TuringM的编码。

5、给定n个数，x1,x2,……xn,判定是否存在不同的i1,i2……ik,使满足下列两个条件：

（1）Xi1+Xi2+……Xik=(X1+X2+……Xn)/2

(2)Xi1+Xi2+……Xik不是素数，给出一个算法，并估量其计算时光，说明这个问题属于NP类，是给算法描述即可。

2022年4月

1、设上下文无关语言L={a}*

（1）假设L为无限语言，且上下文无关文法G生成该语言，即L=L（G）。设K〉1为相对于文法G的泵定理常数，设r=k。证实下列结论：对于随意w∈L，假如|w|≧k，则{wam|n≧0}?L

（2）对于每个i（0≦i|无向图Ｇi=(Vi,Ei)(i=1,2)同构}是ＮＰ的。（只需要给出一个非形式化的描述）