计算理论期末复习：四大主线、高频真题与易错清单

简介：这份《计算理论知识点》文档面向备考计算理论期末的学生，尤其适合哈尔滨工程大学相关课程使用，核心作用是把自动机、图灵机、语言理论与计算复杂度等高频考点集中成可背诵的提纲。压缩包仅含1个docx文件，大小约18KB，内容以定理、判定条件和等价关系为主，便于打印或在手机端快速翻阅。文档覆盖正则语言与有穷自动机、正则表达式、上下文无关语言与下推自动机、乔姆斯基范式、图灵可识别与图灵可判定、判定器、映射归约、线性有穷自动机，以及P类、NP类、SAT与3SAT、CLIQUE、库克定理等复杂度要点，并整理了不可判定问题与常见归约结论。已有551人学习，适合考前串联概念、核对易混定义和查漏补缺。

1. 计算理论期末：七成分数压在四条主线和一张清单上

计算理论期末在不少班里流传一句话：背下来你就好了。这话只对一半。卷面上七成以上的分确实落在几条定理和一张清单上，但判卷的人看的是你能不能把定理用在对的位置，背得再熟、方向写反一样是零分。

这门课的骨架就四段：正则语言与有穷自动机、上下文无关语言与下推自动机、图灵机与可判定性、归约与复杂度。前三段回答“是什么、能不能判”，第四段回答“不会的题怎么变成会的题”。选择填空考的是等价刻画的记忆精度，大题考的是归约方向和证明步骤的完整度。

这份笔记适合已经过了一遍教材、但一落笔就卡在“从哪下手”的人。下面按这四段拆开，先给考点分布，再给高频真题的答法，最后把年年有人翻车的地方单独拎出来。能直接拿去背，也能直接拿去练。

2. 正则与上下文无关：三组等价刻画和一条包含链

语言这一层的题，是整张卷子里最稳的分。原因不复杂：它给的对象都能画出来、构造出来，不需要“想”，只需要按固定动作走。真正拉开差距的是两件事——等价刻画记串了，包含链记反了。

2.1 三个等价刻画怎么互相翻译

正则语言这一组有三张面孔：被确定型有穷自动机识别、被非确定型有穷自动机识别、被正则表达式描述。这三句话在卷子上经常被打散成判断、填空、构造三种题型，但底层是一条链：DFA 是 NFA 的特例，NFA 用子集构造确定化，正则表达式和 NFA 之间用归纳构造来回转。

答题时最容易丢分的不是不会，而是漏写“为什么可以转”。比如题目给一个正则表达式要求画自动机，光画出来只得一半分，得说清楚是按并、连接、星号三种运算归纳构造，每加一个运算就加一组新状态和 ε 转移。

这张表要能默写。尤其是第二行那个 2^k——卷子上很爱问“确定化之后状态数最少是多少、最多是多少”，最多是指数，最少可以不变。

2.2 封闭性：三条基本运算推出全部

教材给的封闭性只有三条：并、连接、星号。但考试不会只考这三条，它会问你交、补、差。这时候要会推：补运算靠 DFA 翻转接受状态即可；有了补和并，交就能用德摩根律凑出来；差用交和补凑。这就是为什么“正则语言对补封闭”这句话在证明题里特别值钱——它几乎是一条免费工具。

构造上还有一条更直接的路：两个 DFA 做乘积，状态对是笛卡尔积，接受状态按需要挑。交就挑“两个都接受”，并就挑“至少一个接受”，差就挑“前一个接受后一个不接受”。答题写“乘积构造”四个字，比写一长串德摩根推导更省时间，也更不容易出错。

空集和空串这两条是送分题也是送命题。空集连接到任何集合上还是空集，这是因为连接要求从第一个集合取一个串、第二个集合取一个串拼起来，第一个集合里根本没有串可取。空串连接到任何串上不改变这个串，因为拼接一个长度为 0 的串等于什么都没做。

但 ∅* 等于 {ε}，不是 ∅。星号运算的定义是“零次或多次连接”，零次连接的结果就是空串。这个点在判断题里出现的频率高得离谱，很多人的第一反应是“空集星号还是空集”，直接翻车。

2.3 上下文无关：乔姆斯基范式和下推自动机的互译

