计算机考博试题.pdf

计算理论 字母表： 一个有穷的符号集合。 字母表上的 字符串 是该字母表中的符号的有穷序列。 一个字符串的 长度是它作为序列的长度。 * 连接 L 中 0 个或多个字符串得 连接 反转 Kleene 星号 L ， 到的所有字符串的集合。 有穷自动机： 描述能力和资源极其有限的计算机模型。 有穷自动机是一个 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是正则表达式 0 5）(R1 R2), 这里 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