有限自动机与正则语言

计算理论的第一个层级：有限自动机与正则语言。本章讲 DFA 与 NFA 的定义、子集构造等价性、正则表达式与自动机的相互转换、泵引理与 DFA 最小化——最后看"词法分析器就是一个 DFA"（直觉版见计算模型）。

DFA 与 NFA

确定性有限自动机（DFA）：五元组 $(Q, \Sigma, \delta, q_0, F)$ ——有限状态集、字母表、转移函数 $\delta: Q \times \Sigma \to Q$ 、初始与接受状态。逐字符读入，结束时在 $F$ 中则接受。

非确定性自动机（NFA）：转移可以是集合（ $\delta: Q \times \Sigma_\epsilon \to \mathcal{P}(Q)$ ）——同一输入可能走向多个状态（或 $\epsilon$ 转移免费跳转）。

NFA 看起来更强，但与 DFA 等价（识别同样的语言）：子集构造把 NFA 的"状态集合"当作 DFA 的单个状态。

正则表达式与自动机等价（Kleene 定理），双向转换：

这条转换链是正则引擎的数学基础（→ 字符串算法）：RE2 一类 NFA 模拟引擎不做子集构造，直接同时模拟所有活跃状态——避开指数爆炸。

正则语言在并、交、补下封闭（DFA 的笛卡尔积与状态补）——封闭性是构造复杂正则的语言学工具。

如何证明一个语言不是正则？ 用泵引理（pumping lemma）：正则语言中足够长的串都能"泵"——分解 $w = xyz$ （ $|xy| \le p$ 、 $|y| \ge 1$ ），使得 $xy^i z$ 对一切 $i$ 都在语言中。

经典应用： $L = \{a^n b^n\}$ 不是正则——任取 $p$ ，串 $a^p b^p$ 的 $y$ 只能含 $a$ ，泵它破坏 a、b 计数相等。泵引理是证明"不是正则"的工具（不是识别正则的工具）——"正则表达式不能数"的本质是有限状态无法表达无界计数。

识别同一语言的最小 DFA 唯一（Myhill–Nerode 定理）。Hopcroft 算法（ $O(n \log n)$ ）：反复合并"不可区分"的状态——两个状态对一切后续输入行为相同即合并。

词法分析器就是一个 DFA（→ 编译流程）：token 的正则表达式合成的 DFA，一次扫描同时匹配所有 token 种类，最长匹配优先。正则库（RE2、Rust regex）编译一次反复使用——DFA 执行无回溯是它对回溯引擎的性能优势。