简介：围绕计算理论期末复习整理的知识点文档，面向哈尔滨工程大学等高校修读计算理论、自动机与形式语言课程的学生，帮助在考前快速梳理概念、定理与判定结论。全包仅 1 个 docx 文件，约 18KB，按自动机理论、图灵机、语言理论、计算复杂度及其他概念五个板块顺序编排，篇幅精炼，便于打印或移动端反复背诵。内容以条目式结论为主：正则语言与有穷自动机、下推自动机与上下文无关语言的对应关系，格局、图灵可识别与图灵可判定、判定器与丘奇-图灵论题，以及可判定性、映射归约、线性有穷自动机、时间与空间复杂性类 P、NP、SAT 与 3SAT 归约等常考判断。适合需要把零散笔记压缩成背诵清单、考前查漏补缺的读者。目前已有 551 人学习。

1. 计算理论期末复习的难点在哪里：背结论和背等价链的差别

计算理论期末的复习，最容易出问题的地方就是把一份计算理论知识点从头背到尾，卷子发下来照样在判断题上卡住。这门课真正考的是你能不能把一张等价关系网理清楚：正则语言对应哪类机器、上下文无关语言对应哪类机器、可判定与可识别差的究竟是“停机”还是“辨别能力”。只做知识点背诵而不理结构，背十遍还是会混。下面按考点模块拆开：先给等价链和清单，再给高频真题的答题思路，最后落到易错点和临场模板。适合已经把教材过了一遍、做题仍然靠感觉的人，也适合临考前只想要一份能直接背的清单的人。

2. 正则语言与有穷自动机：四个等价命题、封闭性与泵引理

2.1 正则语言的四类描述：DFA、NFA、正则表达式与封闭性

教材开篇的几条结论其实在说同一件事：一个语言被有穷自动机识别，它就是正则语言；每一台非确定有穷自动机都等价于一台确定型有穷自动机；一个语言是正则的当且仅当有一台 NFA 识别它；一个语言是正则的当且仅当有一个正则表达式描述它。把这四句压成一句话就是：DFA、NFA、正则表达式、右线性文法，是同一个语言类的四种描述方式，考试让你做的就是在这四种描述之间来回翻译。

DFA 是五元组 (Q, Σ, δ, q₀, F)，转移函数是 δ: Q×Σ→Q，一个输入串走一条唯一路径，走到接受状态就接受；NFA 把转移函数放宽成 δ: Q×Σ_ε→P(Q)，一个输入可以同时走多条路径，只要有一条走到接受状态就算接受。两者识别能力相同，但描述便利性差很多——写一个“倒数第三个字符是 1”的 DFA 要列出八个状态，写 NFA 只要四五个状态。这也是为什么考题总爱让你先把 NFA 画出来再转成 DFA。

封闭性这一块，标准答案是三句话：正则语言在并运算、连结运算、星号运算下封闭。阅卷人最想看到的是你能顺手把证明思路说出来——并运算靠新建初态用 ε 边同时指向两台 NFA 的初态，连结靠把前者接受状态用 ε 边接到后者初态，星号靠加一个新初态兼接受状态并允许回到原初态。多数人只背结论不背构造，一到大题就写不下去。

顺着这三条还能推出几条更好用的：正则语言对补运算封闭（把 DFA 的接受状态与非接受状态对调即可，注意必须是 DFA，NFA 直接翻转会错），对交运算封闭（用乘积构造，或写成 A∩B = (Aᶜ∪Bᶜ)ᶜ），对反转封闭（把 NFA 所有边反向、初态与接受状态角色互换）。这几条在判断题里出现的频率比三大运算还高，因为出题人喜欢设“正则语言对补封闭吗”这种看起来超纲、其实一步就能证的陷阱。

2.2 泵引理：证明“不是正则”的标准四步

泵引理的用途只有一个方向：证明某个语言不是正则语言。它不能用来证明一个语言是正则的，这是最容易被误用的一点。

标准写法是四步。第一步，假设 L 是正则的，于是存在泵长度 p。第二步，构造一个依赖 p 的串 s ∈ L，并且 |s| ≥ p，这个串要让后面无论怎么切都露馅。第三步，任取分解 s = xyz，只要满足 |xy| ≤ p 且 |y| > 0，说明你考虑到了所有合法切法，这一步的关键词是“任取”而不是“存在”。第四步，找到一个 i ≥ 0 使得 xyⁱz ∉ L，与泵引理矛盾，从而 L 不是正则的。

