企业官网建设流程全解析

简介：面向哈工程等高校计算机专业学生的计算理论期末考点梳理，专治“背不下来”的焦虑。内容按自动机理论、图灵机、语言理论、计算复杂度理论等模块展开，系统汇总正则语言封闭性、DFA/NFA 等价、图灵机格局、可判定/可识别语言、映射可归约、P 与 NP 等核心知识，并列出 A_DFA、A_NFA、A_REX、EDFA、EQDFA、A_CFG、A_LBA 等可判定语言，以及 A_TM、停机问题、ETM、REGULAR_TM、EQTM、PCP 等不可判定语言，便于对照记忆。文档采用条目化速记风格，对“图灵可识别”与“图灵可判定”、“判定器”与“识别器”、“可计算函数”与“归约”等易混淆概念做了清晰对比，尤其适合考前集中背诵与查漏补缺。资源包仅含一个 docx 文件，大小仅 18KB，内容以条目式索引组织，轻量易读，便于打印或导入平板标注，方便快速查阅。已有 549 人浏览学习，是期末突击计算理论的实用笔记。

1. 计算理论期末复习：这份知识点清单到底在讲什么

计算理论期末复习最头疼的不是做题，是背——有穷自动机、上下文无关文法、图灵机、可判定性、不可判定性、P与NP，几十个概念互相嵌套，错一个就连锁崩盘。这份《计算理论知识点》把多数高校期末卷的考点浓缩成一条条可以直接引用的结论：从「有穷自动机识别的是正则语言」到「萨维奇定理」再到「L ⊆ NL ⊆ coNL ⊆ P ⊆ NP ⊆ PSPACE ⊆ NPSPACE」这条复杂度包含链，全部按命题形式列好，说穿了就是“背下来你就好了”。它不铺开解释定理的证明过程，只负责把“是什么、考什么、怎么推”讲明白。适合期末冲刺阶段拿来逐条过知识点，也适合刷题时当速查卡用。如果前面复习得稀碎，这份清单能帮你把知识框架重新钉住。

2. 从有穷自动机到正则语言：三张等价身份证与封闭性证明

2.1 正则语言的三张等价身份证

文档第1条、第4条、第6条、第7条放在一起看，其实就一句话：正则语言有三种等价描述方式——DFA、NFA、正则表达式。第1条说“被有穷自动机识别的是正则语言”，这是定义的入口；第4条用“当且仅当”补上反方向，即一个语言是正则的，当且仅当有一台非确定型有穷自动机识别它；第6、7条引入正则表达式，说“一个语言是正则的，当且仅当有一个正则表达式描述它”，“如果一个语言是正则的，则可以用正则表达式描述它”。注意第6条是充要条件，第7条是单向条件，考试常拿这种细节做陷阱。

这三张身份证意味着期末题有大量“换表示”的考法：给你正则表达式让你画NFA，给你DFA让你写出等价的正则表达式，或者给你一个状态图让你判断它识别的语言是不是正则语言。第3条“每一台非确定有穷自动机都等价于一台确定型有穷自动机”是三种表示能自由切换的底层依据。NFA看起来比DFA多了一个“同时处于多个状态”的能力，但这个能力并没有扩大语言类，子集构造法可以把任何NFA转成等价的DFA。理解了这个构造，就能回答“NFA和DFA谁更强”这种送分题——两者等价，谁也不比谁强。

第5条是经常被忽略的小点：空集连接到任何集合上得到空集，空串连接到任何一个串上不改变这个字符串。注意空集是语言层面的“一个元素都没有”，空串是串层面的“长度为0”。所以空集连接任何语言结果还是空集，空串连接任何串结果还是那个串。这两个符号长得像，含义完全不同，填空题最容易在这里翻车。

2.2 封闭性证明的构造思路

第2条说正则语言在并运算、连结、星号运算下封闭。别小看这条，期末证明题里它几乎必考，但很多人写不好构造。核心思路是用NFA而不是DFA做构造，因为NFA允许空串转移，拼装机器非常方便。

并运算的构造：给两台NFA分别加一个全新的起始状态，从这个状态引两条空串边，分别指向两台机器原来的起始状态，接受状态保持两台机器原有的接受状态不变。这样输入串只要被任意一台机器接受，整体就接受。

