logo资料库

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

发布时间：2022-06-05 发布人：admin 分类：说明书 资料大小：0.23M 资料格式：doc 举报 版权申诉
第1页 / 共13页
第2页 / 共13页
第3页 / 共13页
第4页 / 共13页
第5页 / 共13页
第6页 / 共13页
第7页 / 共13页
第8页 / 共13页
资料共13页，剩余部分请下载后查看
    M接收的语言是M接收的所有字符串的集合，记作L(M).
    5）(R10R2),这里R1和R2是正则表达式
    4、NonSelfAccepting是否递归集合
    L1={am bncp:m不等于n，且m、n、p >1}
    2、给出一个Turing包括转移关系等
    L1={w1|w∈{a,b}* ,Na(w)-Nb(w) mod 3 ≠0}
    （1）Xi1+Xi2+……Xik=(X1+X2+……Xn)/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 年，图灵向伦敦权威的数学杂志投了一篇论文，题为《论数字计算在决断难题 中的应用》。在这篇开创性的论文中，图灵给“可计算性”下了一个严格的数学定义，并 提出著名的“图灵机”(Turing Machine)的设想。“图灵机”不是一种具体的机器，而是一 种思想模型，可制造一种十分简单但运算能力极强的计算机装置，用来计算所有能想 像得到的可计算函数。这个装置由下面几个部分组成：一个无限长的纸带，一个读写头。 （中间那个大盒子），内部状态（盒子上的方块，比如 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），为什么？ 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={anbncn:n≧0} 假设 L1 是上下文无关语言。 取常数 p，ω＝a pb pc p ,∣ω∣＝3p≥p
    将ω写成ω＝uvxyz 使得 v 或 y 不是空串且 uvixyiz∈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 月 能被 5 整除的字符串是正则集吗 用图灵机表示下列字符串。Φ，e，{a},{a}* s->ss, s->asb, s->abs, 证明由 s 推得的字符串不可能以 abb 开头。（可能记忆 1． 2． 3． 有误，具体形式就是这样）。 4 证明不是所有的递归可枚举集都是递归的。 定理：语言 不是递归的；所以，递归语言类是递归可枚举语言类的真子集。 2002 年 10 月
    1、 型？ 2、 1 结尾。 什么是计算？计算理论研究的内容和意义是什么？为什么要使用计算的抽象模 请写出一个正则表达式，描述下面的语言：在字母表{0,1}上，不包含 00 子串且以 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 被输入 它自己的描述是，TM D 就调用 H，以了解 M 将做什么。一 得到这个信息，D 就反着做，即：如果 M 接受，它就拒绝；如果 旦 M 不接受，它就接受。下面是 D 的描述。 D＝”对于输入，其中 M 是一个 TM： 1) 在输入>上运行 H。 2) 输出 H 输出的相反结论，即，如果 H 接受，就拒绝； 如果 H 拒绝，就接受。” 接受 如果 M 不接受 总而言之， D()= 拒绝 如果 M 接受 接受 如果 D 不接受 拒绝 如果 D 接受 D()= 当以 D 的描述作为输入来运行 D 自身时，结果会怎样呢？我们得到： 不论 D 做什么，它都被迫相反地做，这显然是一个矛盾。所以，TM D 和 TM H 都不存在。
    它是不可判定的。 假设 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 是非递归的。 2003 年 4 月 1、判断题目，好像有二十分左右，都是书上的概念，譬如：递归语言是递归可枚举语言（错）， 一个语言如果是正则的，那么它一定是上下文无关语言（对），如果一个语言是图灵可识别 的，那么、、、. （） 。后面的记不住了。 2、证明题，第 1 个是要证某种语言是正则语言，第 2 个是证该语言是上下文无关语言，中 间还有一个是要证明某种语言是非上下文无关语言（有可能是非正则语言）。最后一个是证 明该语言是图灵可判语言。该题在上几届的考题中都曾变换个样式出现过。 3、识图题，画了一个图，让写出该图所识别的语言是什么。我记得它是英文参考书上的一 个例题，所识别的是：不全包含{a,b,c}中所有字符的字符串。该题 6 分。 4、我没做，给出了一个式子，好像是 y=a+b,让构造出计算该式的图灵机。这个题目好像也
    分享到：
    赞 收藏

    相关推荐

    资料库

    考试认证

    共收录20637份资料，累计11个分类，关注成员有19位，主要包括：真题,美赛,软考,PMP,Linux/Unix认证,思科认证,微软认证,Oracle认证,华为认证,软考等考,其它

    热门标签

    真题 美赛 软考 PMP Linux/Unix认证 思科认证 微软认证 Oracle认证 华为认证 软考等考 其它

    最新资料