企业官网建设流程全解析

简介：这份《计算理论知识点》文档专为哈尔滨工程大学计算理论期末复习打造，系统梳理自动机理论、图灵机、语言理论与计算复杂度等核心模块，覆盖正则语言、上下文无关语言、图灵可判定性、映射可归约等高频考点，适合考前突击背诵与理解性记忆。资料仅含1个docx文件，约18KB，以知识点清单、关键结论和可判定/不可判定问题对照表的形式组织，无需解压即可快速查阅打印。已有549人学习下载，受到本校及相关课程学生认可。文档不仅给出“有穷自动机识别正则语言”“非确定型与确定型自动机等价”“图灵可判定与可识别”等基础结论，还细化了格局、计算历史、判定器、线性有穷自动机等难点概念，并对ADFA、ATM、停机问题、EQTM等经典判定与不可判定问题做了清晰辨析；同时引入多项式时间归约、P与NP、SAT与3SAT等复杂度理论内容，可帮助读者快速建立完整知识框架，应对期末考试中的选择、简答与证明题。

1. 计算理论期末复习背什么：这份知识点文档把答案串成了一条线

哈工程的《计算理论》期末，很多人挂在同一个地方：上课听懂了，题不会做；题会做了，概念又背串。这门课跟高数不一样，它的核心不是推导，而是先建立起一张“哪些问题能判定、哪些不能判定、归约往哪个方向走”的全局地图，而这张图只能靠背。这份《计算理论知识点.docx》就是干这个用的：它把自动机、图灵机、可判定性、P/NP/PSPACE 这些章节的核心结论按条目收在一起，没有推导过程，全是期末考试可以直接引用的命题。适合两类人：刚学完想快速过一遍的，和考前两三天需要把知识点钉死的。文档后半段编号从 1 重新开始，是原排版问题，内容本身按主题走，不影响背。

2. 自动机与语言层级：从 DFA 到 PDA，先分清谁识别谁

2.1 一张表背熟四台机器与三层语言

这份文档前 11 条，本质就是在回答一个问题：语言、文法、机器三者怎么对应。很多判断题的错误答案，都出在把“谁产生语言”和“谁识别语言”搞反。我一般建议先把下面这张表背到能默写，再去看文档里那些文字表述。

这张表的记忆顺序是“能力递增”：DFA 只有有限状态，PDA 多一个栈，图灵机有无限带。所以文档里那句“每一个正则语言都是上下文无关的”才是对的，反过来说“每个上下文无关语言都是正则的”就错了。我当年期末翻车就翻在这：只背结论不看方向，结果判断题里一个“正则语言都是上下文无关的”的逆命题，直接把分送掉。

判断一个语言是不是正则，常见的反例是 {0ⁿ1ⁿ | n≥0}：它有穷自动机数不清 0 的个数，但 PDA 可以用栈记住，所以它是上下文无关的、但不是正则的。这类反例文档里没写，但简答题一旦要你解释“为什么正则语言是上下文无关的真子集”，它就是标准答案。

2.2 封闭性：并、连结、星号，以及空集和空串的边界

文档第 2 条说了正则语言在并、连结、星号三种运算下封闭。这条的价值在期末，不是让你背“封闭”两个字，而是让你在构造题里合法“偷懒”：要证明一个语言正则，可以把它拆成几个已知正则的语言，再做并/连结/星号组合，不用每次都从 DFA 开始构造。比如证明“所有含偶数个 0 或奇数个 1 的串”正则，拆成两个 DFA 的语言做并集就行。

真正容易翻车的是文档第 5 条那两句话：“空集连接到任何集合上得到空集，空串连接到任何一个串上不改变这个字符串”。这里考的是集合运算和串运算的边界。

∅ 连接 L，结果是 ∅，因为 ∅ 里没有任何串可以拿出来和 L 里的串拼接；而 ε 连接一个串 s，结果是 s 本身，因为 ε 是长度为零的串。很多人把这两条背成“空集是连接的幺元”，那就反了。还有一个文档没写但期末经常跟出来的推论：∅* 等于 {ε}，不是 ∅。根据星号定义，L⁰ = {ε}，空集也不例外。我复习时会把这三条捆在一起背：∅∘L = ∅，{ε}∘L = L，∅* = {ε}，考前默写一遍，五分钟的事，能挡住一道选择或填空。

