跳转至

形式语言与自动机

概述

形式语言与自动机理论是计算理论的基础，研究不同计算模型的能力与限制。从最简单的有限自动机到图灵机，这些模型形成了一个严格的层次结构。

1. Chomsky层次

graph TB
    T3[Type 3: 正则语言] --> T2[Type 2: 上下文无关语言]
    T2 --> T1[Type 1: 上下文有关语言]
    T1 --> T0[Type 0: 递归可枚举语言]
类型 语言类 文法 自动机 产生式规则
Type 3 正则语言 正则文法 有限自动机 (FA) \(A \to aB\) 或 \(A \to a\)
Type 2 上下文无关语言 上下文无关文法 (CFG) 下推自动机 (PDA) \(A \to \gamma\)
Type 1 上下文有关语言 上下文有关文法 (CSG) 线性有界自动机 (LBA) \(\alpha A \beta \to \alpha \gamma \beta\)
Type 0 递归可枚举语言 无限制文法 图灵机 (TM) \(\alpha \to \beta\)

每一层严格包含下一层：\(\text{REG} \subsetneq \text{CFL} \subsetneq \text{CSL} \subsetneq \text{RE}\)

2. 有限自动机

2.1 确定性有限自动机（DFA）

定义：DFA 是五元组 \(M = (Q, \Sigma, \delta, q_0, F)\)

  • \(Q\)：有限状态集
  • \(\Sigma\)：输入字母表
  • \(\delta: Q \times \Sigma \to Q\)：转移函数
  • \(q_0 \in Q\)：初始状态
  • \(F \subseteq Q\)：接受状态集
stateDiagram-v2
    direction LR
    [*] --> q0
    q0 --> q0: 0
    q0 --> q1: 1
    q1 --> q0: 0
    q1 --> q1: 1
    q1 --> [*]

上图是识别"以1结尾的二进制串"的DFA，\(F = \{q_1\}\)。

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

定义：NFA 是五元组 \(N = (Q, \Sigma, \delta, q_0, F)\)

  • \(\delta: Q \times (\Sigma \cup \{\varepsilon\}) \to \mathcal{P}(Q)\)：转移函数返回状态集合

关键区别：

特性 DFA NFA
转移函数 唯一确定 多个可能
\(\varepsilon\)-转移 不允许 允许
接受条件 唯一路径到达接受状态 存在某条路径到达接受状态
实现 直接模拟 需要回溯或子集构造

2.3 DFA与NFA的等价性（子集构造法）

定理：对任意NFA \(N\)，存在等价的DFA \(D\)，使得 \(L(N) = L(D)\)。

子集构造法：

  1. DFA的状态是NFA状态集的子集：\(Q_D = \mathcal{P}(Q_N)\)
  2. 初始状态：\(q_{0,D} = \varepsilon\text{-closure}(\{q_{0,N}\})\)
  3. 转移：\(\delta_D(S, a) = \varepsilon\text{-closure}\left(\bigcup_{q \in S} \delta_N(q, a)\right)\)
  4. 接受状态：\(F_D = \{S \in Q_D \mid S \cap F_N \neq \emptyset\}\)

状态爆炸

子集构造最坏情况下，DFA状态数为 \(2^{|Q_N|}\)。存在NFA使得这个上界是紧的。

2.4 DFA最小化

Myhill-Nerode定理：语言 \(L\) 是正则的当且仅当其 Myhill-Nerode 等价关系有有限个等价类，且最小DFA的状态数等于等价类数。

等价关系：\(x \sim_L y \iff \forall z \in \Sigma^*, xz \in L \leftrightarrow yz \in L\)

最小化算法（Hopcroft算法）：

初始划分: {F, Q-F}
repeat:
    对每个划分块和每个符号a:
        若某块中的状态对a的转移到达不同块:
            细分该块
until 不再变化

3. 正则表达式

3.1 定义

正则表达式递归定义：

  • \(\emptyset\)，\(\varepsilon\)，\(a\)（\(a \in \Sigma\)）是正则表达式
  • 若 \(R_1, R_2\) 是正则表达式，则 \(R_1 \cup R_2\)、\(R_1 \circ R_2\)、\(R_1^*\) 也是

3.2 正则表达式与有限自动机的等价性

Kleene定理：

\[ \text{正则表达式} \iff \text{有限自动机} \iff \text{正则文法} \]
  • FA \(\to\) RE：状态消除法
  • RE \(\to\) NFA：Thompson构造法
graph LR
    RE[正则表达式] -->|Thompson构造| NFA
    NFA -->|子集构造| DFA
    DFA -->|最小化| minDFA[最小DFA]
    DFA -->|状态消除| RE

4. 正则语言的泵引理

4.1 泵引理陈述

若 \(L\) 是正则语言，则存在常数 \(p\)（泵长度），使得对任意 \(s \in L\)（\(|s| \geq p\)），存在分割 \(s = xyz\) 满足：

  1. \(|y| > 0\)
  2. \(|xy| \leq p\)
  3. \(\forall i \geq 0, xy^iz \in L\)

4.2 应用：证明非正则性