连结的构造：把第一台NFA的所有接受状态都加上空串边，指向第二台NFA的起始状态，然后把第一台的接受状态从接受状态集合里去掉，第二台的接受状态作为整体的接受状态。这样输入串必须先完整走完第一台，再进入第二台。

星号运算的构造：在原来的NFA上新增一个起始状态兼接受状态，再从新增状态和原有接受状态各加空串边回到原起始状态，形成“跑完一轮还能再跑一轮”的通路。这样零次、一次、多次都能接受。

这三个构造建议亲手在纸上各画一遍。考试时即使忘了细节，也能根据“闭包”这个直觉现场推出来。封闭性说明一个问题：并、连结、星号这三个运算不会把正则语言带到正则语言之外，这个结论在后面可判定性题目里会反复用到。

补一个容易混淆的点：正则语言在交运算和补运算下也封闭，但这份文档没有列，原因是交和补需要用积构造证明，和并运算的构造不是一套思路。期末如果问“正则语言的交是否封闭”，答案依然是封闭的，但证明时不要和并的构造混在一起。

2.3 NFA转DFA：为什么“非确定”不增加能力

这一节把子集构造法的步骤写细一点，属于每次考前都值得重看一遍的内容。

第一步，初始化：把NFA起始状态的“空串闭包”作为DFA的起始状态。空串闭包指从该状态出发，仅靠空串转移能到达的所有状态集合。

第二步，逐步扩张：对当前DFA状态（它是NFA状态的一个集合S），逐个读入输入符号a，计算S中每个状态经过a能到达的状态，再对这些状态取空串闭包，得到一个新的状态集合，把它作为DFA的转移目标。如果这个集合还没出现过，就加入DFA的状态集合。

第三步，标记接受状态：凡是集合里包含NFA接受状态的DFA状态，都标记为DFA的接受状态。

重复第二步直到没有新状态产生，算法结束。最坏情况新状态数达到2的n次方，n是NFA状态数，所以考试题里状态数一般控制在4个以内，不会让你写出几十个状态的转移表。

理解为什么要做空串闭包：空串转移不消耗输入符号，它只是“并行搬家”，所以每读一个符号，要把所有靠空串能到达的位置一并装进当前集合。这一步漏掉，构造出的DFA就会丢串。常见做法是在草稿纸上先画出完整的空串闭包表，再逐符号填转移，虽然慢一点但不容易漏。

3. 上下文无关语言与下推自动机：乔姆斯基范式和栈式记忆的等价逻辑

3.1 PDA与CFG的双向等价

第9条和第10条是一对完整命题：一个语言是上下文无关的，当且仅当存在一台下推自动机识别它。第10条是正向，第9条是反向。下推自动机可以理解为DFA加一个栈，栈能存无限多的符号，但只能从栈顶读写。这个“栈”给了PDA递归记忆能力，使它恰好能处理那些需要“数数”的语言，比如0的n次方1的n次方这种前后数量对应的串。

为什么CFG和PDA等价？直觉是：文法推导从起始变量开始，每一步把变量替换成产生式右侧的串；PDA则可以用栈模拟这个过程——把起始变量压栈，每读一个终结符，和栈顶对一下并弹出；每遇到栈顶是变量，就选择一条产生式，把变量弹出再把产生式右侧逆序压栈。反过来，从PDA也可以构造等价CFG，思路是把“从状态p到状态q，栈深变化正好抵消”编码成一个变量。期末一般只考简单例子，比如给定一个很短的文法让你构造PDA，或者在选择题里判断“上下文无关当且仅当PDA识别”这种等价性。

注意PDA有两种接受方式：按接受状态接受，和按空栈接受。两种定义下PDA的能力是等价的，但转换算法不一样。试卷上如果画了PDA却没标注接受方式，要先看它有没有画接受状态，再决定怎么分析。这个细节容易被忽略，实际考试中出现过不少次。

3.2 乔姆斯基范式：把CFG换成标准形态

第8条：任何一个上下文无关语言都可以用乔姆斯基范式的上下文无关文法产生。CNF的规则限制得很严：要么A→BC（两个非终结符），要么A→a（一个终结符），加上可选的S→ε。期末最常见的题型是给你一个普通CFG，让你转成CNF。转换有四个标准步骤，每步都有自己的坑。

