Formal Languages

形式语言与自动机理论

形式语言基础

定义

字母表（Alphabet）：有限非空符号集合，记作 Σ。

字符串（String）：字母表上符号的有限序列。|w| 表示长度，ε 表示空串。Σ* 表示所有字符串的集合（含 ε），Σ⁺ = Σ* \ {ε}。

语言（Language）：L ⊆ Σ*，即字符串的任意集合。

基本运算：

• 连接：L₁·L₂ = {w₁w₂ | w₁ ∈ L₁, w₂ ∈ L₂}
• Kleene 闭包：L* = ∪ᵢ₌₀∞ Lⁱ
• 正闭包：L⁺ = ∪ᵢ₌₁∞ Lⁱ

Chomsky 文法层次

定义：文法 G = (V, Σ, R, S)，其中 V 是非终结符，Σ 是终结符，R 是产生式规则，S 是起始符号。

定理（Chomsky 范式 — CNF）：任意 CFG 可转换为 Chomsky 范式，其中所有产生式形如 A → BC 或 A → a。

证明思路：

1. 消除 ε-产生式（除 S → ε 外）
2. 消除单一产生式（A → B）
3. 消除无用符号（不可达/不可推导终结符的）
4. 将 A → X₁X₂...Xₖ（k ≥ 3）拆分为二元产生式链

复杂度：O(|G|) 转换，|G| 是文法大小。

闭包性质

定理：各语言类在以下运算下的闭包性：

关键证明思路：

• 正则语言对交封闭：构造乘积自动机 M = (Q₁×Q₂, Σ, δ, (q₀₁,q₀₂), F₁×F₂)
• CFL 对交不封闭：反例 L₁ = {aⁿbⁿcᵐ} ∩ L₂ = {aᵐbⁿcⁿ} = {aⁿbⁿcⁿ}，后者非 CFL（用 Pumping Lemma 证）

应用：证明某语言不属于某类、编译器设计。

有限自动机

DFA（确定性有限自动机）

定义：DFA M = (Q, Σ, δ, q₀, F)，其中：

• Q：有限状态集
• Σ：输入字母表
• δ: Q × Σ → Q：转移函数（完全定义）
• q₀ ∈ Q：初始状态
• F ⊆ Q：接受状态集

扩展转移函数：δ̂: Q × Σ* → Q

• δ̂(q, ε) = q
• δ̂(q, wa) = δ(δ̂(q, w), a)

语言：L(M) = {w ∈ Σ* | δ̂(q₀, w) ∈ F}

定理：DFA 与 NFA 识别能力等价。

NFA（非确定性有限自动机）

定义：NFA M = (Q, Σ, δ, q₀, F)，其中 δ: Q × Σ → P(Q)（幂集）。

接受条件：w ∈ L(M) 当且仅当存在一条从 q₀ 到某 F 中状态的路径标记为 w。

定理（Rabin-Scott 子集构造）：对每个 n 状态 NFA，存在至多 2ⁿ 状态的等价 DFA。

证明思路：

• DFA 状态 = NFA 状态的子集
• δ'(S, a) = ∪_{q∈S} δ(q, a)
• 初始状态 = {q₀}
• 接受状态 = {S | S ∩ F ≠ ∅}

算法（子集构造）：

SubsetConstruction(NFA N):
  Dstates = {ε-closure({q₀})}
  unmarked = [ε-closure({q₀})]
  while unmarked 非空:
    T = unmarked.pop()
    for each a ∈ Σ:
      U = ε-closure(move(T, a))
      if U ∉ Dstates:
        Dstates.add(U)
        unmarked.append(U)
      Dtran[T, a] = U
  return DFA(Dstates, Σ, Dtran, ε-closure({q₀}), {T | T ∩ F ≠ ∅})

复杂度：O(2ⁿ · |Σ|)，最坏情况指数级。

紧致性：存在 n 状态 NFA，最小等价 DFA 恰有 2ⁿ 状态。例：Lₙ = {w ∈ {0,1}* | w 的倒数第 n 个字符为 1}。

NFA → DFA（子集构造）

见上文。补充 ε-closure 计算：

ε-closure 算法：

ε-closure(T):
  stack = T 的所有状态
  result = T
  while stack 非空:
    t = stack.pop()
    for each u ∈ δ(t, ε):
      if u ∉ result:
        result.add(u)
        stack.push(u)
  return result

复杂度：O(n²) 计算 ε-closure，n 是 NFA 状态数。

DFA 最小化（Hopcroft 算法）

定义：两个 DFA 等价 iff L(D₁) = L(D₂)。最小 DFA 在同构意义下唯一。

定理（Myhill-Nerode）：语言 L 的最小 DFA 状态数 = ∼_L 的等价类数，其中 x ∼_L y 当且仅当 ∀z ∈ Σ*, xz ∈ L ⇔ yz ∈ L。

