1. 如果一个语言被有穷自动机识别，则这个语言是正则语言。 2. 正则语言在并运算、 连结、星号运算下封闭 3. 每一台非确定有穷自动机都等价与一台确定型有穷自动机。 4. 一个语言是正则的当且仅当有一台非确定型有穷自动机识别。 5. 空集连接到任何集合上得到空集， 空串连接到任何一个串上不改变这个字符 串。 6. 一个语言是正则的， 当且仅当有一个正则表达式描述。 7. 如果一个语言是正则的， 则可以用正则表达式描述它。 8. 任何一个上下文无关语言都可以用乔姆斯基范式的上下文无关文法产生。 9. 一个语言是上下文无关的当且仅当存在一台下推自动机识别它。 10. 如果一个语言被下推自动机识别， 则它是上下文无关的。 11. 每一个正则语言都是上下文无关的。 1. 格局——图灵机计算过程中， 当前状态、 当前带内容和读写头当前的位置组 合在一起， 称为图灵机的格局。 2. 图灵可识别（递归可枚举语言） ——如果一个语言可能被某一图灵机识别， 则 称该语言是图灵可识别的。 3. 图灵可判定 （递归语言） ——如果一个语言能被某一图灵机判定， 则称它是 一个图灵可判定的。 ——在输入上运行一个 TM 时，可能出现三种结果：接受、拒绝或者循环。这里 循环仅仅指机器 不停机，而不一定是这个词所指的那样，永远以 同样的方式重复 同样的步骤。 ——图灵机有两种方式不接受：一种是它进入拒绝状态而拒绝它，另一种是进入 循环。 4. 判定器——有时候很难区分进入循环还是需要耗费很长时间的运行， 因此， 我们更喜欢讨论所有输入都停机的图灵机，他们永远不循环，这种机器称为判定 器。他们总是能决定接受还是拒绝， 也称识别某个语言的判定器判定该语言。 5. 每一个可判定语言都是图灵可识别的。 6. 每一个多带图灵机等价于一个单带图灵机。 非确定型图灵机都等价于一个确定型图灵机 1. 如果一个语言是图灵可识别的， 当且仅当存在非确定型图灵机识别它。 2. 一个语言是图灵可判定的， 当且仅当存在非确定型图灵机判定它。 3. 丘奇图灵论题——算法的明确定义。 4. 详细描述图灵机的术语——①形式化描述， 详尽的写出图灵机的状态、 转 移函数，这是最底层次的、 最详细程度的描述。 ②描述水平要高一些， 称为 实现描述， 使用日常用语来描述图灵机， 没有给出状态和转移函数③ 高水平 描述， 他也是使用日常用语来描述算法，忽略了实现模型不需要提及图灵机怎 样 管理它的带子和读写头。 ADFA （确定型有穷自动机） 、A NFA （非确定型有穷自动机） 、A REX （正则表 达式） 、 5. EDFA（判 Φ的确定型有穷自动机） 、EQDFA（两个判别同一个语言的 DFA ）、 A CFG（上下文无关文法） 、ＥCFG（判 Φ上下文无关文法）、 

