第1章：正则语言（Regular Languages）

一、导读

1.1 本章学习目标

第1章是计算理论的起点，从最简单的计算模型——有限自动机——开始，探索什么是"可计算"。本章建立形式语言理论的基础，为后续章节的图灵机和复杂性理论做准备。

本章的核心学习目标包括：

• 理解确定性有限自动机（DFA）：掌握 DFA 的定义、运行和构造。
• 理解非确定性有限自动机（NFA）：掌握 NFA 与 DFA 的等价性。
• 掌握正则表达式：理解正则表达式与有限自动机的关系。
• 学会使用泵引理：证明一个语言不是正则语言。
• 理解正则运算的封闭性：正则语言在各种运算下保持封闭。

1.2 为什么第一章如此重要

有限自动机是计算理论中最简单的模型，但它的理论意义深远。它定义了"可识别"的概念——一个语言如果能被有限自动机识别，就是正则语言。这个概念是理解更复杂计算模型的基础。

Sipser 的教材以清晰优雅著称。他用精确的定义和直觉性的解释，将抽象的数学概念讲得通俗易懂。本章的证明风格——先给出直觉，再给出形式化证明——贯穿全书。

1.3 核心问题引导

什么是有限自动机？它能做什么？不能做什么？

DFA 和 NFA 有什么区别？为什么 NFA 不比 DFA 更强大？

正则表达式和有限自动机有什么关系？

如何证明一个语言不是正则的？

正则语言有哪些封闭性质？

二、核心概念详解

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

2.1.1 形式定义

一个确定性有限自动机（DFA）是一个五元组 $(Q, \Sigma, \delta, q_0, F)$：

• $Q$：有限状态集
• $\Sigma$：有限字母表
• $\delta: Q \times \Sigma \to Q$：转移函数
• $q_0 \in Q$：起始状态
• $F \subseteq Q$：接受状态集

2.1.2 DFA 示例

设计一个 DFA 识别语言 $L = \{w \mid w \text{ 包含偶数个 } 1\}$：

状态集 Q = {q_even, q_odd}
字母表 Σ = {0, 1}
起始状态 q_0 = q_even
接受状态 F = {q_even}

转移函数：
δ(q_even, 0) = q_even    （读0不改变奇偶性）
δ(q_even, 1) = q_odd     （读1改变奇偶性）
δ(q_odd, 0) = q_odd      （读0不改变奇偶性）
δ(q_odd, 1) = q_even     （读1改变奇偶性）

状态图表示：

0           1
    ┌───────┐   ┌───────┐
    │       ▼   │       ▼
  ┌───┐  0  ┌───┐  1  ┌───┐
  │q₀ │────►│q₀ │◄───►│q₁ │
  └───┘     └───┘     └───┘
  起始/接受              拒绝

2.1.3 DFA 的计算

给定输入字符串 $w = w_1 w_2 \cdots w_n$，DFA 从起始状态 $q_0$ 开始，依次经过状态 $r_0, r_1, \ldots, r_n$，其中：

• $r_0 = q_0$
• $r_{i+1} = \delta(r_i, w_{i+1})$，对于 $i = 0, 1, \ldots, n-1$

如果 $r_n \in F$，则 DFA 接受字符串 $w$。

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

2.2.1 NFA 与 DFA 的区别

NFA 有两个关键区别：

可以有 ε 转移：不需要读取输入就可以改变状态。

转移可以不确定：对于同一个状态和输入符号，可以转移到多个状态。

NFA 的形式定义是一个五元组 $(Q, \Sigma, \delta, q_0, F)$，其中 $\delta: Q \times \Sigma_\varepsilon \to \mathcal{P}(Q)$。

2.2.2 NFA 示例

设计一个 NFA 识别语言 $L = \{w \mid w \text{ 以 } ab \text{ 结尾}\}$：

a         b         a,b
    ┌───────┐ ┌───────┐ ┌───────┐
    │       ▼ │       ▼ │       ▼
  ┌───┐  a  ┌───┐  b  ┌───┐a,b ┌───┐
  │q₀ │────►│q₁ │────►│q₂ │────►│q₂ │
  └───┘     └───┘     └───┘     └───┘
  起始                    接受

2.2.3 NFA 与 DFA 的等价性

定理：每个 NFA 都可以转换为等价的 DFA。

证明思路：子集构造法（subset construction）。DFA 的每个状态对应 NFA 的状态集。DFA 在读入一个符号后，转移到 NFA 所有可能到达的状态的集合。

NFA 状态集 {q₀, q₁, q₂} 对应 DFA 的一个状态
DFA 的转移：δ_DFA({q₀, q₁}, a) = {q₀, q₁, q₂}

2.3 正则表达式

2.3.1 正则表达式的定义

正则表达式递归定义如下：