第一步，消去空串产生式。找出所有能推导出空串的变量，然后为每个含该变量的产生式生成“去掉该变量”的版本。比如A→BC，如果B能推导出空串，则新增A→C；如果B和C都能，则A→B、A→C、A→空串也要考虑，但最终A→空串通常要删掉，除非A是起始变量。这里最容易漏掉的是新增多个组合版本。

第二步，消去单元产生式。单元产生式是A→B这种右侧只有单个变量的规则。对每个A→B，把B的所有产生式复制一份给A，然后删掉A→B。注意复制时如果B还有其他单元产生式，要先处理传递闭包，否则删不干净。

第三步，拆长产生式。A→B1B2…Bk（k大于等于3）时，引入新变量，把长产生式拆成两两一组。

第四步，处理无用符号。把不可达的变量和推导不出终结符串的变量删掉。这步容易被忽略，但标准答案里通常要求写清楚。

CNF为什么重要？因为有了规范形态，判断“给定CFG是否接受某个串”就有了固定算法：CYK算法，一个按子串长度从小到大填表的动态规划。期末考试如果考“判定ACFG”，原理就是先转成CNF再跑CYK。虽然手算不会真跑完整张表，但知道这一层会让你做概念题时不容易懵。

3.3 正则 ⊂ 上下文无关 ⊂ 可判定

第11条“每一个正则语言都是上下文无关的”是一条包含关系。为什么成立？因为DFA本身就可以看成一台从来不用栈的PDA——它不用栈也能处理正则语言，所以正则语言全部落在上下文无关语言这个更大的集合里。反过来，上下文无关语言里有大量不是正则的例子，最经典的就是0的n次方1的n次方，DFA数不清前一半的0和后一半的1是否数量相等，但PDA可以用栈压一个0弹一个1，轻松搞定。

文档第12条里还有两个可判定结论：ACFG（上下文无关文法是否接受某个给定串）是可判定的，ECFG（上下文无关文法是否为空）也是可判定的。前者靠CYK算法，后者靠检查起始变量是否能推导出终结符串。另外还有一句“每一个上下文无关语言是可判定的”，意思是上下文无关语言本身是递归语言，存在一台图灵机在有限步内判定任意串是否属于它。

这条线把正则、上下文无关和图灵可判定串起来了：正则语言 ⊆ 上下文无关语言 ⊆ 可判定语言。这个包含链条看着简单，但它揭示了后面复杂度章节的一条暗线：三个语言类从简单到复杂，判定难度递增，可判定性却都还是“良性的”。真正出问题的是图灵机那种带循环的识别过程。

4. 图灵机的三种结局：可识别、可判定与永不停机

4.1 格局与计算历史：图灵机运行的快照

文档第1条讲格局：当前状态、当前带内容和读写头当前的位置，这三样组合在一起就是图灵机的一个格局。一句话理解就是“某一瞬间机器的完整状态快照”。计算历史是格局序列C1到Cl，其中C1是起始格局，Cl是接受格局或拒绝格局，且每个Ci都是Ci-1经一步转移得到的结果。计算历史都是有限序列，如果机器永不停机，就既没有接受历史也没有拒绝历史。

计算历史的性质非常关键：确定型图灵机在给定输入上最多只有一个计算历史，因为每一步转移都是唯一确定的；非确定型图灵机在单个输入上可能有多个计算历史，对应多个分支。这些性质在后面证明不可判定性时会被反复用到——尤其是“计算历史法”，把“是否存在一个符合规则的合法序列”编码成某个判定性问题，再归约到已知不可判定的问题上。

考试里关于格局最常出的题是：给一个图灵机运行的中间快照，让你写出下一个格局，或者判断当前格局是否能被接受。只要记住格局三要素——状态、带上内容、读写头位置——迁移一步就够。注意读写头位置通常用带符号序列中当前字符上方加标记表示，别漏掉带两端可能的空白符号。

4.2 三种结局与判定器的边界