以经典的 L = {0ⁿ1ⁿ | n ≥ 0} 为例。假设正则，取 s = 0ᵖ1ᵖ。由于 |xy| ≤ p，y 只能落在前 p 个字符里，也就是 y 全是 0，设 |y| = k > 0。那么取 i = 2 得 xy²z = 0^{p+k}1^p，0 和 1 的个数不再相等，不在 L 中，矛盾。整个证明的骨架不到十行。

这类题通常这么答：先写“假设 L 正则，取泵长度 p”，再写“取 s = …”，再写“对任意满足条件的分解 s = xyz”，最后写“取 i = …，得 …∉ L，矛盾”。四个环节缺一个就扣分，尤其是漏掉 |xy| ≤ p 这个约束条件——它决定了 y 只能出现在串的前段，这是整个证明能成立的唯一支点。

选串也有讲究。证明 {ww | w ∈ {0,1}*} 不是正则，取 s = 0ᵖ1 0ᵖ1 比取 0ᵖ0ᵖ 好用，因为前者逼迫 y 只能落在最前面那段 0 里。选串的原则是：让所有可能的 y 位置导出的结果都不在 L 内，而不是只挑一种位置验证。

2.3 真题演练：子集构造与状态消除法的答题顺序

第一类必考大题是 NFA 转 DFA。做法是子集构造：DFA 的每个状态是 NFA 状态集合的一个子集，初态是 NFA 初态的 ε 闭包，对每个子集和每个输入符号求转移后再取 ε 闭包，直到没有新子集产生。答题时把转移表画出来最稳，横轴是输入符号，纵轴是子集，一格一格填。

假设某 NFA 有状态 {1,2,3}，初态 1，接受状态 2，转移为 1 在 a 上到 {1,2}，2 在 b 上到 {3}，3 在 a 上到 {2}，没有 ε 边。子集构造的结果是：

表的读法要注意两点：第一，只要子集里含有原来的接受状态 2，这个 DFA 状态就是接受状态；第二，空集状态要不要画出来取决于题目要求，写“完全 DFA”就必须画，写“接受同样语言的 DFA”可以不画。很多人在这一步把 ∅ 状态漏掉，导致转移函数不是全函数，被扣细节分。

第二类是正则表达式与自动机互推。表达式转 NFA 有 Thompson 构造，NFA 转表达式用状态消除法（GNFA）：加一个统一的新初态和新接受状态，二者之间用 ε 边连上，然后每次消掉一个中间状态 k，对所有经过 k 的路径把转移更新为 R_ij ∪ R_ik R_kk* R_kj，直到只剩初态和接受状态之间的一条边，那条边上的表达式就是答案。更新公式里 R_kk* 那一项是星号闭包，最容易写漏。

3. 图灵机与可判定性：格局、运行结果与判定器清单

3.1 格局与三种运行结果：描述算法的三个层次

图灵机的格局（configuration）是三个东西的组合：当前状态、当前带内容、读写头当前的位置。它相当于计算过程的一张快照，两台图灵机之间证明“模拟”关系时，本质就是在格局序列上做归纳。

在输入上运行一台图灵机，只可能出现三种结果：接受、拒绝、循环。这里的循环专指机器不停机，不是指它反复执行同样的步骤——很多判断题就咬住这个字眼，把“进入死循环”和“反复做同一步”混在一起设套。由此引出判定器：所有输入上都停机的图灵机，它永远不循环，总能给出接受或拒绝的答案。一个语言能被某台图灵机识别，就叫图灵可识别（递归可枚举）；能被某台图灵机判定，就叫图灵可判定（递归）。每个可判定语言都是图灵可识别的，反之不成立，这个方向不能反。

描述图灵机算法分三个层次：最底层是形式化描述，把所有状态、转移函数、带字母表全部写出来，一个字都不能省；中间层是实现描述，用日常语言说清读写头怎么移动、带子怎么改，但不列状态表；最高层是高水平描述，连读写头怎么管带子都不提，只说“把输入读入内存、比较两段”这类话。考试里让你“描述一台图灵机”通常是接受高水平描述的，但题干一旦出现“形式化描述”四个字，就必须老老实实写转移表。

3.2 真题演练：可判定、不可判定、不可识别清单的分类默写

这张清单是整门课性价比最高的记忆内容，几乎每套卷子都有判断题出自这里。

