简介这份《计算理论知识点.docx》面向哈尔滨工程大学计算理论期末备考的计算机专业学生也适合需要快速回顾形式语言与可计算性基础的读者用条目化方式梳理自动机、图灵机、语言理论与计算复杂度等核心考点帮助在考前集中背诵结论并查漏补缺。压缩包仅含1个docx文档大小约18KB篇幅轻便适合打印或导入平板反复翻阅。文档围绕DFA与NFA等价、正则语言封闭性、上下文无关语言与下推自动机、图灵可识别与可判定、判定器、可计算函数、映射归约以及P、NP、SAT、3SAT等高频知识点展开强调定义与判定条件的对应关系便于快速定位易混概念。已有551人学习适合期末冲刺时配合教材和习题使用也可作为章节复习前的提纲对易混的判定条件与归约关系可反复对照记忆。1. 加资源不变强、砍资源才变强计算理论里那条反直觉的分界线计算理论里最反直觉的一件事是给机器加资源能力几乎不涨砍资源能力反而涨。给图灵机多加几条带子、多装几个读写头、放开非确定性让它同时走多条分支这三样全加上去它能判定的语言集合一个都没变大——多带等价于单带非确定等价于确定。反过来把读写头拴死在输入区不许越界这台被削弱的线性有界自动机接受问题反倒成了可判定的格局总数有限搜得完。这条分界线值不值得搞懂取决于你想“背下来”还是想“推出来”。这份文档把结论按有穷自动机、上下文无关文法、图灵机、可判定性、复杂性一条条列全了它们压缩的是同一件事机器的记忆结构决定它的能力边界。只背结论换个设问就会错知道记忆结构怎么限制机器结论遇到没见过的题也能现推。下面按这条线索从最弱的有穷自动机往上走。2. 正则语言的三张脸为什么 DFA、NFA、正则表达式总是同时出现2.1 五元组里那个 δ决定了 DFA 只能记住有限个事实确定型有穷自动机写成五元组 (Q, Σ, δ, q0, F)其中 δ: Q×Σ→Q 是一个全函数给定当前状态和一个输入符号下一个状态唯一确定。关键不在“确定”而在 Q 是有限集。整台机器的记忆就是“我现在处在哪个状态”状态数一旦固定它能记住的事实就固定了。这个限制很硬。判断“串是否以 1 结尾”只要 2 个状态判断“串里 1 的个数是不是 3 的倍数”要 3 个状态取模就够了但判断 {0ⁿ1ⁿ | n≥0} 就不行——n 可以任意大机器必须记住“已经读了多少个 0”而这是无穷多种可能塞不进有限个状态。教材里的泵引理就是把这句话形式化p 个状态的机器读长度 ≥p 的串走 p1 步必然重复某个状态中间那段读过的内容可以任意重复或删掉而判断结果不变于是“必须精确计数”的语言全被排除。提示很多教材把 δ 定义成部分函数允许某些 (状态, 符号) 没有转移。这在单独描述 DFA 时没问题但一旦要构造补运算就会出问题后面 2.3 节会踩到这个坑。2.2 子集构造NFA 的“猜测”怎么变成 DFA 的“确定”非确定型有穷自动机的转移函数是 δ: Q×Σε→P(Q)输出的是一个状态集合还允许 ε 转移不读输入就跳。它的接受条件是“存在某条路径走到接受状态”也就是它天生带“猜”的能力。直觉上它比 DFA 强但结论是两者等价桥就是子集构造——把“所有可能处于的状态”打包成一个 DFA 状态。def subset_construct(nfa): start eps_closure({nfa.q0}) # 起始状态先做 ε 闭包 dfa_id {frozenset(start): 0} # DFA 的一个状态 NFA 状态集合 queue, trans [frozenset(start)], {} while queue: cur queue.pop(0) for a in nfa.sigma: # 只遍历真实字母ε 不进这个循环 nxt eps_closure(move(cur, a)) # movecur 中状态经 a 能到达的所有状态 if nxt not in dfa_id: # 只保留可达子集不做全幂集展开 dfa_id[nxt] len(dfa_id) queue.append(nxt) trans[(dfa_id[cur], a)] dfa_id[nxt] accept {i for s, i in dfa_id.items() if s nfa.accept} return dfa_id, trans, accept # accept 按“集合里含 NFA 接受态”判定参数和逻辑说明eps_closure求的是不读输入就能到达的状态闭包move只走一个真实符号两者必须分开否则会把 ε 路径重复计入。nfa.sigma不含 ε 是关键细节——ε 不是输入字母表里的字符把它放进外层循环会导致构造出的 DFA 转移表多出一列永远用不到的边。状态数上界是 2^|Q|实际只建从起始集合可达的那些通常远小于上界但最坏情况下的指数膨胀是真实存在的这也是为什么工程里的正则引擎宁可保留 NFA 模拟 Thompson 构造 并行状态集合也不真去做确定化。注意这个构造同时证明了“语言是正则的当且仅当存在 NFA 识别它”。方向是DFA 是 NFA 的特例一个状态集合退化成单元素集NFA 又能确定化成 DFA两头一夹就闭合了。2.3 封闭性为什么用乘积构造证明星号为什么要靠 ε 边正则语言在并、连接、星号下封闭是文档里反复出现的结论。并和交的证明靠乘积构造两台 DFA 同时跑状态是序对 (q1, q2)转移逐分量进行 δ((q1,q2), a) (δ1(q1,a), δ2(q2,a))接受条件按要证的运算挑。运算状态集合接受条件A ∪ BQ₁×Q₂q₁∈F₁ 或 q₂∈F₂A ∩ BQ₁×Q₂q₁∈F₁ 且 q₂∈F₂A − BQ₁×Q₂q₁∈F₁ 且 q₂∉F₂¬AQ₁先补全死状态q₁∉F₁注意表格最后一行括号里的“先补全死状态”如果原机器的 δ 是部分的某些串根本走不到任何状态取反 F 之后这些串依然不被接受补集就算错了。解决办法是加一个吸收状态把所有缺失的转移都指向它让它非接受再取反。连接和星号没法用乘积构造做因为“前一段在哪结束、后一段在哪开始”这个切分点不确定。所以引入带 ε 边的 NFA连接是把 M₁ 的每个接受状态用 ε 连到 M₂ 的起始状态星号是在外面套一个新起始状态ε 连到旧起始旧接受状态 ε 连回旧起始。三种封闭运算对应三种 ε 连线方式正则表达式的三个基本运算并、连接、星号刚好就是这三条构造。换句话说正则表达式的语法不是随便定的它的三种组合子之所以够用是因为它们各自对应一个可构造的自动机拼接动作多一个少一个都会破坏这套对应关系。3. 下推自动机与乔姆斯基范式一个栈为什么刚好够用3.1 从 A → aB 到 A → BC乔姆斯基范式在拆一棵树上下文无关文法写成四元组 (V, Σ, R, S)产生式形如 A → α左边必须是单个变量右边是变量和终结符组成的任意串。语言里的每个串对应一棵推导树树根是起始符号 S叶子从左到右拼成这个串。上下文无关的意思是不管 A 出现在推导的什么位置把它重写成 α 的规则都成立不需要看 A 的左右邻居。乔姆斯基范式把产生式压缩成两种形状A → BC两个变量和 A → a单个终结符外加一种特例——如果 ε 在语言里允许 S → ε且 S 不出现在任何右部。任何上下文无关文法都能机械地转成这个形状三步走先把 A → BCD 这种长右部拆成 A → BX、X → CD再把终结符混在长右部里的地方换成一个专门产生它的变量 T_a → a最后消掉 ε 产生式和 A → B 这种单位产生式。这套规范化的价值不在“好看”而在它把推导树掰成了严格的二叉树。一棵有 n 个叶子的满二叉树恰好有 n−1 个内部节点对应 n−1 次 A → BC 类型的推导加上 n 次 A → a 把叶子生成出来长度为 n 的串在任何乔姆斯基范式文法里的推导步数正好是 2n−1。这个数字是很多证明的支点它意味着“枚举所有推导”是一棵有限的、深度有界的树可以暴力搜也可以从长度为 1 的子串往上填表——CYK 算法就是借这个结构在 O(n³) 里判成员资格。这也是文档里“每一个上下文无关语言都是 P 类”的来源。3.2 栈的读写策略记忆结构从“有限个格子”变成“一条后进先出的带”下推自动机写得比有穷自动机多一个栈(Q, Σ, Γ, δ, q0, Z₀, F)转移函数 δ: Q×Σε×Γε → P(Q×Γε)第三个输入参数是当前栈顶符号输出可以往栈上压一串符号。栈的规则是后进先出只有栈顶可见、可弹、可压。这个记忆结构刚好对上“嵌套配对”这类语言。判断 {0ⁿ1ⁿ} 时读 0 就压栈读 1 就弹栈最后栈里只剩初始符号 Z₀ 就接受——栈的深度天然记录着“已经读了多少个 0”。有穷自动机做不到这一点因为它的“计数器”只能是有限个状态图灵机不需要专门设计就能做因为带子可以来回移动。栈卡在中间容量无界但只能从一头进出。这个限制也能解释为什么栈不够用。{0ⁿ1ⁿ2ⁿ} 不是上下文无关的理由是栈只有一个顶压 0 的计数会被后面 1 的计数覆盖掉两种计数在同一个栈上互相打架。用一个栈记两件事必然有一件记不住。3.3 非确定性在这里不再是免费的NPDA 与 DPDA 不等价文档里说一个语言是上下文无关的当且仅当存在一台下推自动机识别它。这里有个容易被忽略的差异这个结论里的下推自动机是非确定的。有穷自动机那边非确定型和确定型等价子集构造就能抹掉“猜”的能力下推自动机这边等价的结论不成立确定型下推自动机识别的语言有时叫 DCFL是上下文无关语言的真子集。机制上的原因很清楚。子集构造之所以可行是因为“NFA 当前可能处于的状态集合”虽然是个集合但它是有限集 Q 的子集天生塞得进有限个 DFA 状态里。放到下推自动机上非确定型机器在某一时刻“可能处于的格局”里包含的是栈内容而栈内容有无穷多种这个集合塞不进任何有限结构构造就断了。非确定性在这里没法用枚举抹平只能真留着。提示非确定性是否“免费”取决于你把它当作状态集合还是当作搜索分支。在可判定性层面它免费后面 4.3 节会说非确定图灵机等价于确定图灵机在时间层面它不免费指数代价在栈结构这就连语言类都改变了。还有一条层级要记住每一个正则语言都是上下文无关的。构造很直接——把 DFA 的每个状态 q 变成一个变量 A_q对每条 δ(q,a)r 加一条 A_q → aA_r接受状态再加 A_q → ε。反过来不成立{0ⁿ1ⁿ} 就是分界线上那个反例。4. 格局与判定器图灵机“循环”这件事到底黑在哪4.1 格局把“状态 带内容 读写头位置”打包成一个瞬间快照图灵机的形式定义是 (Q, Σ, Γ, δ, q0, q_accept, q_reject)δ: Q×Γ → Q×Γ×{L,R}即当前状态加读写头下的符号决定新状态、写回的符号和左移还是右移。注意 δ 在 q_accept 和 q_reject 上没有定义这两个状态是“停机”的语义落点。计算过程里任一时刻的完整快照就是把当前状态、带内容、读写头位置三者合起来这叫格局。形式化地写成 u q v 或者 u q a vu 是读写头左边的串q 是当前状态v 是从读写头位置开始往右到最右非空白符号的串。这个写法很省因为它默认读写头左边和右边远处全是空白而空白符号是无限供应的。格局的总数直接决定了一台机器的“可搜索性”。如果带子只用了有限个格子、读写头被限制在输入区内线性有界自动机就是这种情况格局数是 |Q| × n × |Γ|ⁿn 是输入长度这是一个有限的数。既然有限从起始格局能不能走到接受格局就是一张有限图上的路径问题暴力搜一定能出结果。反过来普通图灵机的带子可以越写越长格局数没有上界这张图是无限的“能不能走到接受格局”就不再是有限搜索能回答的问题——这就是后面 5.3 节里可判定与不可判定的真正分水岭。4.2 判定器与识别器停机承诺值多少钱在输入上跑一台图灵机结果只有三种接受、拒绝、循环。这里的循环不是“原地重复同样的步骤”而是“永不停机”可能一直在往右走、一直在写新的符号你看着它一直在动就是不知道它到底会不会停。图灵可识别的语言递归可枚举语言只要求“存在一台图灵机对语言里的串最终接受”对语言外的串没有任何承诺它可能拒绝也可能一直跑下去。图灵可判定的语言递归语言要求更强存在一台机器对所有输入都停机接受或拒绝都有明确答案。这种“所有输入都停机的图灵机”就是判定器。判定器之所以被单独拎出来是因为“区分循环和跑得久”这件事没有通用算法。你盯着机器跑到第 10¹² 步它可能下一步就接受也可能永远不。工程里可以用超时来兜底理论上没有一个上界能保证“过了这个界还没停就是循环”。所以我们宁可讨论“保证停机”的机器也不讨论“有可能循环”的机器。这也解释了为什么文档里要强调那一对结论每一个可判定语言都是图灵可识别的反过来不成立。还有一个非常实用的等价刻画一个语言是可判定的当且仅当它既是图灵可识别的也是补图灵可识别的。做法是让两台识别器并行跑输入串 w 交替喂给两边各走一步哪边先接受就立刻给出答案。因为 w 要么在语言里、要么在补集里两边至少有一台会在有限步内接受所以这个并行过程一定停机而且它同时给出了“是”和“否”的判决。4.3 多带、非确定与三种描述层次加资源为什么不改变能力多带图灵机每条带子有自己的读写头看起来比单带强一大截。等价性证明的做法是把 k 条带子编码到一条带上带子划分成 k 条“道”每条道对应一个虚拟带道与道之间用分隔符隔开每个虚拟读写头的位置用带标记表示。模拟一步需要扫过整段被用到的区域单次代价 O(t)跑到 t 步总代价 O(t²)。这就是文档里那条“t(n) 时间的多带图灵机与 O(t²(n)) 时间的单带图灵机等价”的来源。非确定型图灵机等价于确定型图灵机做法是广度优先遍历格局树用三条带子一条存输入一条当队列存待搜的格局一条当工作区。一条分支的地址就是一串选择编号模拟时按编号在输入上重走一遍。代价是时间从 t 涨到 b^{O(t)}b 是最大分支数。能力没变代价变了——这条差别在第 6 章会成为 P 与 NP 之间那道墙。支撑这一整套等价性证明的是丘奇-图灵论题算法这个直观概念就是图灵机可计算。它不是定理没有证明它是“形式化定义选对了”的经验判断——迄今为止所有被提出的计算模型λ 演算、递归函数、寄存器机算出来的都是同一批函数。至于描述一台图灵机可以分三个层次形式化描述要写全状态和转移函数最啰嗦也最严格实现描述用日常语言讲清楚数据怎么组织但不逐条写转移高水平描述连带子和读写头怎么管理都不提只讲算法步骤。写证明时按需要挑层次写“判定某语言”的证明通常用实现描述就够了写涉及步数或空间的分析就得下沉到形式化描述。5. 归约链排查从 A_TM 到 EQ_TM五条最容易翻车的地方5.1 映射归约一个可计算函数加上一个双向蕴含归约的直觉是“把难问题翻译成另一个问题如果另一个问题能解难问题就能解”。文档里选的是最简单也最好用的一种叫映射可归约性语言 A 映射可归约到语言 B记作 A ≤m B意思是存在一个可计算函数 f: Σ→Σ使得对每个串 ww ∈ A 当且仅当 f(w) ∈ B。这个 f 叫归约函数。可计算函数的定义要卡死存在一台图灵机 M对每个输入 w 都停机停机时带上恰好是 f(w)。两个条件缺一不可——必须处处停机f 是个全函数不能对某些输入卡住必须只留 f(w) 在带上输出唯一不能带一堆计算过程中的垃圾。很多错误证明就坏在没检查第一点如果 f 的计算本身可能不停那这个归约根本没法用来做判定。双向蕴含也是硬要求。如果只能证“w ∈ A 则 f(w) ∈ B”得不到任何结论因为 B 里还可能有 f 送不过去但照样在 B 里的串A 和 B 的成员资格就脱钩了。所以每写一条归约最该检查的是那个反方向w ∉ A 时要能保证 f(w) ∉ B。5.2 传染方向为什么结论总是“B 也不可判定”映射归约的两条定理方向感是理解它的核心前提结论直觉A ≤m B 且 A 不可判定B 不可判定难点从 A 传给了 BA ≤m B 且 B 图灵可识别A 图灵可识别能力从 B 回传给 A第一条的证明是一行逆否如果 B 可判定设 M_B 判定 B那么“先算 f(w) 再交给 M_B”就是一台判定 A 的机器f 处处停机所以这一步一定结束与 A 不可判定矛盾。第二条同理用识别 B 的机器拼出识别 A 的机器。方向感的关键在于箭头永远从“已知难”指向“待证难”。画图时把箭头画成 w ∈ A ⟺ f(w) ∈ B箭头尾部坐的必须是那个已经知道不可判定的 A。这条规矩在考场上尤其要命写反了之后整道题的论证依然读起来通顺但逻辑上是空的——它只证明了“B 的难度不高于 A”而这通常是我们已经知道的事实。经典链条都建立在这个方向上A_TM {⟨M,w⟩ | M 接受 w} 是图灵可识别但不可判定的对角线论证把它的实例改造成“M 在 w 上停机”的实例就得到停机问题 HALT_TM 不可判定同样的手法还能推到 E_TM不接受任何串的图灵机、REGULAR_TM接受的语言是正则的那台图灵机、EQ_TM两台接受相同语言的图灵机。5.3 计算历史把“机器跑起来”编码成一个串证明不可判定性时最有用的工具是把动态的过程压成静态的字符串。设 M 是图灵机、w 是串M 在 w 上的一个接受计算历史是一个格局序列 C₁, C₂, …, C_lC₁ 是起始格局C_l 是接受格局每个 C_i 都是 C_i−1 走一步的结果。拒绝计算历史同理只是最后一个格局是拒绝格局。这个定义有几个直接后果。计算历史一定是有限序列如果 M 在 w 上永不停机那就既不存在接受历史也不存在拒绝历史。确定性机器在给定输入上最多只有一条计算历史非确定型机器可以有多条每条分支各对应一条。正因为有这个编码“M 是否接受 w”就变成了“存不存在一个合法的格局序列”也就是一个关于字符串的匹配问题可以交给别的语言去判。线性有界自动机是这套工具的最佳展台。它是一台被限制的图灵机读写头不许离开输入区想往左越过左端点时原地不动和普通图灵机对待左端点的方式一样。限制带来一个致命后果格局数变成有限的状态 × 位置 × 带内容的所有组合。既然有限A_LBA给定 LBA 是否接受给定串就是可判定的——把所有格局铺开成图跑一遍可达性就行。但 E_LBA这台 LBA 是否不接受任何串就是不可判定的因为被问的不再是某一个固定长度的输入而是“所有可能的输入串”串长无界格局图跟着无界有限搜索这招就废了。注意A_LBA 可判定、E_LBA 不可判定本文还有配套的精品资源点击获取 
长河君 · 2026/10/27 10:42:58 · 阅读 1.2k 从有穷自动机到图灵机：记忆结构决定计算能力边界
简介这份《计算理论知识点.docx》面向哈尔滨工程大学计算理论期末备考的计算机专业学生也适合需要快速回顾形式语言与可计算性基础的读者用条目化方式梳理自动机、图灵机、语言理论与计算复杂度等核心考点帮助在考前集中背诵结论并查漏补缺。压缩包仅含1个docx文档大小约18KB篇幅轻便适合打印或导入平板反复翻阅。文档围绕DFA与NFA等价、正则语言封闭性、上下文无关语言与下推自动机、图灵可识别与可判定、判定器、可计算函数、映射归约以及P、NP、SAT、3SAT等高频知识点展开强调定义与判定条件的对应关系便于快速定位易混概念。已有551人学习适合期末冲刺时配合教材和习题使用也可作为章节复习前的提纲对易混的判定条件与归约关系可反复对照记忆。1. 加资源不变强、砍资源才变强计算理论里那条反直觉的分界线计算理论里最反直觉的一件事是给机器加资源能力几乎不涨砍资源能力反而涨。给图灵机多加几条带子、多装几个读写头、放开非确定性让它同时走多条分支这三样全加上去它能判定的语言集合一个都没变大——多带等价于单带非确定等价于确定。反过来把读写头拴死在输入区不许越界这台被削弱的线性有界自动机接受问题反倒成了可判定的格局总数有限搜得完。这条分界线值不值得搞懂取决于你想“背下来”还是想“推出来”。这份文档把结论按有穷自动机、上下文无关文法、图灵机、可判定性、复杂性一条条列全了它们压缩的是同一件事机器的记忆结构决定它的能力边界。只背结论换个设问就会错知道记忆结构怎么限制机器结论遇到没见过的题也能现推。下面按这条线索从最弱的有穷自动机往上走。2. 正则语言的三张脸为什么 DFA、NFA、正则表达式总是同时出现2.1 五元组里那个 δ决定了 DFA 只能记住有限个事实确定型有穷自动机写成五元组 (Q, Σ, δ, q0, F)其中 δ: Q×Σ→Q 是一个全函数给定当前状态和一个输入符号下一个状态唯一确定。关键不在“确定”而在 Q 是有限集。整台机器的记忆就是“我现在处在哪个状态”状态数一旦固定它能记住的事实就固定了。这个限制很硬。判断“串是否以 1 结尾”只要 2 个状态判断“串里 1 的个数是不是 3 的倍数”要 3 个状态取模就够了但判断 {0ⁿ1ⁿ | n≥0} 就不行——n 可以任意大机器必须记住“已经读了多少个 0”而这是无穷多种可能塞不进有限个状态。教材里的泵引理就是把这句话形式化p 个状态的机器读长度 ≥p 的串走 p1 步必然重复某个状态中间那段读过的内容可以任意重复或删掉而判断结果不变于是“必须精确计数”的语言全被排除。提示很多教材把 δ 定义成部分函数允许某些 (状态, 符号) 没有转移。这在单独描述 DFA 时没问题但一旦要构造补运算就会出问题后面 2.3 节会踩到这个坑。2.2 子集构造NFA 的“猜测”怎么变成 DFA 的“确定”非确定型有穷自动机的转移函数是 δ: Q×Σε→P(Q)输出的是一个状态集合还允许 ε 转移不读输入就跳。它的接受条件是“存在某条路径走到接受状态”也就是它天生带“猜”的能力。直觉上它比 DFA 强但结论是两者等价桥就是子集构造——把“所有可能处于的状态”打包成一个 DFA 状态。def subset_construct(nfa): start eps_closure({nfa.q0}) # 起始状态先做 ε 闭包 dfa_id {frozenset(start): 0} # DFA 的一个状态 NFA 状态集合 queue, trans [frozenset(start)], {} while queue: cur queue.pop(0) for a in nfa.sigma: # 只遍历真实字母ε 不进这个循环 nxt eps_closure(move(cur, a)) # movecur 中状态经 a 能到达的所有状态 if nxt not in dfa_id: # 只保留可达子集不做全幂集展开 dfa_id[nxt] len(dfa_id) queue.append(nxt) trans[(dfa_id[cur], a)] dfa_id[nxt] accept {i for s, i in dfa_id.items() if s nfa.accept} return dfa_id, trans, accept # accept 按“集合里含 NFA 接受态”判定参数和逻辑说明eps_closure求的是不读输入就能到达的状态闭包move只走一个真实符号两者必须分开否则会把 ε 路径重复计入。nfa.sigma不含 ε 是关键细节——ε 不是输入字母表里的字符把它放进外层循环会导致构造出的 DFA 转移表多出一列永远用不到的边。状态数上界是 2^|Q|实际只建从起始集合可达的那些通常远小于上界但最坏情况下的指数膨胀是真实存在的这也是为什么工程里的正则引擎宁可保留 NFA 模拟 Thompson 构造 并行状态集合也不真去做确定化。注意这个构造同时证明了“语言是正则的当且仅当存在 NFA 识别它”。方向是DFA 是 NFA 的特例一个状态集合退化成单元素集NFA 又能确定化成 DFA两头一夹就闭合了。2.3 封闭性为什么用乘积构造证明星号为什么要靠 ε 边正则语言在并、连接、星号下封闭是文档里反复出现的结论。并和交的证明靠乘积构造两台 DFA 同时跑状态是序对 (q1, q2)转移逐分量进行 δ((q1,q2), a) (δ1(q1,a), δ2(q2,a))接受条件按要证的运算挑。运算状态集合接受条件A ∪ BQ₁×Q₂q₁∈F₁ 或 q₂∈F₂A ∩ BQ₁×Q₂q₁∈F₁ 且 q₂∈F₂A − BQ₁×Q₂q₁∈F₁ 且 q₂∉F₂¬AQ₁先补全死状态q₁∉F₁注意表格最后一行括号里的“先补全死状态”如果原机器的 δ 是部分的某些串根本走不到任何状态取反 F 之后这些串依然不被接受补集就算错了。解决办法是加一个吸收状态把所有缺失的转移都指向它让它非接受再取反。连接和星号没法用乘积构造做因为“前一段在哪结束、后一段在哪开始”这个切分点不确定。所以引入带 ε 边的 NFA连接是把 M₁ 的每个接受状态用 ε 连到 M₂ 的起始状态星号是在外面套一个新起始状态ε 连到旧起始旧接受状态 ε 连回旧起始。三种封闭运算对应三种 ε 连线方式正则表达式的三个基本运算并、连接、星号刚好就是这三条构造。换句话说正则表达式的语法不是随便定的它的三种组合子之所以够用是因为它们各自对应一个可构造的自动机拼接动作多一个少一个都会破坏这套对应关系。3. 下推自动机与乔姆斯基范式一个栈为什么刚好够用3.1 从 A → aB 到 A → BC乔姆斯基范式在拆一棵树上下文无关文法写成四元组 (V, Σ, R, S)产生式形如 A → α左边必须是单个变量右边是变量和终结符组成的任意串。语言里的每个串对应一棵推导树树根是起始符号 S叶子从左到右拼成这个串。上下文无关的意思是不管 A 出现在推导的什么位置把它重写成 α 的规则都成立不需要看 A 的左右邻居。乔姆斯基范式把产生式压缩成两种形状A → BC两个变量和 A → a单个终结符外加一种特例——如果 ε 在语言里允许 S → ε且 S 不出现在任何右部。任何上下文无关文法都能机械地转成这个形状三步走先把 A → BCD 这种长右部拆成 A → BX、X → CD再把终结符混在长右部里的地方换成一个专门产生它的变量 T_a → a最后消掉 ε 产生式和 A → B 这种单位产生式。这套规范化的价值不在“好看”而在它把推导树掰成了严格的二叉树。一棵有 n 个叶子的满二叉树恰好有 n−1 个内部节点对应 n−1 次 A → BC 类型的推导加上 n 次 A → a 把叶子生成出来长度为 n 的串在任何乔姆斯基范式文法里的推导步数正好是 2n−1。这个数字是很多证明的支点它意味着“枚举所有推导”是一棵有限的、深度有界的树可以暴力搜也可以从长度为 1 的子串往上填表——CYK 算法就是借这个结构在 O(n³) 里判成员资格。这也是文档里“每一个上下文无关语言都是 P 类”的来源。3.2 栈的读写策略记忆结构从“有限个格子”变成“一条后进先出的带”下推自动机写得比有穷自动机多一个栈(Q, Σ, Γ, δ, q0, Z₀, F)转移函数 δ: Q×Σε×Γε → P(Q×Γε)第三个输入参数是当前栈顶符号输出可以往栈上压一串符号。栈的规则是后进先出只有栈顶可见、可弹、可压。这个记忆结构刚好对上“嵌套配对”这类语言。判断 {0ⁿ1ⁿ} 时读 0 就压栈读 1 就弹栈最后栈里只剩初始符号 Z₀ 就接受——栈的深度天然记录着“已经读了多少个 0”。有穷自动机做不到这一点因为它的“计数器”只能是有限个状态图灵机不需要专门设计就能做因为带子可以来回移动。栈卡在中间容量无界但只能从一头进出。这个限制也能解释为什么栈不够用。{0ⁿ1ⁿ2ⁿ} 不是上下文无关的理由是栈只有一个顶压 0 的计数会被后面 1 的计数覆盖掉两种计数在同一个栈上互相打架。用一个栈记两件事必然有一件记不住。3.3 非确定性在这里不再是免费的NPDA 与 DPDA 不等价文档里说一个语言是上下文无关的当且仅当存在一台下推自动机识别它。这里有个容易被忽略的差异这个结论里的下推自动机是非确定的。有穷自动机那边非确定型和确定型等价子集构造就能抹掉“猜”的能力下推自动机这边等价的结论不成立确定型下推自动机识别的语言有时叫 DCFL是上下文无关语言的真子集。机制上的原因很清楚。子集构造之所以可行是因为“NFA 当前可能处于的状态集合”虽然是个集合但它是有限集 Q 的子集天生塞得进有限个 DFA 状态里。放到下推自动机上非确定型机器在某一时刻“可能处于的格局”里包含的是栈内容而栈内容有无穷多种这个集合塞不进任何有限结构构造就断了。非确定性在这里没法用枚举抹平只能真留着。提示非确定性是否“免费”取决于你把它当作状态集合还是当作搜索分支。在可判定性层面它免费后面 4.3 节会说非确定图灵机等价于确定图灵机在时间层面它不免费指数代价在栈结构这就连语言类都改变了。还有一条层级要记住每一个正则语言都是上下文无关的。构造很直接——把 DFA 的每个状态 q 变成一个变量 A_q对每条 δ(q,a)r 加一条 A_q → aA_r接受状态再加 A_q → ε。反过来不成立{0ⁿ1ⁿ} 就是分界线上那个反例。4. 格局与判定器图灵机“循环”这件事到底黑在哪4.1 格局把“状态 带内容 读写头位置”打包成一个瞬间快照图灵机的形式定义是 (Q, Σ, Γ, δ, q0, q_accept, q_reject)δ: Q×Γ → Q×Γ×{L,R}即当前状态加读写头下的符号决定新状态、写回的符号和左移还是右移。注意 δ 在 q_accept 和 q_reject 上没有定义这两个状态是“停机”的语义落点。计算过程里任一时刻的完整快照就是把当前状态、带内容、读写头位置三者合起来这叫格局。形式化地写成 u q v 或者 u q a vu 是读写头左边的串q 是当前状态v 是从读写头位置开始往右到最右非空白符号的串。这个写法很省因为它默认读写头左边和右边远处全是空白而空白符号是无限供应的。格局的总数直接决定了一台机器的“可搜索性”。如果带子只用了有限个格子、读写头被限制在输入区内线性有界自动机就是这种情况格局数是 |Q| × n × |Γ|ⁿn 是输入长度这是一个有限的数。既然有限从起始格局能不能走到接受格局就是一张有限图上的路径问题暴力搜一定能出结果。反过来普通图灵机的带子可以越写越长格局数没有上界这张图是无限的“能不能走到接受格局”就不再是有限搜索能回答的问题——这就是后面 5.3 节里可判定与不可判定的真正分水岭。4.2 判定器与识别器停机承诺值多少钱在输入上跑一台图灵机结果只有三种接受、拒绝、循环。这里的循环不是“原地重复同样的步骤”而是“永不停机”可能一直在往右走、一直在写新的符号你看着它一直在动就是不知道它到底会不会停。图灵可识别的语言递归可枚举语言只要求“存在一台图灵机对语言里的串最终接受”对语言外的串没有任何承诺它可能拒绝也可能一直跑下去。图灵可判定的语言递归语言要求更强存在一台机器对所有输入都停机接受或拒绝都有明确答案。这种“所有输入都停机的图灵机”就是判定器。判定器之所以被单独拎出来是因为“区分循环和跑得久”这件事没有通用算法。你盯着机器跑到第 10¹² 步它可能下一步就接受也可能永远不。工程里可以用超时来兜底理论上没有一个上界能保证“过了这个界还没停就是循环”。所以我们宁可讨论“保证停机”的机器也不讨论“有可能循环”的机器。这也解释了为什么文档里要强调那一对结论每一个可判定语言都是图灵可识别的反过来不成立。还有一个非常实用的等价刻画一个语言是可判定的当且仅当它既是图灵可识别的也是补图灵可识别的。做法是让两台识别器并行跑输入串 w 交替喂给两边各走一步哪边先接受就立刻给出答案。因为 w 要么在语言里、要么在补集里两边至少有一台会在有限步内接受所以这个并行过程一定停机而且它同时给出了“是”和“否”的判决。4.3 多带、非确定与三种描述层次加资源为什么不改变能力多带图灵机每条带子有自己的读写头看起来比单带强一大截。等价性证明的做法是把 k 条带子编码到一条带上带子划分成 k 条“道”每条道对应一个虚拟带道与道之间用分隔符隔开每个虚拟读写头的位置用带标记表示。模拟一步需要扫过整段被用到的区域单次代价 O(t)跑到 t 步总代价 O(t²)。这就是文档里那条“t(n) 时间的多带图灵机与 O(t²(n)) 时间的单带图灵机等价”的来源。非确定型图灵机等价于确定型图灵机做法是广度优先遍历格局树用三条带子一条存输入一条当队列存待搜的格局一条当工作区。一条分支的地址就是一串选择编号模拟时按编号在输入上重走一遍。代价是时间从 t 涨到 b^{O(t)}b 是最大分支数。能力没变代价变了——这条差别在第 6 章会成为 P 与 NP 之间那道墙。支撑这一整套等价性证明的是丘奇-图灵论题算法这个直观概念就是图灵机可计算。它不是定理没有证明它是“形式化定义选对了”的经验判断——迄今为止所有被提出的计算模型λ 演算、递归函数、寄存器机算出来的都是同一批函数。至于描述一台图灵机可以分三个层次形式化描述要写全状态和转移函数最啰嗦也最严格实现描述用日常语言讲清楚数据怎么组织但不逐条写转移高水平描述连带子和读写头怎么管理都不提只讲算法步骤。写证明时按需要挑层次写“判定某语言”的证明通常用实现描述就够了写涉及步数或空间的分析就得下沉到形式化描述。5. 归约链排查从 A_TM 到 EQ_TM五条最容易翻车的地方5.1 映射归约一个可计算函数加上一个双向蕴含归约的直觉是“把难问题翻译成另一个问题如果另一个问题能解难问题就能解”。文档里选的是最简单也最好用的一种叫映射可归约性语言 A 映射可归约到语言 B记作 A ≤m B意思是存在一个可计算函数 f: Σ→Σ使得对每个串 ww ∈ A 当且仅当 f(w) ∈ B。这个 f 叫归约函数。可计算函数的定义要卡死存在一台图灵机 M对每个输入 w 都停机停机时带上恰好是 f(w)。两个条件缺一不可——必须处处停机f 是个全函数不能对某些输入卡住必须只留 f(w) 在带上输出唯一不能带一堆计算过程中的垃圾。很多错误证明就坏在没检查第一点如果 f 的计算本身可能不停那这个归约根本没法用来做判定。双向蕴含也是硬要求。如果只能证“w ∈ A 则 f(w) ∈ B”得不到任何结论因为 B 里还可能有 f 送不过去但照样在 B 里的串A 和 B 的成员资格就脱钩了。所以每写一条归约最该检查的是那个反方向w ∉ A 时要能保证 f(w) ∉ B。5.2 传染方向为什么结论总是“B 也不可判定”映射归约的两条定理方向感是理解它的核心前提结论直觉A ≤m B 且 A 不可判定B 不可判定难点从 A 传给了 BA ≤m B 且 B 图灵可识别A 图灵可识别能力从 B 回传给 A第一条的证明是一行逆否如果 B 可判定设 M_B 判定 B那么“先算 f(w) 再交给 M_B”就是一台判定 A 的机器f 处处停机所以这一步一定结束与 A 不可判定矛盾。第二条同理用识别 B 的机器拼出识别 A 的机器。方向感的关键在于箭头永远从“已知难”指向“待证难”。画图时把箭头画成 w ∈ A ⟺ f(w) ∈ B箭头尾部坐的必须是那个已经知道不可判定的 A。这条规矩在考场上尤其要命写反了之后整道题的论证依然读起来通顺但逻辑上是空的——它只证明了“B 的难度不高于 A”而这通常是我们已经知道的事实。经典链条都建立在这个方向上A_TM {⟨M,w⟩ | M 接受 w} 是图灵可识别但不可判定的对角线论证把它的实例改造成“M 在 w 上停机”的实例就得到停机问题 HALT_TM 不可判定同样的手法还能推到 E_TM不接受任何串的图灵机、REGULAR_TM接受的语言是正则的那台图灵机、EQ_TM两台接受相同语言的图灵机。5.3 计算历史把“机器跑起来”编码成一个串证明不可判定性时最有用的工具是把动态的过程压成静态的字符串。设 M 是图灵机、w 是串M 在 w 上的一个接受计算历史是一个格局序列 C₁, C₂, …, C_lC₁ 是起始格局C_l 是接受格局每个 C_i 都是 C_i−1 走一步的结果。拒绝计算历史同理只是最后一个格局是拒绝格局。这个定义有几个直接后果。计算历史一定是有限序列如果 M 在 w 上永不停机那就既不存在接受历史也不存在拒绝历史。确定性机器在给定输入上最多只有一条计算历史非确定型机器可以有多条每条分支各对应一条。正因为有这个编码“M 是否接受 w”就变成了“存不存在一个合法的格局序列”也就是一个关于字符串的匹配问题可以交给别的语言去判。线性有界自动机是这套工具的最佳展台。它是一台被限制的图灵机读写头不许离开输入区想往左越过左端点时原地不动和普通图灵机对待左端点的方式一样。限制带来一个致命后果格局数变成有限的状态 × 位置 × 带内容的所有组合。既然有限A_LBA给定 LBA 是否接受给定串就是可判定的——把所有格局铺开成图跑一遍可达性就行。但 E_LBA这台 LBA 是否不接受任何串就是不可判定的因为被问的不再是某一个固定长度的输入而是“所有可能的输入串”串长无界格局图跟着无界有限搜索这招就废了。注意A_LBA 可判定、E_LBA 不可判定本文还有配套的精品资源点击获取