计算理论知识点.docx
5星 · 超过95%的资源 需积分: 38 171 浏览量
2020-08-02
22:19:32
上传
评论 1
收藏 18KB DOCX 举报 
＋
1. 如果一个语言被有穷自动机识别， 则这个语
言是正则语言。
2. 正则语言在并运算、 连结、星号运算下封闭
3. 每一台非确定有穷自动机都等价与一台确
定型有穷自动机。
4. 一个语言是正则的当且仅当有一台非确定
型有穷自动机识别。
5. 空集连接到任何集合上得到空集， 空串连接
到任何一个串上不改变这个字符串。
6. 一个语言是正则的， 当且仅当有一个正则表
达式描述。
7. 如果一个语言是正则的， 则可以用正则表达
式描述它。
8. 任何一个上下文无关语言都可以用乔姆斯
基范式的上下文无关文法产生。
9. 一个语言是上下文无关的当且仅当存在一
台下推自动机识别它。
10. 如果一个语言被下推自动机识别， 则它是上
下文无关的。
11. 每一个正则语言都是上下文无关的。
1. ——格局 图灵机计算过程中， 当前状态、 当
前带内容和读写头当前的位置组合在一起， 称
为图灵机的格局。
2. 图灵可识别 （递归可枚举语言） ——如果一
个语言可能被某一图灵机识别， 则称该语言
是图灵可识别的。
3. 图灵可判定 （递归语言） ——如果一个语言
能被某一图灵机判定， 则称它是一个图灵可
判定的。
——在输入上运行一个 TM 时，可能出现三种结
果：接受、拒绝或者循环。这里循环仅仅指机器
不停机，而不一定是这个词所指的那样，永远以
同样的方式重复同样的步骤。
——图灵机有两种方式不接受：一种是它进入拒
绝状态而拒绝它，另一种是进入循环。
4. ——判定器 有时候很难区分进入循环还是
需要耗费很长时间的运行， 因此， 我们更
喜欢讨论所有输入都停机的图灵机，他们永远
不循环， 这种机器称为判定器。 他们总是能
决定接受还是拒绝， 也称识别某个语言的判
定器判定该语言。
5. 每一个可判定语言都是图灵可识别的。
6. 每一个多带图灵机等价于一个单带图灵机。
7. 非确定型图灵机都等价于一个确定型图灵
机。
8. 如果一个语言是图灵可识别的， 当且仅当存
在非确定型图灵机识别它。
9. 一个语言是图灵可判定的， 当且仅当存在非
确定型图灵机判定它。
10. ——丘奇图灵论题 算法的明确定义。
11. ——① 详细描述图灵机的术语 形式化描述， 详
尽的写出图灵机的状态、 转移函数， 这
是最底层次的、 最详细程度的描述。 ②描述
水平要高一些， 称为实现描述， 使用日常用
语来描述图灵机， ③没有给出状态和转移函数
高水平描述， 他也是使用日常用语来描述算
法， 忽略了实现模型不需要提及图灵机怎样 管
理它的带子和读写头。
12.
A
DFA
（确定型有穷自动机） 、 A
NFA
（非确定
型有穷自动机） 、 A
REX
（正则表达式）、
EDFA
（判 Φ 的确定型有穷自动机）
、EQ
DFA
（两个判别同一个语言的 DFA ）、
A CFG
（上下文无关文法） 、Ｅ
CFG
（ 判 Φ 上下
文无关文法）、
A LBA
（线性界限自动机） 、是一个可判定语
言每一个上下文无关语言是可判定的。
A TM
（图灵机） 、停机问题、 HALT
TM
（一个
图灵机对于给定的输入是否停机） 、 E
TM
（不接受
任何 语 言 图 灵 机 ） 、 REGULAR
TM
（正则 图 灵
机）、
EQTM
（接受串相等的图灵机） 、
ELBA
（不接受语言的线性界限自动
机） 、
ALL CFG
、PCP（波斯地图对应实例）
是不可判定的。
A TM
（补）是不可识别的。
13. 一个语言的补是由不在此语言中的所有串 构
成的语言。 如果一个语言的补集是图灵可识
别的语言，则称它是补图灵可识别的。
14. 一个语言是可判定的， 当且仅当它既是图灵
可识别的，也是补图灵可识别的。
15. 设 M 是一个图灵机， w 是一个串。 M 在 w
上的一个接受计算历史（ accepting
computation history）是一个格局序列 C
1
、
C2
、 、 C
l
，其中 C
1
是 M 在 w 上的起
始格局， C
l
是 M 的一个接受格局，且每个 C
i
都是 C
i-1
的结果，即符合 M 规则。 M 在 w
上的一个拒绝计算历史可类似定义。只是
C
l
是一个拒绝格局。
16. 计算历史都是有限序列。如果 M 在 w 上
永不停机，则在 M 上既没有接受历史，也没
有拒绝计算历史存在。 确定型机器在任何给
定的输入上最多只有一个计算历史。 非确定
型机器即使在单个输入上都有多个计算历
史，他们与各个分支相对应。
17. 线性有穷自动机是一种受到限制的图灵机，
它不允许其读写头离开包含输入带的区域。
如果此机器试图将它的读写头离开输入的
两个端点， 则读写头就在原地保持不动。 这
与普通的图灵机读写头不会离开带子的左
端点方式一样。
18. 讲一个问题归约为另一个问题的概念可以
用多种方式来定义， 选择哪种方式要根据具
体应用的情况。 我们选择一种简单方式的可
归约性，叫做映射可归约性。
19. 用映射可归约性把问题 A 归约为问题 B 指
的是：存在一个可计算函数，他将问题 A
的实例转换成问题 B 的实例。如果有了这样
一个转换函数（称为归约） ，就能用 B 的解
决方案来解决 A。
20. 函数 f ∑： * →∑ * 是一个可计算函数，如果有
某个图灵机 M，使得每个输入 w 上 M 停
机，且此时只有 f(w) 出现在带上。
21. 语言Ａ是映射可归约到语言Ｂ的， 如果存在
可计算函数 f ∑： *→∑ *使得对每个ｗ
∈ ｗ Ａ <=>f(w) ∈Ｂ
22.
≤ 记做Ａ
ｍ Ｂ，称作函数ｆ为Ａ到Ｂ的归约。
≤ 如果Ａ ｍ Ｂ且Ａ是不可判定的， 则Ｂ也是不
可判定的。
≤ 如果Ａ ｍ Ｂ且Ｂ是图灵可识别的， 则Ａ也是
图灵可识别的
23.
EQTM
既不是图灵可识别的，也不是补图
灵可识别的。
24.
→令ｔ：Ｎ Ｒ
是一个函数，定义时间复杂
性类 TIME(t(n)) 为由时间 O(t(n)) 的图灵机可
判定的所有语言的集合。
25. t(n) 是一个函数， t(n) ≥n。则每一个多带图
灵机都和 某一个 O(t2
(n))时间的单带图灵
机等价。
26. t(n) 是一个函数， t(n)≥n 。则每一个 t(n)时间
的非确定型单带图灵机都与某一个 2
O(t(n))
时
间的确定型单带图灵机等价。
27. P 类是一个语言类，该类在多项式时间内可
判定。
28. PATH∈ P 、 RELPRIME ∈ P、每一个上下文
无关文法都是 P
29. 一个语言在 NP 中，当且仅当它能被某个非
确定型多项式时间的图灵机判定。
30. {HAMPATH, CLQUE, SUBSET-SUM, SAT,
3SAT, UHAMPATH, } ∈ NP
31. P=成员可以快速判定的语言类
NP=成员可以快速验证的语言类
32. 若存在多项式时间图灵机 M ，使得在任何输
入 w 上，M 停机时 f(w) 恰好在带上， 函数 f：
∑*→∑ * 是一个多项式时间可计算函数。
33. 语言 A 称作多项式时间映射可归约到语言
B，或者简称为多项式时间可归约到 B，记
≤为Ａ p Ｂ，若存在多项式时间可计算函数
f ∑： *→∑ * ，对于每一个 w，有
∈ ｗ Ａ <=>f(w) ∈Ｂ
函数 f 称为 A 到 B 的多项式时间归约。
34. 列文-库克定理
SAT∈ P ，当且仅当 P=NP
35. 3SAT 多项式时间可归约到 CLIQUE 。
36.
令 f ：N→R+
是一个函数。空间复杂性类和
NSPACE(f(n))
定义如
下：
SPACE(f(n))={L|L 是被 O(f(n)) 空间的确定型
图灵机判定的语言 }
NSPACE(f(n))={L|L 是被 O(f(n)) 空间的非确定
型图灵机判定的语言 }
37. 萨维奇定理
资源评论
LauraKuang2023-07-24这个文件是学习计算理论的好帮手，简洁而实用，值得一读。
乔木Leo2023-07-24作者在文件中给出了详细的实例和案例，有助于读者更好地理解理论知识，很贴心。
白羊的羊2023-07-24这个文件对计算理论的关键知识点进行了清晰的阐述，适合小白入门，很实用。
黄浦江畔的夏先生2023-07-24文件内容扎实，逻辑严密，能够帮助读者理解和应用计算理论的核心概念。
Friday永不为奴2023-07-24文件语言简练明了，不过分炫技，让人易于理解计算理论的重要概念。