默写时有三个高频混淆点。第一，A_LBA 是可判定的，靠的是“如果 LBA 接受某个串，就存在一条长度不超过 状态数 × 带符号数^(输入长度) 的接受计算历史”，格局总数有限所以可以穷举；但 E_LBA 不可判定，两者不在同一档。第二，A_TM 图灵可识别但不可判定，通用图灵机模拟它就能识别，可一旦被模拟的机器循环，模拟者也跟着循环，所以拿不到判定器。第三，EQ_TM 既不是图灵可识别的也不是补图灵可识别的，这是最“黑”的一条，判断题里出现基本就是拿它当正确答案。

3.3 补图灵可识别：判定性的双向等价怎么证

一个语言的补是由不在此语言中的所有串构成的语言。如果某个语言的补集是图灵可识别的，就称这个语言是补图灵可识别的。核心定理只有一句：一个语言是可判定的，当且仅当它既是图灵可识别的，也是补图灵可识别的。

正方向好证：如果 L 可判定，那么有判定器 M，把 M 的接受拒绝状态对调就得到判定 Lᶜ 的判定器，所以 L 和 Lᶜ 都可判定，自然都可识别。反方向是重点：设 M₁ 识别 L，M₂ 识别 Lᶜ，构造判定器 M，在输入 w 上并行跑 M₁ 和 M₂（用多带模拟交替执行一步），因为 w 要么在 L 要么在 Lᶜ，两台机器必有一台最终接受，哪台先接受就按哪台给答案。这个“并行模拟”的技巧是整道题的得分点，写不出并行，就等于没证。

这条定理最常见的用法是反证：已知 A_TM 图灵可识别但不可判定，如果它的补也图灵可识别，那 A_TM 就可判定了，矛盾，所以 A_TM 的补不是图灵可识别的。同理，一个语言如果既不可判定、其补又不可识别，那它连“可识别”都算不上。

4. 归约与复杂度：从映射可归约到 NP 完全与 PSPACE

4.1 映射可归约：方向、传递性与三条常用推论

用映射可归约把问题 A 归约到问题 B，意思是存在一个可计算函数 f，把 A 的实例转换成 B 的实例，使得 w ∈ A 当且仅当 f(w) ∈ B，记作 A ≤m B。函数 f 可计算的定义是：存在一台图灵机 M，在每个输入 w 上都停机，且停机时带上恰好是 f(w)。

方向感是这一章最要命的东西。A ≤m B 的直观含义是“B 至少和 A 一样难”，也就是把 A 的问题搬到 B 上去解决。所以三条推论要背成条件反射：

• 如果 A ≤m B 且 A 是不可判定的，则 B 也是不可判定的（难的问题能归约到它，它不可能简单）。
• 如果 A ≤m B 且 B 是可判定的，则 A 也是可判定的（用 B 的判定器加转换函数就能判定 A）。
• 如果 A ≤m B 且 B 是图灵可识别的，则 A 也是图灵可识别的。

注意第二、三条是同一个方向的两种说法——“B 简单则 A 简单”，而第一、二条合起来才能做不可判定性证明：想证 B 不可判定，要找一个已知不可判定的 A，构造 A ≤m B。很多人在这里把箭头写反，用“B 不可判定推出 A 不可判定”，整道大题直接零分。

4.2 真题演练：A_TM 归约到 HALT_TM 的完整写法

目标是证明停机问题 HALT_TM 不可判定。按归约的思路，要构造 A_TM ≤m HALT_TM，也就是给定 ⟨M, w⟩ 能算出一个图灵机描述 ⟨M′, w⟩，使得 M 接受 w 当且仅当 M′ 在 w 上停机。

构造是这样的：M′ 在输入 w 上先模拟 M 的运行过程，如果 M 接受 w，M′ 就接受并停机；如果 M 拒绝 w，M′ 就故意进入一个不停机的循环。这个描述只用高水平语言写就够，不需要列状态表。

接着证等价性。若 ⟨M, w⟩ ∈ A_TM，M 接受 w，M′ 模拟到接受后停机，所以 ⟨M′, w⟩ ∈ HALT_TM；若 ⟨M, w⟩ ∉ A_TM，M 不接受 w（拒绝或循环），M′ 要么进入循环要么模拟中本身就循环，总之不停机，所以 ⟨M′, w⟩ ∉ HALT_TM。两个方向都成立，归约有效。

