计算理论
字母表：一个有穷的符号集合。
字母表上的 字符串是该字母表中的符号的有穷序列。 一个字符串的 长度是它作为序列的长度。
连接 反转 Kleene星号L*，连接L中o个或多个字符串得 到的所有
字符串的集合。
有穷自动机：描述能力和资源极其有限的计算机模型。
有穷自动机是一个5元组M=(K ,刀,、,s,F ),其中 1) K是一个有穷的集合，称为状态集 2) 刀是一个有穷的集合，称为字母表 3)
是从KXS^ K的函数，称为转移函数
4) s � K是初始状态 5) F K是接收状态集
M接收的语言是M接收的所有字符串的集合，记作 L(M).
对于每一台非确定型有穷自动机，有一台等价的确定型有穷自动机 有穷自动机接受的语言在并、连接、 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年，图灵向伦敦权威的数学杂志投了一篇论文，题为《论数字计算在决断难题 中的应用》。在这篇开创性的论文中，图灵给 提出著名的 图灵机”(Turing Machine)的设想。
可计算性”下了一个严格的数学定义，并 图灵机”不是一种具体的机器，而是一
种思想模型，可制造一种十分简单但运算能力极强的计算机装置，用来计算所有能想 像得到的可计算函数。这个装置由下面几个部分组成：一个无限长的纸带，一个读写头。 (中间那个大盒子)，内部状态(盒子上的方块，比如
A,B,E,H )，另外，还有一个程序对这
个盒子进行控制。这个装置就是根据程序的命令以及它的内部状态进行磁带的读写、移动。
工作带被划分为大小相同的方格，每一格上可书写一个给定字母表上的符号。控制器 可以在带上左右移动，它带有一个读写出一个你期待的结果。这一理论奠定了整个现
代计算机的理论基础。 机的发展史中。
图灵机”更在电脑史上与 冯诺依曼机”齐名，被永远载入计算
图灵机在理论上能模拟现代数字计算机的一切 运算,可视为现代数字计算机的数学模型。实际上 一切\可计算\函数都等价于图灵机可计算函数，而图灵机可计算函数类又等价于一般递归函数类。
2、说明按乔姆斯基分类，语言、文法、自动机的关系
乔姆斯基将语言定义为，按一定规律构成的句子或符号串
合，记为L。数目有限的规则叫文法，记为
文法与自动机的关系：形式文法是从生成的角度来描述语言的
string的有限的或无限的集
G。刻画某类语言的有效手段是文法和自动机。
，而自动机是从识别的角度来描
，如果存在一个该语言
述语言的.文法和自动机是形式语言理论的基本内容。对某种语言来说 的生成过程，就一定存在一个对于它的识别过程 是VN中的初始符号，P是重写规则。
.就描述语言来讲，形式语言 和自动机是统一
的.文法在形式上定义为四元组： G=（ VN,VT,S,P ） ,VN是非终极符号，VT是终极符号，S
形式语言
自动机（接收机） 图灵机
线性有界自动机
下推式存贮自动机
有限自动机
图1*1形式语害和自动机的关联归类图
文法是定义语言的一个数学模型，而自动机可看作是语言的识别系统。
对于一个文法产生的语言，可以构造相应自动机接受该语言：一个自动机接受的语 言，可以构造对应的文法产生该语言。一定类型的自动机和某种类型的文法具有等 价性。
2、乔姆斯基根据转换规则将文法分作 4类。每类文法的生成能力与相应的语言自动机
（识别语言的装置）的识别能力等价，即 4类文法分别与4种语言自动机对应: 类型 0型 1型 2型
文法 无限制文法 上下文有关文法 上下文无关文法 有限状态的正则文法 自动机 图灵机 线性有界自动机 r后进先出自动机 有限自动机 3型 最常见文法的分类系统是
诺姆乔姆斯基于1956年发展的乔姆斯基谱系，这个分
无限制文法、上下文相关文法、上下文无关文法和
递归可枚举语言、上下文相关语言、上下文
但由于高效率的实
例如对下文无关语言存在算法可以生
类谱系把所有的文法分成四类型：
正规文法。四类文法对应的语言类分别是
无关语言和正规语言。这四种文法类型依次拥有越来越严的产生式规则，同时文法所能 表达的言也越来越少。尽管表达能力比无限文法和上下文相关文法要弱， 现，四类文法中最重要的上下文无关文法和正规文法。 成高效的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是正则的，则存在满足泵引理的整数 n。考虑字符串w= anbn� L。根据定理可 以写成w=xyz使得|xy| w n,且
沪e,即y=ai，其中i > 0.但是xz= a^''b'' L,与定理矛盾。
2000年10月
1、 (1)
(2 )对图灵机模型而言，church论题是什么？
(3 )当x是完全平方时值为 3x，否则为3x+1证明其是原始递归函数。
给出图灵机的格局、计算及图灵机 □计算函数f的精确定义。
心）二严 if ⑶）=
* 12x +1 else
设噹心O时LGO艇工的所白因子上利：cr(O)=0. 试证切bCO足饰始递!Hrm
wlieie.
J 1, if K工 | ,Vj jo*, else
3、设7T(X)足小r等「兀的蠱数的个数.试证明更⑴是原始递H的。
兀(工)二工gd)
r-0
1, if xA 2 、证明0( X, X)是不可计算的。 3、 证明L={ambn|m,n>O,m丰n}是上下文无关的，但不是正则的。 利用上下文无关语言在并、连接、 Kleene星号下是封闭的。 正则语言在交运算下封闭。 4、 A为有穷字母表，L是A*的无穷子集， (1 )证明存在无穷序列 次。 (2) 是否存在从L构造序列3 0, 3 1, 3 2??的算法(即i由计算3 i ,为什么？ 3 0, 3 1, 3 2；它由L的所有字组成，每个字恰好在其中只出现一 2001年4月 1、 ( 1)当x是完全平方时值为 2x，否则为2x+1证明其是原始递归函数。 (2) (3) 通用图灵机的描述。 2、 (1)用有穷自动机构造正则语言，以 a2b结尾的字符串组成的正则语言 L 对图灵机模型而言， church论题是什么？ (2) L={a3n bn |n>0}为上下文无关，但不是正则。 3、 A为字母表，L为A*上任意的语言。阐述其乔姆斯基层次及用可计算性表述它们的关系。 4、 证明不存在可计算函数 h(x)，使0 (x,x)盹h(x,x)= 0 (x,x)+a,a N, 0 (x,y)是编号为y输入 为x时的程序。
浙江大学计算机考博试题计算理论及答案