上下文无关这一组同样是三张面孔：被上下文无关文法产生、被下推自动机识别、被乔姆斯基范式的文法产生。前两条是“当且仅当”的关系，第三条是“任何一个上下文无关语言都可以用它产生”，语气不一样，答题时不能混着写。

乔姆斯基范式的形式是每条规则要么 A → BC，要么 A → a，除了开始变元可能有一条 S → ε 且 S 不出现在任何规则右部。它的用处不在“看起来整齐”，而在于让判定变得可做：把文法转成范式之后，判断一个长度为 n 的串能不能被产生，可以用自底向上的动态规划，按子串长度从 1 到 n 逐层填表。

这一步推下去就是一条常考结论：每个上下文无关语言都属于 P。很多人在这一题上写“可以用下推自动机模拟”，方向对但不够，标准答法是“转成乔姆斯基范式后用多项式时间的动态规划判定”。

还有一条包含关系必须背清楚：每一个正则语言都是上下文无关的。理由有两条路可走，一是 DFA 本身就是一台忽略栈的下推自动机，二是正则文法本来就是上下文无关文法的特例。答题时任选一条即可，但别写成“因为正则表达式能转成文法所以等价”——那是把包含写成了相等。

顺带记一句区分度最高的话：上下文无关语言对并、连接、星号封闭，但对交不封闭；正则语言对交封闭。这一条差异，正是“正则真包含于上下文无关”的严格性来源。而一个正则语言和一个上下文无关语言求交，结果仍然是上下文无关的——用 DFA 的状态和 PDA 的状态做乘积就能构造出来，这也是常考的构造题。

2.4 四道高频题的答法

第一题：设 L 被某台非确定型有穷自动机识别，问 L 的补是不是正则的。答“是”，但落笔顺序不能乱：先做子集构造确定化，再翻转接受与非接受状态，得到的 DFA 识别补集，最后按等价刻画说明补集是正则的。踩分点在“先确定化”——直接在 NFA 上翻转状态是错的，因为 NFA 的一条路径拒绝不代表整个串被拒绝。

第二题：问 ∅* 是什么。答 {ε}，并把理由压在一句话里：星号包含零次连接，零次连接得到空串。补一句“若写成 ∅ 则混淆了‘没有串’和‘有空串’”。

第三题：问每个上下文无关语言是不是可判定的。答“是，而且属于 P”，给出路径：转乔姆斯基范式，用按子串长度递推的动态规划判定。只写“是”拿不到过程分。

第四题：设 L1 正则、L2 上下文无关，问 L1 ∩ L2 属于哪一类。答“上下文无关”，构造思路是把 L1 的 DFA 状态与 L2 的 PDA 状态做乘积，栈的操作完全交给原来那台 PDA。这一题的陷阱是有人答“正则”，理由是“交了一个正则的进去应该更简单”——方向正好反了，交运算只会让语言变小，不会让它的描述能力降级。

3. 图灵机与可判定性：格局、判定器和一张分三栏的清单

从这一章开始，题目从“构造”转向“证明”。构造题不会做还能画个大概拿步骤分，证明题一旦前提写错，后面全废。图灵机这部分真正要背的东西不多，但每一条都得背准。

3.1 格局与三种结局：循环为什么要单独拎出来

格局是图灵机计算过程中某一瞬间的快照，由三样东西拼成：当前状态、当前带内容、读写头当前的位置。教材里常用的写法是 u q v，意思是带上的内容是 uv，读写头正指着 v 的第一个符号。举个例子，状态 q3、带上内容 10110、读写头指在第四个符号上，格局就写成 101 q3 10。这个记法在后面讲计算历史时是刚需，现在就得练熟。

在输入上运行一台图灵机，结果只有三种：接受、拒绝、循环。这里的关键限定是——循环只指机器不停机，不是指它反复执行同样的步骤。这个区别看着像文字游戏，其实是整门课的分水岭：如果循环等于“重复”，那模拟足够多步就能判断出来；正因为循环只是“还没停”，你永远无法靠观察来区分“进入循环”和“只是跑得很慢”。

格局的总数是有限的：状态数乘以读写头位置数，再乘以带内容的可能数，大致是 |Q| × (n+1) × |Γ|^(n+1)。有限但巨大，这个“有限”在证明线性有穷自动机的判定性时会被反复使用。