2.3 NFA 与 DFA 等价：为什么它是正则语言的定海神针

文档第 3、4 条说的是同一件事：每一台 NFA 都等价于某台 DFA；一个语言是正则的，当且仅当存在一台 NFA 识别它。这里“当且仅当”四个字是重点，它意味着在写证明的时候，你可以随时把语言从“被 DFA 识别”切换成“被 NFA 识别”，不用每次重新构造机器。

NFA 比 DFA 多了一个“非确定性”：一个状态下读同一个符号，可能有好几条路可以走。直观理解是它“猜”下一步，但只要有“一条路”能走到接受状态，输入就算被接受。DFA 模拟 NFA 的经典做法是子集构造法——把 NFA 的当前状态集合当成 DFA 的“一个状态”，这样 DFA 的状态数是 NFA 的指数级，但一定是有限的。

期末考到这条，常见出法是给你一个 NFA，让你说明它能被 DFA 识别，或反过来。答题套路很简单：先写“根据子集构造法，任意 NFA 都能转化为等价的 DFA”，再补一句“因此该语言正则”。不要试图现场把子集构造的证明写一遍，判卷老师要的是你会用结论，不是默写定理。同一章里“一个语言是正则的当且仅当有一个正则表达式描述”也是同样用法：正则表达式、DFA、NFA 三者可以互相转换，这个等价链是整个正则语言章节的骨架。

3. 图灵机与可判定性：格局、描述层次与“循环也是不接受”

3.1 格局与计算历史：把一次运行变成一串快照

文档从“1.——格局”开始进入图灵机部分，这里编号重新从 1 起，但内容上是接着自动机往更高级的模型走。格局的定义是三要素：当前状态、当前带内容、读写头当前的位置。这三个信息合在一起，能完整描述图灵机在某一时刻的运行状态，相当于给计算过程拍了一张快照。

计算历史就是快照的序列：C₁, C₂, …, Cₗ，其中 C₁ 是起始格局，Cₗ 是接受格局，每个 Cᵢ 都是 Cᵢ₋₁ 按转移规则走一步的结果。文档特意强调了两点：一是计算历史是有限序列，如果图灵机在某个输入上永不停机，那它既没有接受历史也没有拒绝历史；二是确定型机器在给定输入上最多只有一个计算历史，非确定型机器才会有多个，对应多个分支。

这个概念的期末价值在于：它是“用有限串证明图灵机行为”的桥梁。后面 ELBA、ALL_CFG 的不可判定性证明，核心都是把一个图灵机的接受计算历史编码成另一个机器的输入串。所以背这条的时候，要顺带记住“计算历史是可以被检查的有限对象”，而不是只背定义。

3.2 三种描述层次：形式化、实现与高水平

文档第 11 条列了描述图灵机的三种层次，这是期末简答题的高频考点，也最容易写混。

三种描述的差别不在“长度”，而在“细节粒度”。形式化描述是最底层的，要把七元组和转移函数完整写出来；实现描述比它高一层，用“把读写头移到最右端”“在带上做个标记”这类话说清楚；高水平描述则干脆不提机器，直接说算法怎么做。期末如果让你“用实现描述设计一个判定器”，不要写状态转移表，写清楚“对输入串做什么操作”就够，写了反而浪费时间。反过来，如果题目明确要求形式化描述，只写算法描述是不给分的。

3.3 可识别、可判定与循环：图灵机的三种结局

图灵机在一个输入上运行，结果只有三种：接受、拒绝、循环。文档特意解释了“循环”这个词：它只表示机器不停机，不一定是永远以同样方式重复同样步骤。这个澄清很关键，因为有人会误以为“循环”就是进入一个死循环结构，实际上只要不停机就算循环。

可识别和可判定的差别，就在这两种“不接受”的方式上。图灵可识别允许“不是”的情况走进循环：只要输入属于语言，机器最终接受；输入不属于语言，机器可能拒绝、也可能永远不停。图灵可判定则要求所有输入都停机：属于就接受，不属于就拒绝，不存在第三种选择。文档里“判定器”的定义就是这个意思：总是能决定接受还是拒绝，永不循环。

所以“每一个可判定语言都是图灵可识别的”这条，方向是从判定到识别：判定器本身也是一台图灵机，它永不循环，自然满足识别的要求。反过来不成立，ATM 是图灵可识别的但不可判定，这个例子后面第 4 章会展开。