文档第4条：在输入上运行一个图灵机，可能出现接受、拒绝、循环三种结果。循环就是不停机，但它不一定是以同样的方式重复同样的步骤——这是初学者最容易理解错的地方。“循环”不代表机器在绕圈，而是代表它永远不停止，可能每次都在做不一样的事。图灵机有两种不接受输入的方式：一种进入拒绝状态然后停下来，另一种是进入循环，也算不接受。这两种不接受，在可识别性的定义里地位截然不同。

判定器是“在所有输入上都停机”的图灵机。它永远不循环，总能决定接受还是拒绝。所以可判定语言的条件比可识别语言强得多：图灵可识别只要求“语言里的串一定能被接受”，非本语言的串可以不停机；图灵可判定要求所有串都给出明确答复。第5条“每一个可判定语言都是图灵可识别的”是显然的，但反过来不成立。

第14条给了精确的等价条件：一个语言是可判定的，当且仅当它既是图灵可识别的，也是补图灵可识别的。这条定理在期末题里出现频率极高，经常以“L可识别，L的补也可识别，问L是否可判定”的形式出现。答案是可判定，因为两个识别器可以交替运行，谁先接受就输出谁的结果。这个构造思路也解释了为什么“补图灵可识别”这个概念会被单独定义出来。

4.3 多带、非确定与丘奇-图灵论题

文档第6条、第7条是两条等价性结论：每条多带图灵机都等价于一台单带图灵机；每台非确定型图灵机都等价于一台确定型图灵机。这两条合起来的含义是：图灵机的能力不因为“多几条带子”或“多一个不确定选择”而变强。非确定型图灵机“猜”一个答案的能力，在可计算性层面没有扩大图灵可识别语言类。第8条、第9条又把这种等价性写成语言类层面的充要条件：一个语言是图灵可识别的（可判定的），当且仅当存在非确定型图灵机识别（判定）它。

但这里要特别强调：等价是“可计算性层面”的等价，不是“效率层面”的等价。多带转单带会引入平方级时间开销，非确定转确定是指数级开销。很多同学在P与NP问题上懵，根源就是把这两个层面的等价混在了一起。可计算性等价只能说“能不能算”，复杂度等价才是“算得快不快”，两者不是一回事。

第10条丘奇-图灵论题也很好考：算法的直觉概念就等同于图灵机可计算。它是一条论题而不是定理，没有办法被证明，但所有已知计算模型都满足这个边界。第11条三种描述层次是另一种考法：形式化描述要把状态和转移函数全部写出来，最详细也最啰嗦；实现描述用日常语言讲机器怎么管理带子和读写头，不需要列转移函数；高水平描述直接用算法语言描述，完全不提图灵机的带子和读写头。考试要你判断“某个描述属于哪一层”的时候，就看它有没有出现状态集合、转移函数、读写头这一类术语。出现完整状态和转移函数的是形式化描述，只提带子和读写头但不提状态的是实现描述，全程不提机器细节的是高水平描述。

第17条线性有界自动机是受限图灵机：读写头不能离开包含输入带的区域，试图越界时读写头原地不动。线性有界自动机的格局数量是输入长度的指数级，所以ALBA是可判定的，但ELBA是不可判定的，这个反差值得记一下，后面章节会用到。

提示：复习这一章时，把“可识别”“可判定”“停机”三个词在每道题里圈出来，这三个词的差异就是这一章大部分考点的分水岭。

5. 可判定性判断避坑指南：不可判定清单与归约方向的血泪经验

5.1 可判定清单：哪些问题能算出答案

文档第12条先给出了一个可判定名单：ADFA（DFA是否接受给定串）、ANFA（NFA是否接受给定串）、AREX（正则表达式是否生成给定串）、EDFA（DFA是否接受空语言）、EQDFA（两台DFA是否接受同一语言）、ACFG（CFG是否生成给定串）、ECFG（CFG是否生成任何串）、ALBA（LBA是否接受给定串）。

这些判定问题为什么可判定，每个的算法各不相同。ADFA直接模拟DFA跑一遍输入，跑到头看是否停在接受状态；ANFA和AREX先转成DFA再模拟；EDFA做一个从起始状态出发的图搜索，看能不能到达接受状态；EQDFA的思路更巧妙——构造一台“对称差自动机”，它接受正好被其中一台接受、不被另一台接受的串，然后判空；ACFG用CYK算法；ECFG检查起始变量能否推导出终结符串；ALBA因为线性有界自动机的格局数是有限的，可以在所有有限格局的范围内做搜索。把这份名单记牢，做题时先把名字对号入座，再谈其他。