$a$（$a \in \Sigma$）是正则表达式，表示语言 $\{a\}$

$\varepsilon$ 是正则表达式，表示语言 $\{\varepsilon\}$

$\emptyset$ 是正则表达式，表示语言 $\emptyset$

如果 $R_1$ 和 $R_2$ 是正则表达式，则以下也是：

- $R_1 \cup R_2$（并）

- $R_1 \circ R_2$（连接）

- $R_1^*$（Kleene 星号）

2.3.2 正则表达式示例

2.3.3 Kleene 定理

定理：一个语言是正则的，当且仅当它可以被某个正则表达式描述。

这个定理建立了正则表达式和有限自动机之间的等价关系：

• 正则表达式 → NFA（通过构造）
• DFA → 正则表达式（通过状态消除法）

2.4 泵引理

2.4.1 泵引理的内容

泵引理：如果 $A$ 是正则语言，则存在泵长度 $p$，使得对于任意长度至少为 $p$ 的字符串 $s \in A$，都可以将 $s$ 分解为 $s = xyz$，满足：

对于每个 $i \geq 0$，$xy^iz \in A$

$|y| > 0$

$|xy| \leq p$

2.4.2 使用泵引理证明非正则性

证明：$B = \{0^n1^n \mid n \geq 0\}$ 不是正则语言。

证明（反证法）：

假设 $B$ 是正则语言。由泵引理，存在泵长度 $p$。

取 $s = 0^p1^p \in B$。注意 $|s| = 2p \geq p$。

由泵引理，$s = xyz$，其中 $|xy| \leq p$，$|y| > 0$。

因为 $|xy| \leq p$，所以 $y$ 只包含 0。设 $y = 0^k$，$k > 0$。

取 $i = 2$，则 $xy^2z = 0^{p+k}1^p$。

因为 $k > 0$，$p+k \neq p$，所以 $xy^2z \notin B$。

矛盾！因此 $B$ 不是正则语言。

2.5 正则语言的封闭性

正则语言在以下运算下封闭：

三、实战案例

3.1 DFA 构造实战

问题：构造一个 DFA 识别二进制字符串中 1 的个数是 3 的倍数。

状态：q₀（0个1 mod 3 = 0），q₁（1个1 mod 3 = 1），q₂（2个1 mod 3 = 2）
起始状态：q₀
接受状态：{q₀}

转移函数：
δ(q₀, 0) = q₀,  δ(q₀, 1) = q₁
δ(q₁, 0) = q₁,  δ(q₁, 1) = q₂
δ(q₂, 0) = q₂,  δ(q₂, 1) = q₀

3.2 正则表达式实战

问题：写出识别以下语言的正则表达式。

(a) 所有以 "ab" 开头或以 "ba" 结尾的 {a,b}* 中的字符串：

$$(ab(a \cup b)^) \cup ((a \cup b)^ba)$$

(b) 不包含子串 "011" 的 {0,1}* 中的字符串：

$$0^(10^)^ \cup 0^1^0^ \cup (0 \cup 10)^*(1 \cup \varepsilon)$$

3.3 泵引理证明实战

证明：$L = \{ww \mid w \in \{0,1\}^*\}$ 不是正则语言。

证明：假设 $L$ 是正则的，泵长度为 $p$。取 $s = 0^p1^p0^p1^p$。

由泵引理，$s = xyz$，$|xy| \leq p$，$|y| > 0$。

$y$ 只包含 0（因为 $|xy| \leq p$）。设 $y = 0^k$。

取 $i = 0$，$xz = 0^{p-k}1^p0^p1^p$。

这个字符串的前半部分长度为 $2p-k$，后半部分长度为 $2p$，不相等，所以 $xz \notin L$。矛盾。

四、本章小结

第1章建立了计算理论的基础：

DFA：最简单的计算模型，由有限状态和确定性转移组成。

NFA：允许不确定性和 ε 转移，但与 DFA 等价。

正则表达式：描述正则语言的代数工具，与有限自动机等价。

泵引理：证明语言不是正则的有力工具。

封闭性：正则语言在各种运算下保持封闭。

正则语言是计算理论的起点。理解了有限自动机，就为理解更复杂的计算模型（下推自动机、图灵机）打下了基础。

五、思考与练习

思考题

DFA 和 NFA 在实际应用中的性能差异是什么？

为什么正则表达式不能匹配所有语言？

泵引理的直觉是什么？

正则语言的补运算为什么需要 DFA 而不是 NFA？

正则表达式在实际编程中有哪些应用？

编程练习

实现 DFA 模拟器：给定 DFA 的描述和输入字符串，模拟 DFA 的运行。

实现 NFA 到 DFA 的转换：使用子集构造法。

实现正则表达式匹配器：支持连接、并、Kleene 星号。