计算理论复习主线：从DFA、PDA到图灵机与可判定性

简介：《计算理论知识点.docx》是一份面向计算机专业学生、尤其针对哈尔滨工程大学计算理论期末复习整理的知识点速记文档，适合需要短期集中背诵、梳理考点的备考者使用。压缩包内共1个docx文件，约18KB，体量轻便，便于打印或在手机、平板上随时翻阅。文档围绕自动机理论、图灵机、语言理论、计算复杂度与其他延伸概念五部分展开，以结论式条目罗列正则语言与有穷自动机的等价关系、图灵可识别与可判定语言的区别、判定器与格局的定义、丘奇—图灵论题、映射归约与多项式时间归约、P与NP及SAT、3SAT、CLIQUE等典型问题的归属，几乎覆盖期末简答与证明题的常见考点。已有551人学习，适合考前对照课堂笔记快速过一遍定义与判定结论，补上容易混淆的等价条件和不可判定问题清单。

1. 知识地图：这门课其实在比“四台机器谁记得多”

计算理论期末复习最坑的地方，是它看起来像四十多条互不相干的结论，背下来也不会串。其实整门课只有一条主线：给机器加记忆，看它能多认出哪些语言。有穷自动机的记忆只有“当前是哪个状态”；下推自动机多了一个栈；图灵机多了一条能来回读写的带子；最后再把带子加上时间、空间的预算，就进入复杂度。每加一层记忆，就多一个语言类，也多一批封闭运算和可判定问题。

所以复习任何一个结论，都先问四件事：谁识别它、它对哪些运算封闭、它的成员问题可不可判定、要花多少资源。适合已经上过课、手上有讲义但串不起来的人；完全零基础直接读会有点跳。

2. 语言层级：DFA、PDA、图灵机各自认得出什么

这一章是整门课的地基。同一个字符串集合，换一台更强的机器就能认出来，认不出来的原因往往只是“记忆不够”。把每一层都按“识别装置—封闭运算—成员问题”三段来记，后面图灵机和复杂度的结论才有地方挂。

2.1 正则语言：DFA、NFA、正则表达式三方等价

有穷自动机是五元组 (Q, Σ, δ, q0, F)：状态集合、字母表、转移函数、起始状态、接受状态集合。确定的 DFA 每读一个符号只有一条出路；非确定的 NFA 对同一个符号可以有多条出路，还能不读符号就跳（ε 转移）。课上最值钱的一句话是：每一台非确定有穷自动机都等价于一台确定型有穷自动机。等价的实现办法是子集构造，把“NFA 当前可能处在的状态集合”整体当成 DFA 的一个状态，最坏情况下状态数从 n 膨胀到 2 的 n 次方。

把三条结论叠起来看，就是正则语言的三方等价：

• 一个语言被有穷自动机识别，则它是正则语言；
• 一个语言是正则的，当且仅当有一台 NFA 识别它；
• 一个语言是正则的，当且仅当有一个正则表达式描述它。

也就是说 DFA、NFA、正则表达式是同一件事的三种写法，考试给哪一种都能转成另外两种。封闭性上必背的三条是并、连接、星号；补和交也封闭，只是讲义常塞进习题：补靠交换 DFA 的接受与非接受状态，交靠乘积构造。判断“不是正则”的常用工具是泵引理，注意它只能用来证伪，不能用来证明一个语言是正则的，这个误用率相当高。

下面这段把 DFA 的五个参数落到代码里，方便对照定义检查自己写的转移表：

# 用五元组描述 DFA，模拟它读完整串的过程 dfa = { "states": {"q0", "q1", "q2"}, "alphabet": {"0", "1"}, "delta": {("q0", "0"): "q1", ("q0", "1"): "q0", ("q1", "0"): "q1", ("q1", "1"): "q2", ("q2", "0"): "q2", ("q2", "1"): "q2"}, "start": "q0", "accept": {"q2"}, } def run_dfa(m, w): state = m["start"] for ch in w: # 一个符号一步，绝不回头 if ch not in m["alphabet"]: return False # 出现字母表外的符号，直接拒绝 state = m["delta"].get((state, ch)) if state is None: return False # 转移未定义，等价于掉进死状态 return state in m["accept"] print(run_dfa(dfa, "1011")) # 只要出现过 "11" 就停在 q2

