计算理论期末复习：自动机、图灵机与可判定性知识点串讲

简介这份《计算理论知识点》文档专为哈尔滨工程大学计算理论期末复习打造系统梳理自动机理论、图灵机、语言理论与计算复杂度等核心模块覆盖正则语言、上下文无关语言、图灵可判定性、映射可归约等高频考点适合考前突击背诵与理解性记忆。资料仅含1个docx文件约18KB以知识点清单、关键结论和可判定/不可判定问题对照表的形式组织无需解压即可快速查阅打印。已有549人学习下载受到本校及相关课程学生认可。文档不仅给出“有穷自动机识别正则语言”“非确定型与确定型自动机等价”“图灵可判定与可识别”等基础结论还细化了格局、计算历史、判定器、线性有穷自动机等难点概念并对ADFA、ATM、停机问题、EQTM等经典判定与不可判定问题做了清晰辨析同时引入多项式时间归约、P与NP、SAT与3SAT等复杂度理论内容可帮助读者快速建立完整知识框架应对期末考试中的选择、简答与证明题。1. 计算理论期末复习背什么这份知识点文档把答案串成了一条线哈工程的《计算理论》期末很多人挂在同一个地方上课听懂了题不会做题会做了概念又背串。这门课跟高数不一样它的核心不是推导而是先建立起一张“哪些问题能判定、哪些不能判定、归约往哪个方向走”的全局地图而这张图只能靠背。这份《计算理论知识点.docx》就是干这个用的它把自动机、图灵机、可判定性、P/NP/PSPACE 这些章节的核心结论按条目收在一起没有推导过程全是期末考试可以直接引用的命题。适合两类人刚学完想快速过一遍的和考前两三天需要把知识点钉死的。文档后半段编号从 1 重新开始是原排版问题内容本身按主题走不影响背。2. 自动机与语言层级从 DFA 到 PDA先分清谁识别谁2.1 一张表背熟四台机器与三层语言这份文档前 11 条本质就是在回答一个问题语言、文法、机器三者怎么对应。很多判断题的错误答案都出在把“谁产生语言”和“谁识别语言”搞反。我一般建议先把下面这张表背到能默写再去看文档里那些文字表述。语言层级产生/描述方式识别机器核心等价结论正则语言正则表达式有穷自动机DFA/NFA被 DFA 识别 ⟺ 正则 ⟺ 有正则表达式描述上下文无关语言上下文无关文法CFG下推自动机PDA被 PDA 识别 ⟺ 上下文无关 ⟺ 有 CFG 产生图灵可识别语言图灵机可停机接受图灵机存在某台图灵机识别它图灵可判定语言判定器总停机判定器存在某台图灵机判定它这张表的记忆顺序是“能力递增”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文档里那个长条目把自动机和文法相关的成员问题几乎一网打尽全部标成可判定。我把它们整理成一张表每行括号里是判定器的核心思路简答题可以直接引用。语言输入判定器核心思路ADFADFA B 和串 w在 B 上模拟运行 w结束时看是否停在接受态ANFANFA B 和串 w模拟时跟踪所有可能状态或先转 DFA 再模拟AREX正则表达式 R 和串 w把 R 转成 NFA再按 ANFA 的流程判定EDFADFA B检查从起始状态能否到达某个接受状态EQDFA两个 DFA构造对称差自动机用 EDFA 判定它是否为空ACFGCFG G 和串 w转乔姆斯基范式用动态规划检查 w 能否派生ECFGCFG G检查起始变元能否派生某个终结串ALBALBA M 和串 w模拟 M格局数超过上界还未接受则拒绝这张表的记忆钩子是凡是对“有限对象做有限模拟”就能出结果的问题都可判定。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图灵机 M 接受串 w对角化始祖HALTTM图灵机 M 在输入 w 上停机归约自 ATMETM图灵机 M 不接受任何语言归约自 ATMREGULAR_TM图灵机 M 的语言是正则的归约自 ATMEQTM两台图灵机接受相同的语言归约自 ETMELBALBA M 不接受任何语言计算历史归约ALL_CFGCFG G 产生所有串归约自 PCPPCP波斯特对应问题归约自 ATM记忆这张表的一个技巧是分清层级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对每个串 ww 属于 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 归约到 HALTTMf 输入 (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。这条链串起了从对数空间到多项式空间的全部主要复杂度类期末简答题“画出语言类包含关系”就是在考它。复杂度类一句话定义代表对象L对数空间确定性判定对数空间可计算函数NL对数空间非确定性判定PATH 是 NL 完全的P多项式时间可判定PATH、RELPRIME、每个上下文无关文法NP多项式时间可验证SAT、3SAT、CLIQUE、SUBSET-SUMPSPACE多项式空间可判定TQBF、FORMULA-GAME、GG 是 PSPACE 完全的NPSPACE多项式空间非确定性判定由萨维奇定理等于 PSPACE萨维奇定理是这张表的关键支撑对 f(n) ≥ nNSPACE(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》适合直接导入笔记软件按这条路线过一遍比从头到尾读教材省时间。希望帮到你。本文还有配套的精品资源点击获取