3.4 多带、非确定与单带确定：三个等价结论

文档第 6 到第 9 条其实是四个等价性结论串在一起：每个多带图灵机都等价于某个单带图灵机；每个非确定型图灵机都等价于某个确定型图灵机；一个语言图灵可识别，当且仅当存在非确定型图灵机识别它；一个语言图灵可判定，当且仅当存在非确定型图灵机判定它。

对期末来说，这些结论的功能是“语法糖”。写证明题的时候，可以把非确定型图灵机当成“猜一个答案然后验证”的模型；可以放心地用多带图灵机做中间步骤，然后说“根据等价性，存在等价单带图灵机”，不需要把多带模拟单带的细节展开。多带转单带的核心是把多个带的内容用分隔符串在一个带上、再用带符号记录读写头位置，模拟开销是平方级的；非确定转确定的代价更大，是 2 的指数级。这两个代价会在第 6 章的时间复杂性部分再次出现，现在先记住“都能转，但代价不同”。

4. 可判定性全景图：把可判定、不可判定与映射归约背成清单

4.1 可判定清单：从 ADFA 到 ALBA

文档里那个长条目，把自动机和文法相关的成员问题几乎一网打尽，全部标成可判定。我把它们整理成一张表，每行括号里是判定器的核心思路，简答题可以直接引用。

这张表的记忆钩子是：凡是对“有限对象做有限模拟”就能出结果的问题，都可判定。DFA 和 NFA 的状态有限，读入串后必然停机；CFG 的派生可以限制在乔姆斯基范式里用动态规划枚举；LBA 虽然带子无限长，但读写头不能离开输入区域，所以格局总数有限，可以用“超过上界没接受就拒绝”来避免循环。

文档里特意把“每一个上下文无关语言都是可判定的”放在这一组。这条的常见考法和正则的“真子集”关系一样：CFL 的判定器不靠模拟 PDA，因为 PDA 的栈可能无限增长、非确定分支可能循环，标准做法是转成乔姆斯基范式再做 CYK 动态规划。考试如果只让你判断“上下文无关语言是否可判定”，结论和理由各占一分，理由写“转 CNF 后动态规划”就够。

4.2 不可判定清单：停机问题、ETM、PCP

同一组里，文档紧接着列了另一串：ATM、停机问题、HALTTM、ETM、REGULAR_TM、EQTM、ELBA、ALL_CFG、PCP，全部不可判定。这串名字是期末选择题的“雷区”，因为它们和 4.1 那张表长得很像，结论却完全相反。

记忆这张表的一个技巧是分清层级：ATM 是所有不可判定问题的“源头”，其他问题基本都是把 ATM 归约过去的。HALTTM、ETM、REGULAR_TM 属于“第一层”，靠直接改动机器来归约；EQTM 需要更深一层，它连图灵可识别都不是，文档第 23 条专门说了这一点；ELBA 和 ALL_CFG 的证明要用到计算历史，属于“工具题”，期末一般不要求默写完整证明，但要知道它们不可判定。

文档里 PCP 的全称写成了“波斯地图对应实例”，这是 OCR 的错误识别，标准名字是波斯特对应问题（Post Correspondence Problem）。期末如果看到“波斯地图”四个字，别大惊小怪，知道它指 PCP 就行。

4.3 补图灵可识别：可判定当且仅当两个方向都可识别

一个语言的补，由所有不在该语言中的串构成。如果补是图灵可识别的，原语言就叫补图灵可识别。文档第 14 条给出了一个漂亮的刻画：一个语言可判定，当且仅当它既是图灵可识别的，也是补图灵可识别的。

这个定理的用途是“换赛道证明不可判定”。想证明 A 不可判定，除了正面用对角化或归约，还可以证明 A 可识别但 A 的补不可识别：如果 A 可判定，那么 A 的补也应该可识别，矛盾。ATM 就是标准实例：ATM 本身图灵可识别，但 ATM 的补不可识别，所以 ATM 不可判定。而 EQTM 更极端，它和图灵可识别、补图灵可识别都不沾边，文档第 23 条把它单独拎出来，就是为了防止你误以为“不可判定 = 补可识别”。

期末考到这里，容易出判断题“若一个语言是补图灵可识别的，则它是图灵可识别的”。反例就是 ATM 的补：它是补图灵可识别的，但它不可识别。背的时候记住：可判定是“双向可识别”，只看一个方向什么都推不出来。