参数怎么改：要换语言就改 accept 和 delta；delta 必须对 Σ 里每个符号都有定义（全函数），缺的那条要在代码里补一个死状态，这正是“确定的机器每一步只有一条路”的具体含义。想把这段改成 NFA，只需把 delta 的值换成状态集合，运行时维护一个集合而不是单个状态，子集构造做的就是这件事。

2.2 上下文无关语言：文法、下推自动机与乔姆斯基范式

上下文无关文法也是四元组 (V, Σ, R, S)：非终结符、终结符、规则、起始符号。规则左部永远只有一个非终结符，这就是“上下文无关”的字面意思。它对应的机器是下推自动机：一台带栈的非确定有穷自动机，栈顶决定下一步怎么走。两条方向都要背：

• 一个语言是上下文无关的，当且仅当存在一台下推自动机识别它；
• 如果一个语言被下推自动机识别，则它是上下文无关的。

乔姆斯基范式是把文法削成极简形式：每条规则要么是 A → BC（两个非终结符），要么是 A → a（一个终结符），空串另算。结论是任何一个上下文无关语言都可以用乔姆斯基范式的上下文无关文法产生。它的价值不在好看，而在于让派生树变成二叉树，于是“长度为 n 的串的派生步数”可数、可用动态规划判定，CYK 算法就是这么来的。

# 检查一个文法是否已经是乔姆斯基范式：右部要么两个非终结符，要么一个终结符 def is_cnf(g, start="S"): for lhs, rules in g.items(): for rhs in rules: if rhs == (start,) and lhs == start and len(rules) == 1: continue # 只允许起始符号推出空串 if len(rhs) == 2 and all(s in g for s in rhs): continue # A -> BC，两个都是非终结符 if len(rhs) == 1 and rhs[0] not in g: continue # A -> a，一个终结符 return False return True

参数说明：g 是“非终结符 → 右部元组列表”的字典；判断时要看右部符号是否出现在 g 的键里，以此区分终结符和非终结符。很多手写的文法看着像范式，其实某条规则右部混了个单非终结符（A → B），这一步就会返回 False，这也是改写成范式时最先要消掉的“单位规则”。

封闭性要单独记一笔：上下文无关语言在并、连接、星号下封闭，但在交和补下不封闭，这跟正则语言完全相反，是后面易错点那一章的主角之一。

2.3 层级关系：为什么正则 ⊂ 上下文无关 ⊂ 可判定

三层包含关系串起来只有三句话：每一个正则语言都是上下文无关的；每一个上下文无关语言都是可判定的；每一个可判定语言都是图灵可识别的。包含是严格的，反例要能张口就来：{0ⁿ1ⁿ} 是上下文无关但不是正则，{0ⁿ1ⁿ2ⁿ} 不是上下文无关，停机问题是图灵可识别但不可判定。

这张表最好自己默写一遍。默写时如果卡在“到底是哪个不封闭”，就从机器能力倒推：DFA 是有限状态，补运算只需翻转接受状态，代价为零；下推自动机的非确定性无法靠“翻转接受状态”消掉，所以补不封闭，交也需要两台栈，同样出不去。

3. 图灵机：格局、判定器与可判定语言清单

图灵机这一章的结论密度最高，但骨架很清晰：先把“机器此刻在干什么”形式化，再把“机器能否给个准话”分成两档，最后把常见问题的可判定性排成一张表。这三步走完，第三章和第四章的分界就出来了——判定器存在与否，决定了问题落进哪张清单。

3.1 格局与三种结局：接受、拒绝、循环

格局是图灵机计算过程中“当前状态、当前带内容、读写头当前位置”三者的组合。单独说状态没意义，单独说带子也没意义，必须三者一起才能唯一确定机器此刻的处境。起始格局是开机时的那个格局，接受格局和拒绝格局是停机后的那两个格局，中间每一步都由转移函数决定。