5.2 不可判定清单：哪些问题根本算不出

另一份名单更让考生头大。不可判定的问题包括：ATM（给定图灵机M和串w，M是否接受w）、停机问题HALTTM（M在w上是否停机）、ETM（M是否不接受任何串）、REGULARTM（M识别的语言是否正则）、EQTM（两台图灵机是否接受相同的串）、ELBA（线性有界自动机是否不接受任何串）、ALLCFG（CFG是否生成所有串）、PCP（波斯特对应问题）。文档里写的“波斯地图对应实例”是PCP的翻译差异，按“波斯特对应问题”记就好。

这里要分清不可判定的证明路径。ATM本身用对角化法证明：假设存在判定器H，构造一台“反着来”的机器D，D问H“D自己是否接受w”然后给出相反答案，导致逻辑矛盾。其他问题大多靠归约证明——把ATM归约到目标问题，如果目标问题可判定，ATM就可判定，矛盾。所以复习策略很清晰：先把ATM不可判定这个根记牢，再把每条归约的大方向记清楚，细节题靠现推。

文档第12条还给了两个更进阶的结论：ATM的补是不可识别的（不光是不可判定，连可识别都做不到）；EQTM既不是图灵可识别的，也不是补图灵可识别的。复习到后期要能区分“不可判定但可识别”（如ATM本身）和“连识别都不可”（如ATM的补和EQTM）两类问题。这两类在选择题里经常以“下列说法正确的是”的形式出现。

5.3 映射可归约：方向决定一切

第18条到第22条是映射可归约的定义和性质。一句话：存在一个可计算函数f，把问题A的每个实例w映射成问题B的实例f(w)，并且w属于A当且仅当f(w)属于B。记作A ≤m B，f就叫从A到B的归约。第20条定义了可计算函数本身：存在图灵机在任意输入w上停机时，带上恰好留下f(w)。第21条把这个定义用到语言上，就是语言A映射可归约到语言B的完整条件。

由这个定义得到两个最常用的推论，也是第22条的内容：如果A ≤m B且A不可判定，则B不可判定；如果A ≤m B且B图灵可识别，则A图灵可识别。方向特别容易被记反。想做“证明B不可判定”的题目，正确姿势是：找出一个已知不可判定的A（比如ATM），构造f把A归约到B，然后由第一条推出B不可判定。如果你写的是B ≤m A，那是归约方向搞反了，结论推不出来。

证明REGULARTM不可判定的经典思路就是：构造函数f，输入是(M,w)，输出一台新机器M'。M'先模拟M在w上的运行，如果M接受w，M'就只接受一个固定的非正则语言（比如0的n次方1的n次方）；如果M不接受w，M'不接受任何串。于是“M是否接受w”被编码成了“M'识别的语言是否正则”的反面，严格说是把ATM归约到REGULARTM的补，再由补可判定推出原问题可判定会产生矛盾，从而证明REGULARTM不可判定。理解了这条思路，类似ETM、EQTM的证明都能顺下来。

5.4 避坑常见问题：期末高频混淆点记录

坑一：把“图灵可识别”当成“图灵可判定”。 现象：题目说“一个语言能被某图灵机识别”，选项直接判它“是可判定的”。 原因：初学者只记了“识别”这个词里有“可”字，没注意到识别器允许在拒绝方向陷入循环。 解决：做题先划关键词——题里写的是“识别”还是“判定”。识别是存在性，只要语言里的串能被接受就行；判定是全称性，所有输入都必须停机给出结果。没有“判定器”或“停机”相关表述，就不能推可判定。

坑二：补图灵可识别验证时漏了方向。 现象：证“L可判定”，只说明L可识别就收工。 原因：可判定当且仅当可识别且补可识别，两个条件都要满足。 解决：按模板写两句话：“L可识别（理由…）；L的补可识别（理由…）；由定理，L可判定。”如果其中一个方向给不出来，题目大概率是想考不可判定。