4.4 映射可归约：把不可判定性“传染”给下一个语言

映射可归约是文档后半段的重点，定义要背准：存在一个可计算函数 f，对每个串 w，w 属于 A 当且仅当 f(w) 属于 B。这里的“当且仅当”是双向的，方向反了整个归约就废了。记号是 A ≤m B，读作 A 映射可归约到 B。

它的两个推论就是期末的得分点。第一：如果 A ≤m B 且 A 不可判定，那么 B 不可判定。第二：如果 A ≤m B 且 B 图灵可识别，那么 A 图灵可识别。注意第二个推论的方向：可识别性是“向前传染”的，但 A 不可识别推不出 B 不可识别，只能反过来说如果 B 可识别则 A 可识别。我当年考场上就栽在这里，把归约方向当成“等价”来用，实际上它只是单向蕴含。

构造归约函数 f 是简答题的常见出法，套路一般是：先把 A 的实例编码成 B 的输入格式，再设计一台机器对 w 做模拟。比如用 ATM 归约到 HALTTM，f 输入 (M, w)，输出 (M′, w)，其中 M′ 在 M 接受时停机、在 M 拒绝时进入循环。这样 w ∈ ATM 当且仅当 M′ 在 w 上停机。

从映射可归约再往前走一步，就是文档第 33 条的“多项式时间映射可归约”：把“可计算函数”换成“多项式时间可计算函数”，记号变成 A ≤p B，后面第 6 章的 P/NP 部分全靠它。两层归约长得像，但约束不同，一个只要求能算，一个要求算得快，这个坑第 5 章还会单独说。

5. 背知识点避坑指南：五个最容易翻车的记忆混淆

5.1 现象：把 ADFA 可判定和 ATM 不可判定记反

选择题里 ADFA、EDFA、ALBA 和 ATM、HALTTM、ETM 混在一起，让你选哪些是可判定的，结果一慌就把 DFA 相关的题和 TM 相关的题背反。

原因出在“自动机和图灵机到底差在哪”没理解透。DFA 状态有限，模拟它跑完输入一定停机，所以成员问题天然可判定；图灵机有无限带，可能循环，所以成员问题不可判定。这不是算法技巧问题，是机器模型能力问题。

解决：按机器分类背清单。DFA/NFA/正则表达式/CFG/PDA 相关的成员问题全部可判定；TM 相关的，ATM 和 HALTTM 不可判定；但 LBA 是个例外，ALBA 因为格局数有限反而是可判定的，ELBA 才不可判定。我考前会把 4.1、4.2 两张表默写一遍，写错一个就重新来，比反复读原文有效。

5.2 现象：认为“图灵可识别”就是“图灵可判定”

判断题说“ATM 是图灵可识别的”，有人选错成“不可识别”；或者看见“可识别”就默认它“可判定”，把两个概念画等号。

原因：可识别允许“不是”的时候循环，可判定要求对所有输入都停机。两个概念差在一个“会不会不停机”上，这在直觉上很难分清。

解决：把“可识别”记成“半判定”。一台机器半判定一个语言，输入属于它时一定说“是”，输入不属于它时可能说“不是”、也可能永远不说话。然后再背文档第 14 条：只有两边都能半判定，才是真判定。所以 ATM 是图灵可识别的，但不是可判定的，因为 ATM 的补不可识别。

5.3 现象：封闭性里漏掉空集与空串的边界

填空题问 ∅ 连接某个语言 L 等于什么，有人写 {ε}；问 ε 连接一个串是什么，有人觉得集合连接和串连接一样。

原因：把集合层面的“语言连接”和串层面的“字符串连接”混在一起。语言是串的集合，连接是拿一个集合里的每个串去和另一个集合里的每个串拼接；∅ 里没有串，拼不出任何东西，所以 ∅∘L = ∅。ε 是串不是集合，连接单个串时它才是幺元。

解决：把文档第 5 条扩展成三个公式，考前默写：∅∘L = ∅，{ε}∘L = L，∅* = {ε}。第三个是推论，不在原文档里，但填空选择经常带出来，不记就亏。

5.4 现象：把映射可归约和多项式时间归约混为一谈

证明某个问题属于 NP 时，直接套用“A ≤m B”，没检查归约函数是不是多项式时间可计算的；或者反过来，在可判定性证明里要求归约函数必须多项式时间。

