Elements of the theory of com putat ion （2nd） 计算 理论 基础英文版 计算 理论 是国外 计算 机专业常见的课程。 ELEMENTS OF THE THEORY OF COM PUTAT ION Second Edit ion Harry R. Lewis Gordon McKay Professor of Com puter Science Harvard University and Dean of Harvard College Cambridge, Massachusetts Christos H. Papadimitriou C. Lester Hogan Professor of Electrical Engineering and Com puter Science University of California Berkeley, California 哈里·R·刘易斯 Gordon McKay，哈佛大学 计算 机科学教授，马萨诸塞州剑桥哈佛学院院长 克里斯多夫帕帕迪米里奥 C. Lester Hogan，加利福尼亚加利福尼亚大学伯克利分校电气工程与 计算 机科学教授 确定性有限自动机 ( DFA ) 与 非确定性有限自动机 ( NFA ) 之间是相互等价的 ; 确定性的有限自动机 ( DFA ) 可以 看作是非确定性有限自动机 ( NFA ) ; 确定性有限自动机 给定一个输入 , 其输出时唯一的 ; 非确定性有限自动机的定义 包含 确定性有限自动机的 定义中 ; NFA 的后继状态 可以是 00 个 , 11 个 或 多个 , DFA 每个状态只能有 11 个后继状态 ; 确定性有限自动机 ( DFA ) 就是 特殊的 非确定性有限自动机 ( NFA 介绍一种语言，称为简单语言，通过它可以看到 计算 机解决任何问题所需要的最少语句是三条。介绍一种工具，称为图灵机的 计算 机模型，可以看到简单语言可以解决的问题也可以用图灵机解决。证明没有任何程序可以知道另一个程序终止与否。证明本身也表明了有些问题 计算 机是无法解决的。 计算 理论 有三个传统领域：自动机，可 计算 性和复杂性。 自动机 理论 自动机 理论 中包含几种数学模型：有穷自动机模型，可用于文本处理，编译程序，硬件设计；上下文无关文法模型，可用于程序设计语言和人工智能。 有穷自动机： 有穷自动机分确定有穷自动机（DFA）和非确定有穷自动机（ NFA ）。 DFA）D是一个五元组：D=（K，Σ，M，S，F）其中 K：有穷非空的状态集合； Σ：有穷非空的输入 一， 计算 模型：1. 有穷(状态)自动机确定型 有穷自动机定义：由5元组组成，字母集，状态集，转移函数，初始状态，接受状态如果A是机器M接受的全部字符串集，则称A是机器M的语言，记做L(M)=A。也叫M识别A。A={w|M接受w}如果一个语言被一台有穷自动机识别，则称它为正则语言。注意：一般情况描述：机器接受字符串，机器识别语言，M接受w, M识别A给定某个语言，如何设计一台确定型有穷自动机？设计 ... 对任何时间可构造函数，存在语言A，在时间O(t(n))内可判定，但不能在时间o(t(n)/logt(n))内判定。存在某个图灵机在O(f(n))空间内运行，在输入 时，总能停机，停机时f(n)的二进制出现在带子上。存在某个图灵机在O(t(n))时间内运行，在输入 时，总能停机，停机时t(n)的二进制出现在带子上。对任何空间可构造函数，存在语言A，在空间O(f(n))内可判定，但不能在空间o(f(n))内判定。NP问题：算起来不确定快不快的问题，但是我们可以快速验证这个问题的解。