例：证明 \(L = \{a^n b^n \mid n \geq 0\}\) 不是正则语言。

证明：假设 \(L\) 是正则的，泵长度为 \(p\)。

取 \(s = a^p b^p \in L\)，\(|s| = 2p \geq p\)。

由泵引理，\(s = xyz\)，\(|xy| \leq p\)，故 \(y = a^k\)（\(k > 0\)）。

取 \(i = 2\)：\(xy^2z = a^{p+k}b^p \notin L\)（因为 \(p + k \neq p\)）。矛盾。\(\square\)

5. 下推自动机与上下文无关语言

5.1 上下文无关文法（CFG）

定义：\(G = (V, \Sigma, R, S)\)

  • \(V\)：变量（非终结符）集
  • \(\Sigma\)：终结符集
  • \(R\)：产生式规则 \(A \to \gamma\)（\(A \in V\)，\(\gamma \in (V \cup \Sigma)^*\)）
  • \(S \in V\)：起始变量

例：\(\{a^n b^n \mid n \geq 0\}\) 的CFG：

\[ S \to aSb \mid \varepsilon \]

5.2 Chomsky范式（CNF）

任何CFG可转化为 Chomsky范式：

\[ A \to BC \quad \text{或} \quad A \to a \quad \text{或} \quad S \to \varepsilon \]

CYK算法：基于CNF的动态规划解析算法，\(O(n^3|G|)\)。

5.3 下推自动机（PDA）

定义：PDA 是六元组 \((Q, \Sigma, \Gamma, \delta, q_0, F)\)

  • 额外的 \(\Gamma\)：栈字母表
  • \(\delta: Q \times (\Sigma \cup \{\varepsilon\}) \times (\Gamma \cup \{\varepsilon\}) \to \mathcal{P}(Q \times (\Gamma \cup \{\varepsilon\}))\)

定理：CFL \(=\) PDA接受的语言类 \(=\) CFG生成的语言类。

确定性PDA

确定性PDA（DPDA）识别的语言类（确定性上下文无关语言，DCFL）是CFL的真子集。大多数编程语言的语法是DCFL。

5.4 上下文无关语言的泵引理

若 \(L\) 是上下文无关语言，则存在常数 \(p\)，使得对任意 \(s \in L\)（\(|s| \geq p\)），存在分割 \(s = uvxyz\) 满足：

  1. \(|vy| > 0\)
  2. \(|vxy| \leq p\)
  3. \(\forall i \geq 0, uv^ixy^iz \in L\)

应用：证明 \(L = \{a^n b^n c^n \mid n \geq 0\}\) 不是上下文无关的。

6. 上下文无关语言的性质

6.1 封闭性

运算 正则语言 上下文无关语言
并 封闭 封闭
连接 封闭 封闭
Kleene星 封闭 封闭
交 封闭 不封闭
补 封闭 不封闭
与正则语言的交 — 封闭

6.2 判定问题

问题 正则语言 CFL
成员判定 \(w \in L\)? $O( w
空性 \(L = \emptyset\)? 可判定 可判定
等价性 \(L_1 = L_2\)? 可判定 不可判定

7. 图灵机

7.1 定义

图灵机 \(M = (Q, \Sigma, \Gamma, \delta, q_0, q_{accept}, q_{reject})\)

  • \(\Gamma\)：带字母表（\(\Sigma \subsetneq \Gamma\)，含空白符 \(\sqcup\)）
  • \(\delta: Q \times \Gamma \to Q \times \Gamma \times \{L, R\}\)：转移函数（读写头可左移或右移）

7.2 图灵机与其他模型

graph TB
    FA[有限自动机] -->|加栈| PDA[下推自动机]
    PDA -->|无限带| TM[图灵机]
    TM ---|等价| Multi[多带图灵机]
    TM ---|等价| NDTM[非确定图灵机]
    TM ---|等价| Lambda[Lambda演算]
    TM ---|等价| RAM[RAM模型]

Church-Turing论题：所有"合理的"计算模型都与图灵机等价。

7.3 图灵机变体

变体 与标准TM的关系
多带图灵机 等价（\(O(t^2)\) 模拟）
非确定图灵机 等价（\(O(2^{t})\) 模拟）
双向无限带 等价
多维带 等价
枚举器 等价于识别器

8. 语言层次总结

graph TB
    subgraph "Chomsky 层次"
        REG["正则语言<br>DFA/NFA/RE"]
        CFL["上下文无关语言<br>PDA/CFG"]
        CSL["上下文有关语言<br>LBA"]
        RE["递归可枚举语言<br>TM"]
        ALL["所有语言"]
    end
    REG --> CFL --> CSL --> RE --> ALL

关键分界点：

  • 正则 vs CFL：\(\{a^n b^n\}\) 区分
  • CFL vs CSL：\(\{a^n b^n c^n\}\) 区分
  • 可判定 vs RE：停机问题区分
  • RE vs ALL：不可识别语言的存在（对角化）

参考资料

  • Sipser, Introduction to the Theory of Computation（经典教材）
  • Hopcroft, Motwani & Ullman, Introduction to Automata Theory, Languages, and Computation

相关章节：

评论 #