精选优质文档-倾情为你奉上计算理论复习题总结1、 自动机、可计算性、复杂性内涵及关系；计算理论的三个传统的核心领域：自动机、可计算性和复杂性。通过“计算机的基本能力和局限性是什么？“这一问题将这三个领域联系在一起。可计算理论与复杂性理论是密切相关的，在复杂性理论中，目标是把问题分成容易计算的和难计算的；而在可计算理论中，是把问题分成可解的和不可解。自动机阐述了计算的数学模型的定义和性质，主要包含两种模型：有穷自动机模型；上下文无关文法模型。可计算性理论和复杂性理论需要对计算机给了一个准确的定义。自动机理论允许在介绍与计算机科学的其他非理论领域有关的概念时使用计算的形式化定义。2、 有穷自动机、正则语言、正则表达式、非确定有穷自动机、非正则语言；有穷自动机：描述能力和资源极其有限的计算机模型。是一个5元组（Q，q0,F），其中1）Q是一个有穷集合，称为状态集。2）是一个有穷集合，称为字母表。3）：QQ是转移函数。4）q0Q是起始状态。5）FQ是接受状态集。正则语言：如果一个语言能被有穷自动机识别。正则表达式：用正则运算符构造描