算法（Hopcroft）：

Minimize(DFA D = (Q, Σ, δ, q₀, F)):
  P = {F, Q\F}  // 初始划分
  W = {min(|F|, |Q\F|)} 对应的集合
  while W 非空:
    A = W.pop()
    for each c ∈ Σ:
      X = {q ∈ Q | δ(q, c) ∈ A}
      for each Y ∈ P where X∩Y ≠ ∅ and Y\X ≠ ∅:
        替换 Y 为 Y₁ = X∩Y 和 Y₂ = Y\X
        if Y ∈ W:
          替换 Y 为 Y₁, Y₂（选较小者入 W）
        else:
          W.add(|Y₁| ≤ |Y₂| ? Y₁ : Y₂)
  合并等价状态，构建最小 DFA

复杂度：O(|Σ| · |Q| · log |Q|)。

应用：正则表达式引擎优化、协议验证。

Moore 机与 Mealy 机

定义：

• Moore 机：输出仅依赖于当前状态。M = (Q, Σ, Δ, δ, λ, q₀)，λ: Q → Δ。
• Mealy 机：输出依赖于当前状态和输入。λ: Q × Σ → Δ。

定理：Moore 机与 Mealy 机可互相转换。n 状态 Mealy 机 → n 状态 Moore 机（状态分裂），反之亦然。

证明思路：

• Moore → Mealy：λ'(q, a) = λ(δ(q, a))
• Mealy → Moore：按不同输出分裂状态，每个 (q, output) 对一个新状态

应用：数字电路设计、协议状态机、词法分析器。

双向自动机（2DFA）

定义：2DFA 的读写头可左右移动。转移函数 δ: Q × Σ → Q × {L, R, S}。

定理：2DFA 与 DFA 识别能力等价。

证明思路：用跨越序列（crossing sequence）模拟 2DFA。每个边界位置记录读写头经过时的状态序列，可证明 DFA 状态数为指数级。

复杂度：n 状态 2DFA → O(2ⁿ) 状态 DFA。

应用：理论意义大于实际，用于证明自动机模型等价性。

正则表达式

基本运算与扩展运算

基本运算：

• 连接：R₁R₂
• 选择：R₁|R₂（或 R₁∪R₂）
• Kleene 闭包：R*

扩展运算：

• 正闭包：R+ ≡ RR*
• 可选：R? ≡ R|ε
• 字符类：[a-z], [0-9], [^0-9]
• 重复：R{n,m} ≡ R{n}(R?){m-n}
• 通配符：. ≡ Σ 中任一字符
• 锚点：^(行首), $(行尾)

定理（Kleene）：L 是正则语言 ⟺ L 可用正则表达式描述。

证明思路：

• RE → FA：结构归纳构造 ε-NFA（Thompson 构造）
• FA → RE：状态消除法（或 Arden 引理）

Thompson 构造

算法：将正则表达式 R 转换为 ε-NFA N，使得 L(N) = L(R)。

基础情况：
  R = ∅: 两个状态，无转移
  R = ε: 两个状态，ε 转移
  R = a:  q₀ --a--> q₁

归纳情况：
  R = R₁R₂（连接）：
    N₁ 的接受状态 --ε--> N₂ 的初始状态
    N₁ 的初始状态为新初始
    N₂ 的接受状态为新接受

  R = R₁|R₂（选择）：
    新 q₀ --ε--> N₁.q₀
    新 q₀ --ε--> N₂.q₀
    N₁.q_f --ε--> 新 q_f
    N₂.q_f --ε--> 新 q_f

  R = R₁*（闭包）：
    新 q₀ --ε--> N₁.q₀
    新 q₀ --ε--> 新 q_f
    N₁.q_f --ε--> N₁.q₀
    N₁.q_f --ε--> 新 q_f

复杂度：O(|R|) 状态数，|R| 是正则表达式长度。

正则等价性判定

定理：给定两个正则表达式 R₁, R₂，判定 L(R₁) = L(R₂) 是可判定的。

算法：

1. R₁ → ε-NFA N₁ → DFA D₁ → 最小化 D₁'
2. R₂ → ε-NFA N₂ → DFA D₂ → 最小化 D₂'
3. 判定 D₁' ≅ D₂'（同构检查）

复杂度：O(2ⁿ)（最坏），n = |R₁| + |R₂|。实际上多数情况远快于指数。

Pumping Lemma（正则语言）

定理：若 L 是正则语言，则存在常数 p（pumping length），使得 ∀w ∈ L, |w| ≥ p，可分解 w = xyz 满足：

1. |xy| ≤ p
2. |y| > 0
3. ∀k ≥ 0, xyᵏz ∈ L

证明思路：设 L 由 p 状态 DFA 接受。接受 w 时经过 p+1 个状态，必有状态重复（鸽巢原理），重复段即为 y。