最后收尾：假设 HALT_TM 可判定，有判定器 R，那么构造 S：在输入 ⟨M, w⟩ 上先算 f(⟨M, w⟩) = ⟨M′, w⟩，再跑 R 给出答案，就得到 A_TM 的判定器，与 A_TM 不可判定矛盾。所以 HALT_TM 不可判定。

这道题的评分点是分段的：构造 f 占一部分，双向等价性占一部分，反证收尾占一部分。只写“假设可判定，推出 A_TM 可判定，矛盾”而不写 f 长什么样，最多拿三分之一的分数。

4.3 时间与空间复杂性类：多带换单带为什么多了个平方

时间复杂性类 TIME(t(n)) 定义为能被 O(t(n)) 时间的图灵机判定的所有语言的集合。两条模拟定理是必背的：每个多带图灵机都与某台 O(t²(n)) 时间的单带图灵机等价；每个 t(n) 时间的非确定型单带图灵机都与某台 2^O(t(n)) 时间的确定型单带图灵机等价。

第一条的平方从哪来，是最容易被追问的细节。单带图灵机模拟 k 带图灵机时，把所有带的内容按“带符号 + 虚拟读写头标记”的形式压缩到一条带上，每模拟一步，都要把读写头来回扫过整段有效带内容去收集 k 个虚拟读写头下的符号，这段距离是 O(t(n))，模拟 t(n) 步就是 O(t²(n))。答题时把这句“每步扫带子，扫 t 步”讲出来，比只写结论强得多。

第二条的指数从哪来：非确定型机器每一步有常数个分支，t(n) 步最多产生 b^{t(n)} 条分支，确定型机器用宽度优先搜索遍历这棵计算树，所以是 2^O(t(n))。至于空间，萨维奇定理给出 NSPACE(f(n)) ⊆ SPACE(f²(n))，其中 f(n) ≥ n，靠的是可达性问题的空间高效算法，把“是否存在长度不超过 2^{O(f(n))} 的路径”压到 O(f²(n)) 空间里判。

基于这些定义，P 是多项式时间可判定的语言类，NP 是非确定型多项式时间可判定的语言类。P = NP 之外的等价刻画要会背两句：P 是成员可以快速判定的语言类，NP 是成员可以快速验证的语言类。PATH、RELPRIME 属于 P，每个上下文无关语言也属于 P；HAMPATH、CLIQUE、SUBSET-SUM、SAT、3SAT、UHAMPATH 都属于 NP。

4.4 真题演练：SAT 到 3SAT 再到 CLIQUE 的归约链

多项式时间映射可归约 A ≤p B 的定义与映射可归约结构相同，只多一个要求：转换函数 f 必须多项式时间可计算。列文-库克定理给出 SAT 是 NP 完全的，也就是 SAT ∈ NP 且所有 NP 语言都多项式时间归约到它。围绕这条定理，整条链是 SAT → 3SAT → CLIQUE。

SAT 到 3SAT 的做法是把每个子句拆成三段，用辅助变量把长短不一的子句补齐成恰好三个文字，这一步的构造关键在“子句长度小于 3 时补什么”“大于 3 时怎么切分并加新变量”，写的时候按子句长度分类讨论，把每种情况的等可满足性说清楚。

3SAT 到 CLIQUE 的构造更常考：设公式 φ 有 k 个子句，为每个子句的三个文字各建一个顶点，得到 3k 个顶点；两个顶点之间连边，当且仅当它们来自不同子句且不是互补文字（不是 x 与 ¬x）。于是 φ 可满足当且仅当这张图有 k-团。证明也是双向：可满足赋值给每个子句挑一个真文字，这 k 个顶点两两来自不同子句、互不冲突，构成 k-团；反过来一个 k-团只能从每个子句各取一个顶点，给这些顶点对应的文字赋真，就能满足所有子句。

这条链的答题要点是构造和等价性证明分开写，先写“给定 φ，构造图 G 如下”，再写“下面证明 φ 可满足当且仅当 G 有 k-团”，中间那条“不同子句且非互补”的连边规则是唯一容易写错的地方，写漏了“非互补”，整道题就废了。

5. 易错点：判断题和大题里最容易失分的五个地方

5.1 把“识别”当“判定”用

错在哪：看到“图灵可识别”就默认它可判定，或者反过来，认为可判定语言不一定是可识别的。为什么错：识别只要求“接受时停机”，拒绝和循环都不管；判定要求“所有输入都停机”。两者差了一个停机保证，而这个保证正是整门课一半定理的来源。怎么答对：做题时先问自己一句“这台机器在不在语言里的输入上都会停吗”，答不上来就不是判定器；写结论时严格区分“存在图灵机识别它”和“存在判定器判定它”，别用一个“可计算”糊过去。