3.2 识别器、判定器和三种描述层次

图灵可识别的意思是：存在一台图灵机，对属于该语言的串一律接受。它不保证对不属于的串会停机——可能循环。图灵可判定的意思是：存在一台图灵机，对所有输入都停机，并且接受当且仅当串属于该语言。这样的机器叫判定器。

所以“每一个可判定语言都是图灵可识别的”成立，反过来不成立。这条包含关系是后面所有不可判定性证明的地基，写错一次，后面连环错。

答题时还有个层次问题。描述一台图灵机有三种写法：形式化描述要写清状态集合和转移函数，是最低层、最详细的写法；实现描述用日常语言说清机器怎么移动读写头、怎么改带子；高水平描述同样用日常语言，但完全忽略带子和读写头的管理，只讲算法本身。证明可判定性时用高水平描述就够了，题目明确要求“形式化描述”才需要写到转移函数。很多人栽在这一点上——明明问的是思路，硬写了两页状态转移表，时间全花在这道小题上。

还有三条等价性要背：每一台多带图灵机等价于一台单带图灵机；每一台非确定型图灵机等价于一台确定型图灵机；一个语言是图灵可识别的，当且仅当存在非确定型图灵机识别它。等价成立不代表代价相同，代价在复杂度那一章会变成平方和指数，现在先记住“等价”两个字。

最后一条常被当作填空题：丘奇-图灵论题给出的是算法的明确定义。它不是一个能被证明的定理，而是一个论题——凡是直觉上可计算的，都能用图灵机算。

3.3 一张分三栏的清单

这张清单是整门课最值得反复过的东西。它只有三栏：可判定、不可判定、连识别都做不到。

记忆线索只有一条：问题里只要出现“给定一台具体的自动机或文法，问它接不接受某个串 / 是不是空的”，绝大多数能靠模拟加有限搜索判掉；一旦问题里出现“任意一台图灵机”“所有串”“两台图灵机是否等价”，基本就掉进不可判定。PCP 是唯一的例外，它压根不是关于机器的，而是关于一个拼接游戏有没有解——这条单独记。

还有两条收尾的结论要抄在清单底下。第一，一个语言是可判定的，当且仅当它既是图灵可识别的，也是补图灵可识别的。第二，EQ_TM 既不是图灵可识别的，也不是补图灵可识别的；而 A_TM 的补是不可识别的。这两句话在选择题里出现的频率极高，且只考记忆，不考推导。

3.4 A_TM 不可判定的证明怎么写才拿满

这道题的证明步骤是固定的，写不全就扣分。第一步，假设存在判定器 H，它在输入 ⟨M, w⟩ 上判断 M 是否接受 w，接受则 H 接受，拒绝则 H 拒绝。第二步，用 H 构造一台新机器 D：D 在输入 ⟨M⟩ 上，对 ⟨M, ⟨M⟩⟩ 运行 H。第三步，让 D 的结论与 H 相反——H 接受时 D 拒绝，H 拒绝时 D 接受。第四步，把 D 自己喂给 D，得到 D 接受 ⟨D⟩ 当且仅当 D 不接受 ⟨D⟩，矛盾。第五步，结论是 H 不存在。

踩分点有三个。一是必须写成 ⟨M, ⟨M⟩⟩，也就是把机器自己的描述同时当作程序和输入，这是“对角”的来源，漏了这一步整个证明就退化成普通模拟。二是矛盾必须落在“D 对 ⟨D⟩ 的判断与 H 的判断相反”上，不能含糊地说“产生矛盾”。三是最后一句要明确否定假设，很多人写到矛盾就停笔，扣一个结论分。

紧接着常考的下一问是从 A_TM 归约到 HALT_TM。构造思路是：给定 ⟨M, w⟩，造一台新机器 M′，M′ 在输入上模拟 M，M 接受则 M′ 接受，M 拒绝则 M′ 进入循环。于是 M 接受 w 当且仅当 M′ 在 w 上停机。这个构造的意义在于把“接受性”换成了“停机性”，写出这一句，归约的正反方向就都立住了。

4. 归约与复杂度：从 ≤m 到 P/NP/PSPACE 的两级台阶