应用（证明非正则）：

例：L = {aⁿbⁿ | n ≥ 0} 非正则。

假设 L 正则，pumping length = p。
取 w = aᵖbᵖ ∈ L，|w| ≥ p。
分解 w = xyz，|xy| ≤ p，故 y = aʲ (j > 0)。
则 xy²z = aᵖ⁺ʲbᵖ ∉ L。矛盾。

更多非正则语言例子：

• {ww | w ∈ {0,1}*}（回文）
• {aⁿ² | n ≥ 0}（平方串）
• {aᵖ | p 是素数}

推广（Myhill-Nerode 定理）： L 是正则语言 ⟺ ∼_L 的等价类数有限。

用于证明非正则：找到无限多个 ∼_L 不等价的串。

例：对 L = {aⁿbⁿ}，{aⁱ | i ≥ 0} 中任意两个 aⁱ, aʲ（i ≠ j）不满足 ∼_L（取 z = bⁱ），故 ∼_L 有无穷多等价类。

下推自动机

确定性 PDA（DPDA）

定义：DPDA M = (Q, Σ, Γ, δ, q₀, Z₀, F)，其中：

• Q：有限状态集
• Σ：输入字母表
• Γ：栈字母表
• δ: Q × (Σ ∪ {ε}) × Γ → Q × Γ*（至多一个转移）
• q₀：初始状态
• Z₀：初始栈符号
• F：接受状态集

限制：δ(q, a, X) 和 δ(q, ε, X) 不能同时有定义（确定性要求）。

定理：DPDA 识别的语言类（DCFL）严格包含于 NPDA 识别的语言类（CFL）。

例：L = {wwᴿ | w ∈ {0,1}*} 是 CFL（NPDA 可识别）但非 DCFL。

非确定性 PDA（NPDA）

定义：δ: Q × (Σ ∪ {ε}) × Γ → P(Q × Γ*)（转移集合）。

接受方式：

1. 接受状态：{w | (q₀, w, Z₀) ⊢* (q, ε, γ), q ∈ F}
2. 空栈：{w | (q₀, w, Z₀) ⊢* (q, ε, ε)}（可选 q）

定理：两种接受方式等价（可互相转换）。

例（识别 {aⁿbⁿ}）：

δ(q₀, a, Z₀) = {(q₀, AZ₀)}
δ(q₀, a, A)  = {(q₀, AA)}
δ(q₀, b, A)  = {(q₁, ε)}
δ(q₁, b, A)  = {(q₁, ε)}
δ(q₁, ε, Z₀) = {(q₁, ε)}  // 空栈接受

PDA ↔ CFG 构造

定理：CFL = NPDA 识别的语言类。

CFG → PDA 构造：

给定 CFG G = (V, Σ, R, S)，构造 NPDA：

状态：{q}
初始栈：S$
转移规则：
  对每个 A → γ ∈ R：δ(q, ε, A) 包含 (q, γ)
  对每个 a ∈ Σ：δ(q, a, a) 包含 (q, ε)
  δ(q, ε, $) 包含 (q, ε)  // 空栈接受

直觉：PDA 模拟最左推导，栈存储未展开的文法符号。

PDA → CFG 构造：

给定 PDA M = (Q, Σ, Γ, δ, q₀, Z₀, F)：

对每对状态 p, q ∈ Q 和栈符号 X，定义非终结符 [p, X, q]
含义：从状态 p、栈顶 X 开始，到达状态 q 且弹出 X

产生式规则：
  对 δ(p, a, X) 包含 (r, Y₁Y₂...Yₖ)：
    [p, X, qₖ] → a [r, Y₁, q₁] [q₁, Y₂, q₂] ... [qₖ₋₁, Yₖ, qₖ]
    对所有 q₁, q₂, ..., qₖ ∈ Q 的组合

  对 δ(p, a, X) 包含 (r, ε)：
    [p, X, r] → a

起始符号：[q₀, Z₀, q]（q ∈ F 或空栈接受时的 q）

复杂度：CFG → PDA 是 O(|G|)；PDA → CFG 是 O(|Q|ⁿ · |Γ|)，其中 n 是最大栈压入长度。

CYK 算法（CFG 句子识别）

定义：给定 CFG G（CNF 形式）和字符串 w = a₁a₂...aₙ，判定 w ∈ L(G)。

算法：

输入：CNF 文法 G = (V, Σ, R, S)，字符串 w = a₁...aₙ
输出：w ∈ L(G)?

// table[i][j] = {A ∈ V | A ⇒* aᵢ...aⱼ}
for i = 1 to n:
  table[i][i] = {A | A → aᵢ ∈ R}