A LBA （线性界限自动机） 、是一个可判定语言每一个上下文无关语言是可判定 的。 A TM（图灵机）、停机问题、 HALT TM（一个图灵机对于给定的输入是否停机） 、 ETM （不接受任何语言图灵机） 、REGULAR TM （正则图灵机） 、EQTM （接受串相 等的图灵机） 、 ELBA （不接受语言的线性界限自动机） 、ALL CFG 、PCP（波斯地图对应实 例）是不可判定的。 A TM （补）是不可识别的。 6. 一个语言的补是由不在此语言中的所有串 构成的语言。 如果一个语言的补集 是图灵可识别的语言，则称它是补图灵可识别的。 7. 一个语言是可判定的， 当且仅当它既是图灵可识别的，也是补图灵可识别的。 设 M 是一个图灵机，w 是一个串。 M 在 w 上的一个接受计算历史（ accepting computation history）是一个格局序列 C 1、C2 、 、Cl ，其中 C 1 是 M 在 w 上的起始格局，Cl 是 M 的一个接受格局，且每个 Ci 都是 Ci-1 的结果，即符合M规则。M在 w上的一个拒绝计算历史可类似定义。只是 Cl 是一个拒绝格局。 7. 计算历史都是有限序列。如果 M 在w 上 永不停机，则在 M 上既没有接 受历史，也没有拒绝计算历史存在。 确定型机器在任何给定的输入上最多只 有一个计算历史。 非确定型机器即使在单个输入上都有多个计 算历 史，他们与各个分支相对应。 8. 线性有穷自动机是一种受到限制的图灵机， 它不允许其读写头离开包含输入 带的区域。如果此机器试图将它的读写头离开输入的 两个端点， 则读写头就在原地保持不动。 这与普通的图灵机读写头不会离开 带子的左 端点方式一样。 9. 讲一个问题归约为另一个问题的概念可以 用多种方式来定义， 选择哪种方 式要根据具体应用的情况。 我们选择一种简单方式的可归约性，叫做映射可归 约性。 10. 用映射可归约性把问题A归约为问题B指的是：存在一个可计算函数，他将问题 A 的实例转换成问题B 的实例。如果有了这样一个转换函数（称为归约），就 能用B的解决方案来解决A。 11. 函数 f：∑ * →∑* 是一个可计算函数，如果有某个图灵机 M，使得每个输入 w 上 M 停机，且此时只有f(w) 出现在带上。 12. 语言Ａ是映射可归约到语言Ｂ的，如果存在可计算函数 f：∑ *→∑ *使得对每 个ｗ ｗ∈Ａ <=>f(w) ∈Ｂ 

13. 记做Ａ≤ ｍＢ，称作函数ｆ为Ａ到Ｂ的归约。如果Ａ≤ ｍＢ且Ａ是不可判定的，则 Ｂ也是不可判定的。 如果Ａ≤ ｍ Ｂ且Ｂ是图灵可识别的， 则Ａ也是图灵可识别的 EQTM 既不是图灵可识别的，也不是补图灵可识别的。 14. 15. 令ｔ：Ｎ→Ｒ 是 一 个 函 数 ， 定 义 时 间 复 杂 性 类 TIME(t(n)) 为 由 时 间 O(t(n)) 的图灵机可判定的所有语言的集合，t(n)是一个函数， t(n) ≥n。则 每一个多带图灵机都和某一个 O(t2(n))时间的单带图灵机等价。 16. 17. 18. t(n)是一个函数， t(n)≥n。则每一个 t(n)时间的非确定型单带图灵机都与某 一个 2O(t(n)) 时间的确定型单带图灵机等价。 P 类是一个语言类，该类在多项式时间内可判定。 PATH∈P、RELPRIME ∈ P、每一个上下文无关文法都是 P 19. 一个语言在 NP 中，当且仅当它能被某个非确定型多项式时间的图灵机判 定。 20. {HAMPATH, CLQUE, SUBSET-SUM, SAT, 3SAT, UHAMPATH, } ∈NP P=成员可以快速判定的语言类NP=成员可以快速验证的语言类 21. 22. 若存在多项式时间图灵机 M ，使得在任何输 入 w 上，M 停机时 f(w) 恰好在带上， 函数 f： ∑*→∑ * 是一个多项式时间可计算函数。 23. 语言 A 称作多项式时间映射可归约到语言B，或者简称为多项式时间可归约 B，记为Ａ≤ pＢ，若存在多项式时间 到 可计算函数f：∑ *→∑ * ，对于每一个 w，有 ｗ∈Ａ <=>f(w) ∈Ｂ 函数 f 称为 A 到 B 的多项式时间归约。 24. 列 文 -库克定理 SAT∈ P，当且仅当 P=NP 3SAT 多项式时间可归约到 CLIQUE 。 25. 26. 令 f ：N→R+是一个函数。空间复杂性类和NSPACE(f(n)) 定义如下： SPACE(f(n))={L|L 是被 O(f(n)) 空间的确定型图灵机判定的语言 } NSPACE(f(n))={L|L 是被 O(f(n)) 空间的非确定型图灵机判定的语言 } 27. 萨维奇定理