计算理论字母表：一个有穷的符号集合。

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

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

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

在这篇开创性的论文中，图灵给“可计算性”下了一个严格的数学定义，并提出著名的“图灵机”(Turing Machine)的设想。

“图灵机”不是一种具体的机器，而是一种思想模型，可制造一种十分简单但运算能力极强的计算机装置，用来计算所有能想像得到的可计算函数。

这个装置由下面几个部分组成：一个无限长的纸带，一个读写头。

（中间那个大盒子），内部状态（盒子上的方块，比如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(X R,X)不是可计算的。

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

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

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

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

P56假设L是正则的，则根据在交下的封闭性，L∩a*b*也是封闭的，而后者正好是L1={ a i b i:i ≧0},假设L1是正则的，则存在满足泵引理的整数n。

考虑字符串w= a n b n∈L。

根据定理可以写成w=xyz使得|xy|≦n，且y≠e，即y=a i，其中i＞0.但是xz= a n-i b n 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），为什么？2001年4月1、（1）当x是完全平方时值为2x，否则为2x+1证明其是原始递归函数。

（2）对图灵机模型而言，church论题是什么？（3）通用图灵机的描述。

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

3、A为字母表，L为A*上任意的语言。

阐述其乔姆斯基层次及用可计算性表述它们的关系。

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

2001年10月1、{a，b}上递归枚举语言是否可数？证明2、L={a，b，c数目相同的语言}是否CFL（上下文无关）？证明p95证：不是上下文无关的。

假设L是上下文无关的，则它与正则语言a* b*c*的交也是上下文无关的。

令L1={a n b n c n:n≧0}假设L1是上下文无关语言。

取常数p，ω＝a p b p c p ,∣ω∣＝3p≥p将ω写成ω＝uvxyz使得v或y不是空串且uv i xy i z∈L1 I=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是否递归集合2002年4月1．能被5整除的字符串是正则集吗2．用图灵机表示下列字符串。

Φ，e，{a},{a}*3． s->ss, s->asb, s->abs, 证明由s推得的字符串不可能以abb开头。

（可能记忆有误，具体形式就是这样）。

4 证明不是所有的递归可枚举集都是递归的。

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

2002年10月1、什么是计算？计算理论研究的内容和意义是什么？为什么要使用计算的抽象模型？2、请写出一个正则表达式，描述下面的语言：在字母表{0,1}上，不包含00子串且以1结尾。

4、语言L={a n:n是素数}是不是正则语言，是不是上下文无关的？5、一个succ(n+1)的组合Turing机描述，说出它的作用。

P1276、什么是Turing机的停机问题？它是可判定的么？为什么？H={“M”“w”：Turing机M在输入w上停机}，ATM ＝{<M, ω>|M是一个TM，且M接受ω}证明：假设ATM是可判定的，下面将由之导出矛盾。

设H是ATM的判定器。

令M是一个TM，ω是一个串。

在输入<M, ω>上，如果M接受ω，则H就停机且接受ω；如果M不接受ω，则H也会停机，但拒绝ω。

换句话说，H是一个TM使得：接受如果M接受ωH(<M, ω>)=拒绝如果M不接受ω现在来构造一个新的图灵机D，它以H作为子程序。

当M被输入它自己的描述<M>是，TM D就调用H，以了解M将做什么。

一旦得到这个信息，D就反着做，即：如果M接受，它就拒绝；如果M不接受，它就接受。

下面是D的描述。

D＝”对于输入<M>，其中M是一个TM：1) 在输入<M,<M>>上运行H。

2) 输出H输出的相反结论，即，如果H接受，就拒绝；如果H拒绝，就接受。

”总而言之，接受如果M不接受<M>D(<M>)=拒绝如果M接受<M>当以D的描述<D>作为输入来运行D自身时，结果会怎样呢？我们得到：接受如果D不接受<M>D(<D>)=拒绝如果D接受<M>不论D做什么，它都被迫相反地做，这显然是一个矛盾。

所以，TM D和TM H都不存在。

它是不可判定的。

假设H是递归的，那么H1={“M”：Turing机M在输入字符串“M”上停机}也是递归的。

H1表示对角化程序的halts（X，X）部分。