for l = 2 to n:       // 子串长度
  for i = 1 to n-l+1: // 起点
    j = i + l - 1      // 终点
    table[i][j] = ∅
    for k = i to j-1:  // 分割点
      for each A → BC ∈ R:
        if B ∈ table[i][k] and C ∈ table[k+1][j]:
          table[i][j] ← table[i][j] ∪ {A}

return S ∈ table[1][n]

复杂度：O(n³ · |G|)，其中 n = |w|。

定理：CFL 成员判定是多项式时间可解的（CYK 算法）。

应用：自然语言处理（CYK 解析器）、RNA 二级结构预测。

LL(1)/LR(1) 与 PDA 的关系

定理：

• LL(1) 分析器对应确定性 PDA（预测型）
• LR(1) 分析器对应确定性 PDA（移进-归约型）

LL(1) PDA：

栈存储：剩余待匹配的文法符号序列（栈顶在左）
操作：
  栈顶为终结符 a：匹配输入 a，弹出
  栈顶为非终结符 A：查分析表 M[A, lookahead]，弹出 A，压入产生式右部（逆序）

LR(1) PDA：

栈存储：状态序列（隐含已识别的文法前缀）
操作：
  Shift：读入输入符号，压入新状态
  Reduce：弹出产生式右部长度的状态，查 Goto 表压入新状态
  Accept：接受

Pumping Lemma（上下文无关语言）

定理（Ogden 引理 / CFL Pumping Lemma）：若 L 是 CFL，则存在常数 p，使得 ∀w ∈ L, |w| ≥ p，可将 w 分解为 w = uvxyz 满足：

1. |vxy| ≤ p
2. |vy| > 0
3. ∀k ≥ 0, uvᵏxyᵏz ∈ L

证明思路：对 CNF 文法的分析树，深度 > log₂ p 时有路径上的重复非终结符，对应 v, x, y。

应用（证明非 CFL）：

例：L = {aⁿbⁿcⁿ | n ≥ 0} 非 CFL。

假设 L 是 CFL，pumping length = p。
取 w = aᵖbᵖcᵖ。
分解 w = uvxyz，|vxy| ≤ p。
情况 1：vxy 只含 a 和 b。
  则 uv²xy²z 中 a 和 b 增多但 c 不变 → 不属于 L。
情况 2：vxy 只含 b 和 c。类似。
情况 3：vxy 只含 a 或只含 b 或只含 c。
  则 uv²xy²z 中只有一种字符增多 → 不属于 L。
矛盾。

更多非 CFL 例子：

• {ww | w ∈ {a,b}*}（复制语言）
• {aⁱbʲcᵏ | i < j < k}

图灵机

标准图灵机

定义：TM M = (Q, Σ, Γ, δ, q₀, q_accept, q_reject)，其中：

• Q：有限状态集
• Σ：输入字母表（不含 ␣）
• Γ：带字母表（␣ ∈ Γ，Σ ⊆ Γ）
• δ: Q × Γ → Q × Γ × {L, R}（部分函数）
• q₀：初始状态
• q_accept：接受状态
• q_reject：拒绝状态

语言：L(M) = {w | M 对输入 w 最终进入 q_accept}

递归可枚举语言（RE）：存在 TM 接受 L。 递归语言（Decidable）：存在 TM 接受 L 且对所有输入都停机。

多带图灵机

定义：k 带图灵机有 k 条无限带，每条带有独立的读写头。

定理：多带 TM 与单带 TM 计算能力等价。

证明思路：

• 单带模拟多带：用 # 分隔各带内容，用标记符号记录读写头位置
• k 带需要 2k 遍扫描（一遍读，一遍写）

复杂度开销：k 带时间 t(n) → 单带时间 O(t(n)²)。

非确定性图灵机（NTM）

定义：δ: Q × Γ → P(Q × Γ × {L, R})。

定理：NTM 与确定性 TM 计算能力等价。

证明思路：确定性 TM 用广度优先搜索模拟 NTM 的所有可能计算路径。

复杂度开销：NTM 时间 t(n) → DTM 时间 O(2^{O(t(n))})。

Church-Turing 论题

论题：任何"可计算"的函数都可用图灵机计算。

这不是定理，而是经验性论题——所有已知的"合理"计算模型（λ 演算、递归函数、寄存器机、马尔可夫算法、Post 系统）都与图灵机等价。

等价计算模型：

• λ 演算（Church）
• μ-递归函数（Kleene）
• 寄存器机
• Post 对应系统
• 元胞自动机（Rule 110 已证明图灵完备）

通用图灵机

定义：通用图灵机 U 满足：对任意 TM M 和输入 w，U(⟨M⟩, w) = M(w)。

构造思路：

• 将 TM M 的描述编码为字符串 ⟨M⟩
• U 读取 ⟨M⟩ 和 w
• U 在模拟带上维护 M 的状态和带内容
• 每步查找 δ 的对应条目并执行

意义：存在一个固定程序可以模拟任意程序——"可编程计算机"的理论基础。