5.2 归约方向写反

错在哪：想证明 B 不可判定，却构造了 B ≤m A 而不是 A ≤m B。为什么错：归约的直观是“把问题搬到另一个问题上解决”，A ≤m B 意味着 B 至少和 A 一样难；写成 B ≤m A 只能说明 A 比 B 难，推不出 B 不可判定。怎么答对：下笔前先写一行“已知 A 不可判定，要证 B 不可判定，所以需要 A ≤m B”，把方向钉死在纸上，再开始构造 f。凡是结论是“B 不可判定”的题，f 的输入一定取自那个已知不可判定的问题。

5.3 拿泵引理去证“是正则”

错在哪：题目要求判断某语言是否正则，考生用泵引理“验证”它满足泵性质，就下结论说它是正则的。为什么错：泵引理是正则语言的必要条件，不是充分条件，满足泵性质的语言也可能是非正则的。怎么答对：要证是正则，只能给出构造——画 DFA、写正则表达式、写右线性文法，三者任一即可；要证不是正则，才用泵引理反证。判断题型里先想“能不能构造”，构造不出来再上泵引理，别一上来就泵。

5.4 复杂度包含关系写成等号或反号

错在哪：把 L、NL、P、NP、PSPACE 之间的包含写成相等，或者把萨维奇定理写成 SPACE(f(n)) ⊆ NSPACE(f²(n))。为什么错：确定型类包含于对应的非确定型类，同一层次的确定类包含于上一层；萨维奇定理说的是非确定空间类被确定空间类以平方代价包含，方向是 NSPACE → SPACE。怎么答对：默写时按链条背“L ⊆ NL ⊆ P ⊆ NP ⊆ PSPACE = NPSPACE”，配合两个标志性结论记：PATH 是 NL 完全的，TQBF 是 PSPACE 完全的；再记住 NL = coNL 这个少见的等号。

5.5 把 SAT ∈ P 说成列文-库克定理的内容

错在哪：判断题写“列文-库克定理表明 SAT ∈ P，当且仅当 P = NP”，把定理内容和推论搅在一起。为什么错：列文-库克定理给出的是 SAT 的 NP 完全性——SAT ∈ NP 且所有 NP 语言多项式时间归约到 SAT；而“SAT ∈ P 当且仅当 P = NP”是由完全性直接推出的推论，两者不是一个层次。怎么答对：看到“列文-库克”就写“SAT 是 NP 完全的”，看到“SAT ∈ P 当且仅当 P = NP”就写“这是完全性的推论”，答题时分两句话写，别合并成一句，合并了容易被判为概念混淆。

6. 答题技巧：三张模板把该拿的分数固定下来

临场时间有限，计算理论这门课的大题其实高度套路化，带三张模板进考场就够了。

第一张是等价链默写模板。开考前先在草稿纸角上写两行：正则 = DFA = NFA = 正则表达式，上下文无关 = 下推自动机 = 乔姆斯基范式文法，可判定 ⊆ 图灵可识别，L ⊆ NL ⊆ P ⊆ NP ⊆ PSPACE = NPSPACE。凡是判断题拿不准，就往这两行上靠，看它问的是同一层内的等价，还是跨层的包含。

第二张是归约五步。第一步写“要证 B 不可判定，取已知不可判定的 A，构造 A ≤m B”；第二步写转换函数 f 在输入上的运行方式，用高水平描述；第三步写“若 x ∈ A 则 f(x) ∈ B”和“若 x ∉ A 则 f(x) ∉ B”两个方向；第四步写“f 可计算，因为它在所有输入上停机”；第五步写反证收尾“若 B 可判定，则 A 可判定，矛盾”。五步齐了，分数基本就稳。

第三张是不可判定性清单模板，也就是第 3 章那张表。考前十分钟只背这张表，重点记 A_LBA 可判定、E_LBA 不可判定、A_TM 可识别不可判定、EQ_TM 两头都不可识别，四个点各占一行。

血泪经验是：这类卷子最后一道证明题往往不是不会，而是时间不够导致只写了结论没写构造。我从那次在归约题上只写了“矛盾，故不可判定”却漏掉转换函数之后，每次模考都强制自己先把五步骨架的五个小标题列在答题纸上，再往回填内容——哪怕填得粗糙，骨架在就有过程分。希望帮到你。

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