归约是这门课唯一一件“工具型”的知识。它不产生新结论，但它把已知的结论搬到新问题上。复杂度那一半则是把“能不能算”换成“要算多久”，两件事共用一套归约语言。

4.1 映射归约：定义只有一句话，方向却年年写反

用映射可归约性把问题 A 归约为问题 B，意思是存在一个可计算函数，把 A 的实例转换成 B 的实例，于是有了 B 的解法就能解 A。形式化一点：存在可计算函数 f，使得对每个 w，w ∈ A 当且仅当 f(w) ∈ B，记作 A ≤m B，f 称为 A 到 B 的归约。

可计算函数的定义要单独背：存在一台图灵机 M，在每个输入 w 上都停机，且停机时带上恰好是 f(w)。注意“都停机”这三个字，它排除了那些跑着跑着卡住的转换函数。

真正决定分数的是两条定理的用法。第一条：如果 A ≤m B 且 A 是不可判定的，则 B 也是不可判定的。第二条：如果 A ≤m B 且 B 是图灵可识别的，则 A 也是图灵可识别的。

题目的问法永远是“证明 B 不可判定”，而定理说的是“从 A 不可判定推出 B 不可判定”。所以动作只能是：找一个已知不可判定的 A，构造 A 到 B 的归约。方向写反的人，等于在证明一个已知结论的逆命题，而这个逆命题根本不成立。

口头记法就一句：把已知难的问题往里塞，塞给要证难的那个。想证 HALT_TM 不可判定，就拿 A_TM 往它身上归约；想证 EQ_TM 不可判定，就构造两台机器，其中一台的行为依赖某台机器在某个串上是否接受，让“等价”这个判断等价于“接受”这个判断。

还有一条高级用法：要证某个语言既不可识别也不补可识别，得两头夹。先用一个方向证它不可识别，再用另一个方向补图灵可识别的定理证它的补也不可识别。EQ_TM 就是这么被拿下的，这种题在卷面上属于压轴。

4.2 计算历史：为什么“有限”两个字这么值钱

设 M 是一台图灵机，w 是一个串。M 在 w 上的接受计算历史是一个格局序列 C1、C2……Cl，其中 C1 是起始格局，Cl 是接受格局，每个 Ci 都是 Ci−1 一步之后的结果。把“接受格局”换成“拒绝格局”，就得到拒绝计算历史的定义。

两个性质必须记牢。第一，计算历史都是有限序列。第二，如果 M 在 w 上永不停机，那么既不存在接受历史，也不存在拒绝历史。这两句话合起来，正好把“不停机”这件事翻译成了“历史不存在”，而“历史不存在”是可以搜索的。

第三，确定型机器在任何给定输入上最多只有一个计算历史；非确定型机器即使在单个输入上也可能有多个，它们对应各个分支。这一条在做非确定型机器的证明时经常被引用。

用途上最典型的是线性有穷自动机。它是一台受限制的图灵机，读写头不允许离开包含输入的那段带子，试图越界就原地不动。带子受限意味着格局数有限，于是：如果它接受某个串，一定存在一条长度不超过格局总数的接受计算历史；把所有可能的格局序列按长度穷举一遍，就能判定。这就是 A_LBA 可判定的底层理由，也是“有限”两个字最值钱的一次出场。

4.3 时间、空间与那条包含链

时间复杂性类 TIME(t(n)) 的定义是：能被 O(t(n)) 时间的图灵机判定的所有语言的集合。空间复杂性类 SPACE(f(n)) 和 NSPACE(f(n)) 同理，只是把时间换成空间，确定型和非确定型分开写。

两条换算要分清，这是本课程最典型的数字陷阱。一是多带换单带：对 t(n) ≥ n，每一台多带图灵机都和某一台 O(t²(n)) 时间的单带图灵机等价，代价是平方。二是非确定换确定：每一台 t(n) 时间的非确定型单带图灵机，都与某一台 2^O(t(n)) 时间的确定型单带图灵机等价，代价是指数。很多人把这两条记混，写成“非确定换确定是平方”，一错就是两道题。

P 类是在多项式时间内可判定的语言类。已知属于 P 的有 PATH、RELPRIME，以及每一个上下文无关语言。NP 类的等价刻画是：一个语言在 NP 中，当且仅当它能被某台非确定型多项式时间的图灵机判定。更实用的说法是，P 是成员可以快速判定的语言类，NP 是成员可以快速验证的语言类——给一个证书，多项式时间验完即可。