可判定语言

定义：语言 L 是可判定的（recursive），如果存在 TM M 使得：

• w ∈ L → M 接受 w
• w ∉ L → M 拒绝 w （M 对所有输入都停机）

可判定语言示例：

1. {⟨D, w⟩ | DFA D 接受 w}：直接模拟，O(n) 步
2. {⟨D⟩ | DFA D 的语言为空}：从初始状态 BFS，检查能否到达接受状态
3. {⟨D₁, D₂⟩ | L(D₁) = L(D₂)}：最小化后比较同构
4. {⟨G, w⟩ | CFG G 生成 w}：CYK 算法
5. {⟨G⟩ | CFG G 的语言为空}：从终结符反推可达的非终结符

定理（DECIDABLE 类的闭包性质）：可判定语言对并、交、补、连接、Kleene 星封闭。

可计算性

停机问题

定义：HALT_TM = {⟨M, w⟩ | TM M 对输入 w 停机}。

定理（Turing, 1936）：停机问题是不可判定的。

证明（对角线化）：

假设存在 TM H 判定停机问题：
  H(⟨M, w⟩) = accept  如果 M(w) 停机
  H(⟨M, w⟩) = reject  如果 M(w) 不停机

构造 TM D：
  D(⟨M⟩) = 
    if H(⟨M, M⟩) = accept: loop forever
    if H(⟨M, M⟩) = reject: accept

矛盾：D(⟨D⟩) 停机 ⟺ H(⟨D,D⟩) = accept ⟺ D(⟨D⟩) 不停机。

推论：

• ATM = {⟨M, w⟩ | M 接受 w} 不可判定（但 RE）
• ATMᶜ（补）甚至不是 RE
• 空语言问题 E_TM = {⟨M⟩ | L(M) = ∅} 不可判定

归约

定义：语言 A 可归约到语言 B（A ≤ₘ B），如果存在可计算函数 f 使得 ∀w, w ∈ A ⟺ f(w) ∈ B。

定理：若 A ≤ₘ B 且 B 可判定，则 A 可判定。逆否命题：若 A 不可判定且 A ≤ₘ B，则 B 不可判定。

常见归约链：

HALT_TM ≤ₘ ATM ≤ₘ E_TM ≤ₘ EQ_TM ≤ₘ REGULAR_TM

归约示例（E_TM 不可判定）：

归约 ATM ≤ₘ E_TM：

给定 ⟨M, w⟩，构造 M'：
  M'(x):
    模拟 M(w)
    如果 M(w) 接受，则接受 x