原因：两个归约的名字太像，本质都是映射，但约束不同。映射可归约里的 f 只要可计算，哪怕指数时间都行，它服务于可判定性证明；多项式时间映射归约要求 f 在多项式时间内算出来，它服务于 NP 完全性证明。文档第 21、33 条分别是这两个定义，记号一个是 ≤m，一个是 ≤p，差一个下标 p，用途完全不同。

解决：做题先问问题在哪一层。可判定性讨论里用映射可归约，NP 讨论里用多项式时间归约，L/NL 讨论里用对数空间归约（文档第 40 条）。归约的“速度门槛”跟着讨论的复杂度类走，不能混。

5.5 现象：把 P 与 NP 背成“都能快速判定”

简答题让解释 P 和 NP 的区别，有人写“P 是能在多项式时间内解决的问题，NP 是不能在多项式时间内解决的问题”，直接把 NP 理解成“难题集合”。

原因：P 和 NP 都是用“判定问题”定义的，但判定方式不同。P 是确定型图灵机在多项式时间内判定；NP 是非确定型图灵机在多项式时间内判定，等价说法是存在一个多项式时间验证器：给你一个证书（比如 SAT 的一组赋值），你能在多项式时间内验证它。文档第 31 条说得最直白：P 是成员可以被快速判定的语言类，NP 是成员可以被快速验证的语言类。

解决：背六个字：“P 判得快，NP 验得快”。SAT、3SAT、CLIQUE、HAMPATH 这些属于 NP，是因为猜一个解再去验证很轻松，而不是因为能直接快速判定。再补一句库克-列文定理：SAT ∈ P 当且仅当 P = NP，也就是说 SAT 是 NP 完全问题，是 NP 家族里“最容易变成 P 的那一个”。

6. 考前 72 小时：用语言类层级链自测一遍，比再刷一遍讲义管用

6.1 从 L 到 NPSPACE：一条链背完四大复杂度类

文档最后一条给出了整个知识体系的“总地图”：L ⊆ NL ⊆ coNL ⊆ P ⊆ NP ⊆ PSPACE ⊆ NPSPACE。这条链串起了从对数空间到多项式空间的全部主要复杂度类，期末简答题“画出语言类包含关系”就是在考它。

萨维奇定理是这张表的关键支撑：对 f(n) ≥ n，NSPACE(f(n)) ⊆ SPACE(f²(n))。取 f(n) = n，就得到 NPSPACE ⊆ PSPACE；反方向 PSPACE ⊆ NPSPACE 由“确定性是非确定性的特例”直接成立，所以 PSPACE = NPSPACE。文档第 42 条还有一条对应 L 和 NL 的结论：如果有一个 NL 完全语言属于 L，那么 L = NL。这条的考点是“完全问题的地位”，和 P 与 NP 的关系是同构的。

6.2 自测清单：五问五答

考前最后一天，别再看文档原文，拿这张清单自测，答不上来的条目回到对应章节查：

第一问：默写语言类包含链。答不出 NPSPACE 的位置正常，但 L、P、NP、PSPACE 的相对顺序必须对。

第二问：ATM 的可判定性状态是什么？答案：可识别、不可判定；它的补不可识别。EQTM 更狠，既不可识别也不补可识别。

第三问：3SAT 和 CLIQUE 的归约方向是什么？答案：3SAT ≤p CLIQUE，构造方式是把每个子句变成一个三元团，再用冲突边防止不同子句的赋值冲突。方向反了就完全错了。

第四问：萨维奇定理在 f(n) = n 时说了什么？答案：NPSPACE ⊆ PSPACE，加上反方向 PSPACE ⊆ NPSPACE，推出两者相等。

第五问：一个语言可判定当且仅当什么？答案：它和图灵可识别、补图灵可识别同时成立，少一个方向都不行。

我当年考这门课前一天晚上，只背了零散知识点，结果简答题让画包含链，我把 NP 和 PSPACE 的位置写反，当场就意识到整门课的框架是散的。从那以后每次复习计算理论，第一步永远是默写这条链，然后往链上挂 4.1 和 4.2 的可判定、不可判定清单，最后才回头过封闭性和归约方向。这份《计算理论知识点.docx》适合直接导入笔记软件，按这条路线过一遍，比从头到尾读教材省时间。希望帮到你。

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