# Formal Languages

> 形式语言与自动机理论

- Skill: `viewway/formal-languages` (Agent Skill)
- Install (CLI): `npx skillmds@latest add viewway/formal-languages`
- Raw SKILL.md: https://api.skillmd.com/api/skills/viewway/formal-languages/raw
- Safety review: pending
- Works with: Claude Code, Claude.ai, OpenAI Codex
- Category: Coding & Dev Tools
- Author: viewway (https://skillmd.com/u/viewway)
- Updated: 2026-09-17
- Page: https://skillmd.com/skills/viewway/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 是起始符号。

| 类型 | 名称 | 产生式形式 | 等价自动机 |
|------|------|-----------|-----------|
| 0 型 | 递归可枚举（RE） | α → β，\|α\| ≥ 1 | 图灵机（TM） |
| 1 型 | 上下文相关（CSL） | αAβ → αγβ，γ ≠ ε（\|αβ\| ≤ \|γ\|） | 线性有界自动机（LBA） |
| 2 型 | 上下文无关（CFL） | A → γ | 下推自动机（PDA） |
| 3 型 | 正则（Regular） | A → aB 或 A → a | 有限自动机（FA） |

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

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

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

### 闭包性质

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

| 运算 | 正则 | CFL | CSL | RE |
|------|------|-----|-----|-----|
| 并 ∪ | ✅ | ✅ | ✅ | ✅ |
| 交 ∩ | ✅ | ❌ | ✅ | ✅ |
| 补 ¬ | ✅ | ❌ | ✅ | ❌ |
| 连接 · | ✅ | ✅ | ✅ | ✅ |
| Kleene 星 * | ✅ | ✅ | ✅ | ✅ |
| 正同态 h | ✅ | ✅ | ✅ | ✅ |
| 逆同态 h⁻¹ | ✅ | ✅ | ✅ | ✅ |

**关键证明思路**：
- **正则语言对交封闭**：构造乘积自动机 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** | ∪ₖ DTIME(nᵏ) | 多项式时间可解 |
| **NP** | ∪ₖ NTIME(nᵏ) | 多项式时间可验证 |
| **co-NP** | {Lᶜ \| L ∈ NP} | NP 的补 |
| **PSPACE** | ∪ₖ DSPACE(nᵏ) | 多项式空间可解 |
| **EXPTIME** | ∪ₖ DTIME(2^{nᵏ}) | 指数时间可解 |
| **EXPSPACE** | ∪ₖ DSPACE(2^{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 自动机识别 ω-正则语言（正则语言的无穷推广）
```

**应用**：
- 硬件电路验证
- 软件验证
- 安全协议分析
- 分布式系统验证

---

## 总结

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

| 层次 | 语言类 | 自动机模型 | 判定问题 |
|------|--------|-----------|---------|
| 3 型 | 正则语言 | FA (DFA/NFA) | 成员判定 O(n)，等价判定 O(n log n) |
| 2 型 | CFL | PDA | 成员判定 O(n³)（CYK），歧义性不可判定 |
| 1 型 | CSL | LBA | 成员判定可判定，等价性不可判定 |
| 0 型 | RE | TM | 成员判定不可判定（停机问题） |

| 复杂度类 | 定义 | 典型问题 |
|---------|------|---------|
| P | 多项式时间 | 排序、最短路径、矩阵乘法 |
| NP | 非确定性多项式时间 | SAT、TSP、图着色 |
| PSPACE | 多项式空间 | QBF、地理游戏 |
| EXPTIME | 指数时间 | 某些博弈问题 |

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