坑三：归约方向写反。 现象：要证B不可判定，写“B ≤m A”还觉得没毛病。 原因：把“用B的解法解决A”误记成“用A解决B”。 解决：每次写归约前先默念“从已知到未知”：左手是已知不可判定的A，右手是待证的B，f把A的实例翻译成B的实例。写完后检查一遍：翻译后的实例是否属于B，跟原实例是否属于A保持一致。

坑四：空集和空串的运算混用。 现象：填空题“空集和任意语言L连接，结果是？”填了L，甚至填了空串。 原因：空集与空串形近义不同。 解决：把空集看成“一个元素都没有的集合”，它连接任何集合都没有元素可选，结果只能是空集；空串是“一个长度为0的串”，它连接任何串也只是原串。

坑五：3SAT归约到CLIQUE的方向记反。 现象：默写“3SAT ≤p CLIQUE”时，写成了“CLIQUE ≤p 3SAT”。 原因：只记住两个都在NP完全清单里，忽略了归约链的具体方向。 解决：用库克-列文定理锁定SAT是NP完全，再用“子句到团”的编码记住3SAT归约到CLIQUE。考试现场推不出来时，就用定义验证：CLIQUE要求“是否存在k个两两相邻的顶点”，这个结构偏图论，不容易被编码成布尔公式，而3SAT的子句天然可以编码成图，所以方向是从3SAT到CLIQUE。

6. 复杂度类怎么读才不糊：从P到PSPACE的自测验证法

6.1 复杂度定义与两条时间换算

第24条定义时间复杂性类TIME(t(n))：由时间O(t(n))的图灵机可判定的所有语言的集合。这里隐含了一个前提：讨论复杂度时用的图灵机必须是判定器，因为只有停机才有时间可言。第25条说每条多带图灵机都等价于某个O(t²(n))时间的单带图灵机；第26条说每个t(n)时间的非确定型单带图灵机都等价于某个2^O(t(n))时间的确定型单带图灵机。这两条是多带转单带、非确定转确定在复杂度层面的“代价表”：前者是平方级，后者是指数级，两者差距巨大。

第36条定义了空间复杂性类SPACE(f(n))和NSPACE(f(n))，第37条萨维奇定理把非确定空间压缩到确定空间的平方，使得NPSPACE等于PSPACE。第40条对数空间转换器是归约的一种细化，它要求归约函数本身在对数空间内可计算，这是L与NL类内部讨论归约时默认使用的归约基准。

6.2 归约关系与三个“完全”定盘星

第28条和第30条是P与NP的具体成员：PATH、RELPRIME、每个上下文无关语言都在P里；HAMPATH、CLIQUE、SUBSET-SUM、SAT、3SAT、UHAMPATH都在NP里。第31条给了一个直觉对照：P是成员可以快速判定的语言类，NP是成员可以快速验证的语言类。第34条库克-列文定理：SAT属于P当且仅当P=NP，这句话把SAT推成NP完全问题的原点。第35条给出3SAT多项式时间可归约到CLIQUE。PSPACE完全的代表是TQBF、FORMULA-GAME、GG；NL完全的代表是PATH。

6.3 自测验证法：我期末前三天怎么用这份文档

分享一个我自己的复习习惯。拿到这份知识点文档后，我第一件事不是背，而是把所有“当且仅当”语句单独抄出来，做成双向卡片：一边写条件，一边写结论。比如“一个语言是可判定的，当且仅当它既是图灵可识别的，也是补图灵可识别的”，盖住后半句默写前半句，再反过来盖住前半句默写后半句。双向推得动，才算真正记住，单向能背不算数。

第二件事是把不可判定清单按证明方法分组：从ATM直接对角化的归一组，经归约证明的归一组，连识别都不行的归一组（ATM的补、EQTM）。分组之后，考场上遇到没见过的判定问题，先想它能不能用列表法做有穷搜索，能则可判定；再想ATM能不能归约到它，能则不可判定。第三件事是考前最后一天把复杂度包含链默写三遍，每写一遍都顺带写出每个类的一个代表语言。

这套流程看着简单，但我每次都是靠它把“好像背过但又说不太清楚”的知识点钉死。从那以后，我期末复习计算理论，都强制自己先过一遍这份文档，再过一遍自测单，再进考场。希望帮到你。

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