在输入上运行一台图灵机，可能出现三种结果：接受、拒绝、循环。这里的循环仅仅指机器不停机，不是“永远以同样的步骤重复”那个日常语义。由此推出两条常用结论：图灵机不接受有两种方式，进入拒绝状态，或者进入循环；如果 M 在 w 上永不停机，那么在 M 上既不存在接受计算历史，也不存在拒绝计算历史。

计算历史就是格局序列 C₁、C₂、…、C_l，其中 C₁ 是起始格局，C_l 是接受（或拒绝）格局，每个 C_i 都是 C_{i-1} 走一步的结果。计算历史永远是有限序列。确定型机器在任何输入上最多只有一个计算历史，非确定型机器即使只有一个输入也有多个计算历史，分别对应各个分支——这句是后面证明不可判定性时的关键抓手。

# 格局 = (当前状态, 带内容, 读写头下标)，三者缺一就说不清机器在哪 def step(config, delta, blank="_"): state, tape, head = config if state in ("q_accept", "q_reject"): # 已停机，格局不再演变 return config symbol = tape.get(head, blank) # 没写过的格子读出来是空白符 write, move, nxt = delta[(state, symbol)] # 转移函数一次给出三样东西 tape[head] = write # 改写当前格 head += 1 if move == "R" else -1 # 读写头左移或右移 return (nxt, tape, head) # 新状态 + 新带内容 + 新位置

参数说明：tape 用字典存“下标 → 符号”，所以向左走不需要特殊处理，但形式定义里带子是左端有界的，真要限制读写头不越界，就得另加判断——这正是线性界限自动机的由来。delta 的键是 (状态, 当前符号)，值依次是写入符号、移动方向、下一状态。考试让你“描述 M 在 w 上的计算历史”时，按这个格式一个个列格局，不容易漏项。

3.2 识别与判定：一字之差，隔着一整张清单

图灵可识别（又叫递归可枚举语言）：如果一个语言可能被某一台图灵机识别，则称它是图灵可识别的。注意“识别”只要求对语言内的串给出接受，对语言外的串可以拒绝，也可以一直循环。

图灵可判定（又叫递归语言）：如果一个语言能被某一台图灵机判定，则称它是图灵可判定的。判定意味着对每个输入都停机，永远不循环。这类机器叫判定器，它总是能决定接受还是拒绝。

为什么教材要单独把判定器拎出来？因为判定器有时候很难区分“进入循环”和“只是需要耗费很长时间”，在理论上你没有任何办法给这两种情况划一条线。所以宁可只讨论所有输入都停机的机器，这类机器的行为是可预期的。这条直观解释比定义本身更值得记，很多证明题的第一步就是“把 NTM 改成判定器”。

四条关系必须成组背：

• 每一个可判定语言都是图灵可识别的；
• 一个语言是图灵可识别的，当且仅当存在非确定型图灵机识别它；
• 一个语言是图灵可判定的，当且仅当存在非确定型图灵机判定它；
• 一个语言是可判定的，当且仅当它既是图灵可识别的，也是补图灵可识别的。

最后一条最容易漏。顺便把“补”的定义补齐：一个语言的补是由不在此语言中的所有串构成的语言；如果一个语言的补集是图灵可识别的，就称它是补图灵可识别的。于是 ATM 的补是不可识别的，而 ATM 本身可识别，两者一拼，可判定性就不成立——这是标准证法。

3.3 等价变形与丘奇-图灵论题：为什么可以“随手画图灵机”

考试里经常出现“多带图灵机”“非确定型图灵机”，先别慌，它们都不比单带确定型强：每一个多带图灵机等价于一个单带图灵机，非确定型图灵机也都等价于确定型图灵机。等价是“能识别同样的语言”，代价体现在时间上（第四章会给出平方和指数的换算），语言层面没有区别。

丘奇-图灵论题给的是“算法”的明确定义：凡是直觉上可计算的，都能用图灵机算。它不是一个可证的定理，而是整个学科的地基假设，所以凡是题目里写“给出一个算法”，默认就是“给出一台图灵机”。

描述层次要分清，三级从低到高：

最容易翻车的地方是层次混用：前面用高水平描述写了个“把 w 复制一份”，后面又突然开始讨论读写头位置，读起来像两台机器拼在一起。血泪经验是——一道题里选定一个层次写到底，需要细节时再补一句“这一步

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