则 L(M') ≠ ∅ ⟺ M 接受 w。
⟨M, w⟩ ∈ ATM ⟺ ⟨M'⟩ ∈ E_TMᶜ。

映射归约 vs Turing 归约：

• ≤ₘ（多一归约）：一对一函数映射
• ≤T（Turing 归约）：使用谕示机（oracle）归约，更强

Rice 定理

定理（Rice, 1953）：TM 的任何非平凡语义性质都是不可判定的。

形式化：设 P 是 TM 的语义性质（即 L(M₁) = L(M₂) ⟹ P(M₁) = P(M₂)）。若 P 非空且非全，则 {⟨M⟩ | P(M)} 不可判定。

证明思路：将 ATM 归约到 P。假设 P(M₀) 为真，P(M∅) 为假（M∅ 拒绝所有输入）。构造 M'：先模拟 M(w)，若接受则模拟 M₀(x)。

应用：直接判定以下问题不可判定——

• TM 是否接受空语言？
• TM 是否接受正则语言？
• TM 是否接受有限语言？
• 两个 TM 是否等价？

递归定理

定理（Kleene 递归定理）：对任意可计算函数 f，存在 TM e 使得 L(e) = L(f(e))。

直觉：程序可以获取自己的源代码并据此构造新程序。

证明思路：

构造 TM SELF：
  1. 计算⟨M⟩的描述（自己的代码）
  2. 输出⟨M⟩（或执行其他操作）

方法：用 quine 技巧
  定义 q(w) = 生成打印 w 再执行 w 的程序
  SELF = q(⟨q⟩)

应用：

• 自复制程序（quine）
• 证明停机问题不可判定（另一种证法）
• 计算复杂性中的对角线化论证

Post 对应问题（PCP）

定义：PCP = {⟨(t₁, b₁), (t₂, b₂), ..., (tₖ, bₖ)⟩ | 存在索引序列 i₁i₂...iₘ 使得 tᵢ₁tᵢ₂...tᵢₘ = bᵢ₁bᵢ₂...bᵢₘ}。

定理：PCP 是不可判定的。

证明思路：将 ATM 归约到 PCP。对 TM M 和输入 w，构造骨牌集，使得骨牌可拼接 ⟺ M 接受 w。

应用：

• 证明 CFG 歧义性不可判定
• 证明某些文法问题不可判定

MPCP（修改版 PCP）：要求第一个骨牌固定。MPCP ≤ₘ PCP。

复杂性理论

复杂度类

定义：

• DTIME(f(n))：确定性 TM 在 O(f(n)) 时间内可判定的语言类
• NTIME(f(n))：非确定性 TM 在 O(f(n)) 时间内可判定的语言类
• DSPACE(f(n))：确定性 TM 在 O(f(n)) 空间内可判定的语言类

主要复杂度类：

已知关系：

P ⊆ NP ⊆ PSPACE ⊆ EXPTIME
P ⊆ co-NP ⊆ PSPACE ⊆ EXPTIME
至少有一个包含关系是真包含（由空间层次定理）

时间层次定理：若 f(n) log f(n) = o(g(n))，则 DTIME(f(n)) ⊊ DTIME(g(n))。

空间层次定理：若 f(n) = o(g(n))，则 DSPACE(f(n)) ⊊ DSPACE(g(n))。

Savitch 定理：NSPACE(f(n)) ⊆ DSPACE(f(n)²)。特别地，NPSPACE = PSPACE。

NP 完全（Cook-Levin 定理）

定义：

• NP 难：∀L' ∈ NP, L' ≤ₚ L（多项式归约）
• NP 完全：L ∈ NP 且 L 是 NP 难

定理（Cook-Levin, 1971）：SAT 是 NP 完全的。

证明思路：

1. SAT ∈ NP：给定赋值，可在多项式时间内验证
2. ∀L ∈ NP, L ≤ₚ SAT：
   对 NP 中的语言 L，存在 NTM M 在 nᵏ 时间内判定
   对输入 w，构造布尔公式 φ：
   - 变量：table[i,j,s] 表示时刻 i、位置 j、符号/状态为 s
   - 子句：
     (a) 初始配置正确
     (b) 每步转移合法
     (c) 最终达到接受状态
     (d) 每格每刻恰好一个符号
   φ 可满足 ⟺ M 接受 w
   |φ| = O(n^{2k})

Levin 证明了类似定理（独立于 Cook）。

NP 完全问题

经典 NP 完全问题及多项式归约链：

SAT ≤ₚ 3-SAT ≤ₚ CLIQUE ≤ₚ VERTEX-COVER
                   ≤₃ HAM-CYCLE ≤ₚ TSP
                   ≤ₚ 3-COLOR ≤ₚ SUBSET-SUM
                   ≤ₚ INDEPENDENT-SET

1. SAT（布尔可满足性）：

输入：布尔公式 φ（CNF 形式）
问题：φ 是否可满足？

归约：直接由 Cook-Levin 定理

2. 3-SAT：

输入：3-CNF 公式（每子句恰好 3 个文字）
问题：公式是否可满足？

SAT ≤ₚ 3-SAT：
  将一般子句 (l₁ ∨ l₂ ∨ ... ∨ lₖ) 转换为：
  (l₁ ∨ l₂ ∨ y₁) ∧ (ȳ₁ ∨ l₃ ∨ y₂) ∧ ... ∧ (ȳₖ₋₃ ∨ lₖ₋₁ ∨ lₖ)
  引入 O(k) 个新变量

3. 旅行商问题（TSP）：

输入：完全图 G = (V, E)，权重 w: E → ℕ，界限 B
问题：是否存在总权重 ≤ B 的哈密顿回路？

HAM-CYCLE ≤ₚ TSP：
  令 w(e) = 1（原图边）或 2（非原图边），B = |V|

4. 子集和（SUBSET-SUM）：

输入：整数集 S = {s₁, ..., sₙ}，目标 T
问题：是否存在子集 S' ⊆ S 使得 Σ S' = T？

3-SAT ≤ₚ SUBSET-SUM（利用数的十进制编码）

5. 图着色（k-COLOR）：

输入：图 G = (V, E)
问题：G 是否可用 k 种颜色着色（相邻顶点不同色）？

3-SAT ≤ₚ 3-COLOR：
  构造三角形（真/假/基础）+ 变量节点 + 子句 gadget

6. 哈密顿回路（HAM-CYCLE）：

输入：图 G = (V, E)
问题：G 是否包含经过每个顶点恰好一次的回路？

VERTEX-COVER ≤ₚ HAM-CYCLE（构造边 gadget）

NP 难 vs NP 完全

NP 难：至少和 NP 中最难的问题一样难。不要求本身在 NP 中。

NP 完全：NP 难 + 属于 NP。

例：

• 停机问题：NP 难但不可判定（不在 NP 中）
• SAT：NP 完全
• 最优 TSP（决策版）：NP 完全
• 最优 TSP（搜索版）：NP 难（不在 NP 中，因为验证最优性不显然）

P = NP？：

• 千禧年数学问题之一
• 大多数计算机科学家认为 P ≠ NP
• 若 P = NP，则所有 NP 完全问题有多项式算法

多项式归约技术

常见归约方法：

1. 直接构造（Local Replacement）：

将问题 A 的实例直接转换为问题 B 的实例
例：SAT → 3-SAT（子句变换）

2. Gadget 构造：

设计问题 B 的子结构（gadget）模拟问题 A 的组件
例：3-SAT → 3-COLOR（变量 gadget + 子句 gadget）

3. 组合构造：

利用问题的组合性质
例：CLIQUE ↔ INDEPENDENT-SET（补图）

归约的正确性证明：

对 A ≤ₚ B，需证：
1. 归约函数 f 多项式时间可计算
2. x ∈ A ⟺ f(x) ∈ B

方向 1（x ∈ A → f(x) ∈ B）："是"映射到"是"
方向 2（f(x) ∈ B → x ∈ A）："是"蕴含"是"

近似算法

定义：对最小化问题，α-近似算法总是找到解 OPT' ≤ α·OPT。

1. TSP（满足三角不等式）— 2-近似：

算法：
  1. 计算 MST T
  2. T 的边加倍，得到欧拉图
  3. 找欧拉回路 C
  4. 沿 C 快捷（shortcut）得到哈密顿回路 H

分析：
  w(MST) ≤ OPT（TSP 回路删一边是生成树）
  w(C) = 2·w(MST) ≤ 2·OPT
  快捷不增加权重（三角不等式）
  w(H) ≤ w(C) ≤ 2·OPT

复杂度：O(n²)

2. TSP — Christofides 3/2-近似：

算法：
  1. 计算 MST T
  2. 找 T 中奇数度顶点集 O
  3. 在 O 的导出子图上求最小完美匹配 M
  4. T ∪ M 是欧拉图
  5. 找欧拉回路并快捷

分析：
  w(T) ≤ OPT
  w(M) ≤ OPT/2（奇数度顶点的最小完美匹配 ≤ 最优 TSP 的一半）
  w(H) ≤ w(T) + w(M) ≤ 3/2·OPT

复杂度：O(n³)

3. 集合覆盖 — O(ln n)-近似：

算法（贪心）：
  U = 全集，S = 可用集合
  while U 非空:
    选择覆盖最多未覆盖元素的集合 Sᵢ
    U = U \ Sᵢ

分析（harmonic number 界）：
  近似比 = H(n) = Σᵢ₌₁ⁿ 1/i ≤ ln n + 1

复杂度：O(|S| · |U|)

定理（不可近似性）：

• 一般 TSP 不可近似到任意常数因子（除非 P = NP）
• MAX-3-SAT 不可近似到 7/8 + ε（PCP 定理）

随机复杂性

定义：

• BPP（有界误差概率多项式时间）：概率 TM 在多项式时间内判定，误差概率 ≤ 1/3
• RP（随机多项式时间）：
  • x ∈ L → 以 ≥ 1/2 概率接受
  • x ∉ L → 一定拒绝
• ZPP（零误差概率多项式时间）：期望多项式时间，零误差
  • ZPP = RP ∩ co-RP

定理：RP ⊆ NP，RP ⊆ BPP，ZPP = RP ∩ co-RP。

概率放大：通过多次重复（O(log(1/δ)) 次），误差概率可降至任意 δ > 0。

开放问题：BPP = P？（广泛认为是。通过去随机化猜想）

量子计算

定义：

• BQP（有界误差量子多项式时间）：量子 TM 在多项式时间内判定，误差概率 ≤ 1/3

已知关系：

P ⊆ BPP ⊆ BQP ⊆ PSPACE
P ⊆ NP ⊆ PP ⊆ PSPACE

Shor 算法（整数因子分解）：

输入：合数 N
输出：N 的非平凡因子

步骤：
  1. 随机选择 a < N
  2. 计算 gcd(a, N)，若 > 1 则返回
  3. 用量子傅里叶变换（QFT）找 a mod N 的周期 r
  4. 若 r 为偶数，计算 gcd(a^{r/2} ± 1, N)

复杂度：O((log N)³) 量子操作
经典最优：亚指数时间（数域筛法）

意义：RSA 加密依赖因子分解的困难性，量子计算机可破解 RSA

Grover 算法（无序搜索）：

输入：无序数据库 N 个元素，一个目标元素
输出：目标元素的索引

算法（量子振幅放大）：
  1. 初始化均匀叠加态
  2. repeat O(√N) 次：
     a. Oracle 标记目标（相位翻转）
     b. 扩散算子（关于均值的翻转）
  3. 测量 → 以高概率得到目标索引

复杂度：O(√N) 量子操作
经典最优：O(N)

意义：对 NP 问题提供平方级加速，但不足以使 NP ⊆ BQP

应用

词法分析器设计（正则 → DFA）

完整流程：

正则表达式 R
  ↓ Thompson 构造（O(|R|)）
ε-NFA（O(|R|) 状态）
  ↓ 子集构造（O(2^|R|) 最坏）
DFA（至多 2^|R| 状态）
  ↓ Hopcroft 最小化（O(n·log n)）
最小 DFA
  ↓ 代码生成
词法分析器代码

示例（标识符的正则）：

正则：[a-zA-Z_][a-zA-Z0-9_]*

Thompson 构造：
  ε-NFA：约 100 个状态（展开字符类后）

子集构造 → DFA：约 3 个状态
  状态 0：初始（读首字符）
  状态 1：接受（读后续字符）
  状态 2：死状态

最小化：已是 DFA

协议验证（有限状态机）

模型检验（Model Checking）：

将通信协议建模为有限状态机，验证性质（安全性、活性）。

定义：

• 系统 M = (S, S₀, R, L)：Kripke 结构
  • S：状态集，S₀：初始状态，R：转移关系，L：标记函数
• 性质 φ：时序逻辑公式（CTL/LTL）

CTL（计算树逻辑）：

语法：φ ::= p | ¬φ | φ∧φ | EXφ | EGφ | E[φ U ψ] | AXφ | AGφ | A[φ U ψ]

语义：
  EXφ：存在一个后继满足 φ
  EGφ：存在一条路径上始终满足 φ
  E[φ U ψ]：存在路径上 φ 直到 ψ
  AXφ：所有后继满足 φ
  AGφ：所有路径上始终满足 φ

模型检验算法：
  对 CTL 公式 φ 递归计算满足 φ 的状态集合
  EXφ: {s | ∃t. R(s,t) ∧ t ∈ Sat(φ)}  // O(|S| + |R|)
  EGφ: Sat(φ) 的最大不动点              // O(|S| + |R|)
  E[φ U ψ]: 最小不动点                  // O(|S| + |R|)

复杂度：CTL 模型检验 O(|M| · |φ|)，线性时间。

应用：硬件验证、通信协议验证、安全关键系统。

正则表达式引擎

实现类型：

1. 基于 DFA 的引擎：

正则 → ε-NFA → DFA → 匹配

优点：O(n) 匹配时间（n = 输入长度）
缺点：不支持捕获组、反向引用；DFA 可能指数膨胀
代表：re2（Google）

2. 基于回溯的引擎（NFA 模拟）：

正则 → NFA → 回溯搜索

优点：支持捕获组、反向引用、零宽断言
缺点：最坏 O(2^n) 匹配时间（灾难性回溯）
代表：PCRE、Python re、JavaScript RegExp

3. Pike VM（NFA + 损害追踪）：

每个线程记录当前位置和捕获组信息

初始化：线程 (state=q₀, pos=0, captures=[])
每步：
  对每个活跃线程，尝试所有转移
  合并到达同一状态的线程（保留更优捕获）

优点：O(n·m) 时间（n = 输入长度, m = 正则长度）
支持捕获组，无回溯问题
代表：RE2、Rust regex

模型检查

LTL（线性时序逻辑）模型检查：

定义：LTL 公式描述路径上的性质。

语法：φ ::= p | ¬φ | φ∧φ | Xφ | Fφ | Gφ | φ U ψ

语义：
  Xφ：下一步满足 φ
  Fφ：最终满足 φ（Eventually）
  Gφ：始终满足 φ（Globally）
  φ U ψ：φ 直到 ψ

LTL 模型检验算法：

输入：Kripke 结构 M，LTL 公式 φ
输出：M ⊨ φ?

1. 构造 ¬φ 的 Büchi 自动机 A_{¬φ}
   - LTL → GBA（广义 Büchi 自动机）
   - GBA → NBA（标准 Büchi 自动机）

2. 计算 M ⊗ A_{¬φ}（同步积）
   - 状态 = (M 状态, A 状态)
   - 转移同步

3. 检查积中是否存在接受循环
   - 使用 SCC（强连通分量）分析
   - 若存在 → 找到反例路径
   - 若不存在 → M ⊨ φ

复杂度：O(|M| · 2^{|φ|})（指数于公式长度）

Büchi 自动机：

定义：Büchi 自动机 A = (Q, Σ, δ, q₀, F)
接受无穷字 w = a₁a₂a₃... 当且仅当
存在运行 r 使得 Inf(r) ∩ F ≠ ∅
（Inf(r) = 运行中无限次出现的状态集）

定理：Büchi 自动机识别 ω-正则语言（正则语言的无穷推广）

应用：

• 硬件电路验证
• 软件验证
• 安全协议分析
• 分布式系统验证

总结

形式语言与自动机理论是计算机科学的理论基础：

每个概念都遵循"定义→定理→证明思路→算法→复杂度→应用"的结构，形成从基础理论到工程实践的完整体系。