属于 NP 的常考问题有 HAMPATH、CLIQUE、SUBSET-SUM、SAT、3SAT、UHAMPATH，这张名单要背。多项式时间归约记作 A ≤p B，要求那个转换函数是多项式时间可计算的。3SAT 多项式时间可归约到 CLIQUE，这条归约本身常被当作大题考。库克-列文定理的写法是：SAT 是 NP 完全的，SAT 属于 P 当且仅当 P = NP。

空间这一侧的核心是萨维奇定理：对任何 f(n) ≥ n，NSPACE(f(n)) ⊆ SPACE(f²(n))。把 f 取成多项式，立刻得到 PSPACE = NPSPACE。这条推导是标准考点，答题时要把“取 f 为多项式”这一步显式写出来。PSPACE 完全的代表是 TQBF、FORMULA-GAME、GG；NL 完全的代表是 PATH。

对数空间可归约要单独说一句：对数空间转换器是一条只读输入带、一条只写输出带、一条 O(log n) 个符号的读写工作带，它计算的函数叫对数空间可计算函数。若存在这样的函数把 A 映射归约到 B，记作 A ≤L B。传递性在这里同样成立：若 A ≤L B 且 B ∈ L，则 A ∈ L。更进一步的结论是，若有一个 NL 完全语言属于 L，则 L = NL。

最终的层级链只有一行，必须默写：L ⊆ NL ⊆ P ⊆ NP ⊆ PSPACE = NPSPACE。

4.4 3SAT 归约到 CLIQUE 的写法

题目要求证明 3SAT ≤p CLIQUE 时，四步缺一不可。第一步，构造：给定一个含 k 个子句的 3SAT 实例，为每个子句画三个顶点，同一子句内的三个顶点两两相连成三角形；不同子句的顶点之间，只有当两个文字不是互补关系时才连边。第二步，正方向：若公式可满足，每个子句至少有一个文字为真，从每个三角形里挑一个为真的文字，它们之间两两不互补，所以彼此相连，构成大小为 k 的团。第三步，反方向：若图中有大小为 k 的团，由于团在同一个三角形内最多取一个顶点，必然每个子句恰好取一个，把这 k 个文字赋真，互补的文字不会同时被选中，所以赋值合法且满足所有子句。第四步，说明构造在多项式时间内完成。

第四步最常被漏掉，而它恰恰是“多项式时间归约”这五个字里唯一的得分点。归约证明写完构造和两个方向，只算证了一半。

5. 易错点：五个年年有人翻车的判断题

这一节挑的都是“看着像送分、实际年年有人错”的题。每一条都按“错在哪、为什么错、怎么答对”写，对着自己的错题本核一遍。

5.1 五个高频翻车点

第一，把归约方向写反。错在把“要证不可判定的 B”归约到“已知不可判定的 A”。原因在于把 ≤m 读成了“难度不小于”，而它表达的是“A 不比 B 难”。答对的写法是固定动作：先写“下面构造从 A 到 B 的归约”，再写转换函数，最后引用那条“A ≤m B 且 A 不可判定则 B 不可判定”。

第二，拿 A_TM 去证某个语言不可识别。错在把“不可判定”和“不可识别”当成一回事。A_TM 本身是图灵可识别的，用它只能证明不可判定性；要证不可识别，得用 A_TM 的补，或者做两头夹。答对的关键是先想清楚目标结论属于哪一栏，再选归约的源头。

第三，把 ∅ 和 {ε} 混着用。错在写封闭性构造时把 ∅ 当成“含空串的集合”。区别在于：∅ 里一个串都没有，{ε} 里有一个长度为 0 的串。连带出的高频错法是 ∅* = ∅，正确结果是 {ε}。答对只需一句话：星号含零次连接，零次连接得空串。

第四，用“模拟了很多步还没停”来判定循环。错在把工程直觉当成了判定过程。原因是停机问题不可判定，不存在一个通用程序能区分“进入循环”和“只是跑得慢”。答对的表述是：判定器要求对所有输入停机，因此只能靠结构性论证——比如格局数有限——而不能靠观察运行时长。

第五，复杂度换算记反。

本文还有配套的精品资源，点击获取