《计算理论》复习题总结.doc

《《计算理论》复习题总结.doc》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、《计算理论》复习题总结1、自动机、可计算性、复杂性内涵及关系；计算理论的三个传统的核心领域：自动机、可计算性和复杂性。通过“计算机的基本能力和局限性是什么？“这一问题将这三个领域联系在一起。可计算理论与复杂性理论是密切相关的，在复杂性理论中，目标是把问题分成容易计算的和难计算的；而在可计算理论中，是把问题分成可解的和不可解。自动机阐述了计算的数学模型的定义和性质，主要包含两种模型：有穷自动机模型；上下文无关文法模型。可计算性理论和复杂性理论需要对计算机给了一个准确的定义。自动机理论允许在介绍与计算机科学的其他非理论领

2、域有关的概念时使用计算的形式化定义。2、有穷自动机、正则语言、正则表达式、非确定有穷自动机、非正则语言；有穷自动机：描述能力和资源极其有限的计算机模型。是一个5元组（Q，∑，δ，q0,F），其中1）Q是一个有穷集合，称为状态集。2）∑是一个有穷集合，称为字母表。3）δ：Q×∑→Q是转移函数。4）q0Q是起始状态。5）FQ是接受状态集。正则语言：如果一个语言能被有穷自动机识别。正则表达式：用正则运算符构造描述语言的表达式。称R是正则表达式，如果R是：1）a，a是字母表中的一个元素；2）；3）;4）（R1R2）；5）(R

3、1R2)；6）(R1*)非确定有穷自动机：是一个5元组（Q，∑，δ，q0,F），其中1）Q是有穷状态集。2）∑是有穷字母表。3）δ：Q×∑→P（Q）是转移函数。4）q0Q是起始状态。5）FQ是接受状态集。3、上下文无关语言及上下文无关文法、歧义性、乔姆斯基范式、下推自动机、等价性、非上下文无关语言；上下文无关语言：用上下文无关文法生成的语言。上下文无关文法：是一个4元组（V，∑，R，S）且1）V是一个有穷集合，称为变元集2）∑是一个与V不相交的有穷集合，称为终结符集3）R是一个有穷规则集，每条规则由一个变元和一个由变

4、元及终结符组成的字符串构成，4）SV是起始变元歧义性：如果字符串W在上下文无关文法G中有两个或者两上以上不同的最左派生，则称G歧义地产生的字符串W。如果文法G歧义的产生某个字符串则称G是歧义的。乔姆斯基范式：一个上下文无关文法如果它的每一个规则具有如下形式A→BCA→a其中a为任意终结符，ABC为任意变元且BC不是起始变元，此外允许规则S→其中S是起始变元。下推自动机：是6元组Q，∑，，δ，q0,F），这里Q，∑，，F都是有穷集合，并且1）Q是状态集2）∑是字母表3）是栈字母表4）δ：Q×∑×→P（Q×）是转移函数学

5、5）q0Q是起始状态。6）FQ是接受状态集。4、各种等价性；每一台非确定型有穷自动机等价于一台确定的有穷自动机；一个语言是正则的当且仅当可以用正则表达式描述；一个语言是上下文无关的则存在一台下推自动机识别它。5、计算科学；能性问题；Church-Turing论题；计算；可计算；计算科学：系统的研究信息描述和变换的算法，包括其理论、分析、设计、效率、实现和应用。用计算科学涵盖并称谓计算机科学和计算机工程。计算机科学所研究问题的核心是能行问题。能行问题：什么能被（有效的）自动化？什么不能被（有效）的自动化？Church－

6、Turing论题：可计算性等价于Turing机可计算性。计算：Truing机所进行的工作就是计算。可计算：Turing机能够进行的工作就叫可计算。6、几个计算模型；各种计算模型的特点；图灵机的特点；计算模型：1、递归函数。Gödel，Church，等人提出并完善了递归函数理论。从数学演算的思想出发，考虑从简单的、直观上可计算的函数出发构复杂的可计算函数。2、Turing机（理论模型）：Turing研究的Turing机计算模型与现代计算机更接近，在Turing机的基础上引进了大量的自动机。3、Church－λ演算：用来

7、描述计算过程，基本思想主要用于函数式程序语言的研制。4、Post系统（符号变换系统）：Post系统的基础上引进了大量的形式语言。Turing机的特点：存储无穷，时间无限制。Turing机可计算只是理论上可计算，并不是现实可计算。现实可计算：研究计算复杂性。但如果Turing机不可计算则现实更不可计算。7、原语言，指令系统，输入输出规定；原语言：变元、标号（语句标号）、指令：X＝X＋1；X＝X－1；ToAIFX≠0；ToA；Y＝X输入变元用x表示x，x1，x2，x3，……输出变元用y表示，函数只输出一个值。对程序做如下

8、两点规定：1、当程序开始执行时自动认为一切变元的值为0（输入变元除外）2、当程序出现下列两种情形之一时，自动认为停机。a、转向无定义的标号b、执行程序的最后一条指令。8、n元程序对应的n元函数的定义；若程序P恰有n个输入变元X1，X2，……，Xn，而没有其它X变元，则称P为n元程序。n元程序P对应的函数Ψp（X1，X2，……，Xn）定义如下：Ψ