1 / 4概念
Automata & Formal Languages
自动机是“带多少记忆的识别器”,形式语言是“它能识别的字符串集合”。判断标准不是“正则更简单”,而是语言需不需要计数、嵌套或栈;选错层级,正则会写出回溯灾难,语法分析器会为简单 token 付出过高代价。
1 概念
1.1 一句话定义
自动机是有限状态 + 转移规则的计算模型;形式语言是某个字母表上字符串的集合。DFA/NFA 识别正则语言,CFG/PDA 识别上下文无关语言,图灵机识别递归可枚举语言;乔姆斯基谱系按“记忆能力”从弱到强排列。
1.2 它解决什么问题
- 词法分析:标识符、数字、关键字是正则语言,DFA 可以线性扫描。
- 语法分析:括号、嵌套、表达式优先级需要栈,CFG/PDA 才能表达。
- 协议与状态机:登录、订单、连接生命周期可以用有限状态机建模并验证。
- 边界判断:先判断语言属于哪一层,再决定用正则、解析器还是通用程序。
1.3 不属于本页的内容
| 主题 | 去哪 |
|---|---|
| 图灵机、可计算性、停机问题 | Computability |
| P/NP、NP 完全性 | Computational Complexity |
| 编译器前端的完整实现 | 编译原理相关页面(待补) |
| 正则引擎的工程实现与优化 | 文本处理/正则工程页面(待补) |
| 模型检验与形式化验证 | 形式化方法页面(待补) |
1.4 关键术语
| 术语 | 含义 | 容易混淆的点 |
|---|---|---|
| 字符串 / 语言 | 符号序列 / 字符串集合 | 空串 ε 不是空语言 ∅ |
| DFA | 确定性有限自动机,每个状态每个符号唯一转移 | 转移函数是全函数 |
| NFA | 非确定性有限自动机,可有 ε 转移和多个后继 | 与 DFA 等价,不是更强 |
| 子集构造 | 把 NFA 状态集合变成 DFA 状态 | 最坏 2ⁿ 个状态 |
| 正则表达式 | 用并、连接、闭包描述正则语言 | 工程正则常带反向引用,超出理论正则 |
| CFG | 上下文无关文法,产生式左部是单个非终结符 | 不是“所有语法” |
| 推导 / 分析树 | 从开始符号展开得到字符串 | 歧义是两棵不同分析树 |
| PDA | 下推自动机,带一个栈 | 非确定 PDA 比确定 PDA 强 |
| 泵引理 | 证明语言不属于某层的必要条件 | 不是充分条件,不能证明属于 |
2 机制
2.1 心智模型
把计算模型想成“内存越来越大”:DFA 只有有限状态,记不住“已经数到几”;PDA 多一个栈,能匹配嵌套但只能后进先出;图灵机有一条可读写纸带,能模拟任意计算。语言层级跟着记忆能力走,而不是跟着语法复杂度走。
2.2 机制拆解
- DFA:五元组
(Q, Σ, δ, q₀, F);从 q₀ 读入每个符号,按 δ 转移,读完在 F 中则接受。DFA 是线性扫描,O(n) 时间、O(1) 工作空间。 - NFA:δ 返回状态集合,允许 ε 转移;同一个字符串可能有多条路径。子集构造把“当前可能的状态集合”做成 DFA 状态,最坏 2ⁿ 个;DFA 最小化可把等价状态合并。
- 正则表达式:并
|、连接、闭包*三种基本运算;Thompson 构造把正则转成 NFA,再转 DFA。工程正则的\1反向引用、环视等已超出理论正则语言。 - CFG:四元组
(V, Σ, R, S);产生式A → α,左部必须是单个非终结符。推导可从任意非终结符展开;最左/最右推导对应不同分析策略;同一字符串有两棵分析树即歧义。 - PDA:七元组,带一个栈;转移可读输入、压栈/弹栈。非确定 PDA 识别 CFL;确定 PDA 识别 DCFL,是 CFL 的真子集。
- 泵引理:正则语言存在长度 p,任何足够长的串都能拆成
xyz,|xy| ≤ p、|y| > 0,且xyⁱz仍在语言中;CFL 的泵引理拆成uvwxy,|vwx| ≤ p、|vx| > 0。它是必要条件,只能用来证明“不属于”,不能证明“属于”。
2.3 完整枚举
乔姆斯基谱系:
| 类型 | 文法 | 识别器 | 语言类 | 典型例子 | 判定问题 |
|---|---|---|---|---|---|
| 3 | 正则文法 | DFA / NFA | 正则语言 | 标识符、IP、日期格式 | 成员、空、等价可判定 |
| 2 | 上下文无关文法 | 非确定 PDA | 上下文无关语言 | 括号、表达式、JSON | 成员/空可判定,等价/歧义不可判定 |
| 1 | 上下文有关文法 | 线性有界自动机 | 上下文有关语言 | 敏感依赖、部分自然语言现象 | 成员可判定,资源受限 |
| 0 | 无限制文法 | 图灵机 | 递归可枚举语言 | 任意可计算语言 | 成员半可判定,空/等价不可判定 |
正则语言与 CFL 的闭包性质:
| 运算 | 正则语言 | 上下文无关语言 |
|---|---|---|
| 并 | 封闭 | 封闭 |
| 连接 | 封闭 | 封闭 |
| Kleene 星 | 封闭 | 封闭 |
| 补 | 封闭 | 不封闭 |
| 交 | 封闭 | 不封闭(与正则语言交仍封闭) |
| 反转 | 封闭 | 封闭 |
| 同态 | 封闭 | 封闭 |
DFA/NFA 与解析算法:
| 对象/算法 | 输入 | 复杂度 | 输出 |
|---|---|---|---|
| DFA 模拟 | 字符串 | O(n) | 接受/拒绝 |
| 子集构造 | NFA | 最坏 O(2ⁿ) 状态 | 等价 DFA |
| Hopcroft 最小化 | DFA | O(n log n) | 最小 DFA |
| CYK | CFG + 字符串 | O(n³) | 是否接受/分析表 |
| Earley | CFG + 字符串 | 最坏 O(n³),无歧义文法常更快 | 分析结果 |
| LL/LR 分析 | 受限 CFG | O(n) | 分析树/动作表 |
2.4 关键数字与复杂度
| 指标 | 量级 | 说明 |
|---|---|---|
| NFA 子集构造 | 最多 2ⁿ 个状态 | 实际可达状态通常少得多 |
| CYK | O(n³) | 一般 CFG 的通用成员判定 |
| LL/LR | O(n) | 需要文法满足条件 |
| 回溯正则 | 最坏指数级 | 嵌套量词是典型触发 |
| NFA 正则引擎 | O(n·m) | m 为模式长度/状态数 |
3 实践
3.1 最小示例
# 子集构造:把 NFA 的“可能状态集合”变成 DFA 状态。
SUBSET_CONSTRUCTION(NFA):
S0 = EPS_CLOSURE({q0})
map = {S0: 0}; queue = [S0]; trans = []
while queue not empty:
S = queue.pop_front()
for a in ALPHABET:
T = EPS_CLOSURE(UNION(δ(q, a) for q in S))
if T not in map:
map[T] = |map|; queue.push_back(T)
trans[map[S]][a] = map[T]
accept = {map[S] | S ∩ F != ∅}
return trans, accept
# CYK:CFG 成员判定,要求文法先转成 CNF(A -> BC 或 A -> a)。
CYK(G, w):
n = |w|; table = n x n sets
for i in 0..n-1:
for A -> a in G:
if a == w[i]: table[i][i].add(A)
for len in 2..n:
for i in 0..n-len:
j = i + len - 1
for k in i..j-1:
for A -> BC in G:
if B in table[i][k] and C in table[k+1][j]:
table[i][j].add(A)
return S in table[0][n-1]
3.2 常用操作与参数
| 操作 | 做法 | 说明 |
|---|---|---|
| 判断是否正则 | 构造 DFA/NFA,或用泵引理证伪 | 泵引理不能证“是” |
| 正则转自动机 | Thompson 构造 | 再子集构造/最小化 |
| NFA 转 DFA | 子集构造 | 注意状态爆炸 |
| DFA 最小化 | Hopcroft/分区细化 | 合并等价状态 |
| CFG 成员判定 | CYK / Earley | CYK 需 CNF |
| 消除左递归 | 把 A → Aα 改写成不含左递归的形式 | 递归下降前必做 |
| 处理歧义 | 优先级/结合性/重写文法 | 或改用 LR |
3.3 标准流程
- 用一句话写出目标语言:字母表是什么,字符串需要什么结构。
- 判断是否需要计数/嵌套:不需要 → 正则;需要栈 → CFG/PDA;需要任意计算 → 图灵机。
- 正则:写正则 → Thompson → NFA → DFA → 最小化;避免回溯引擎的嵌套量词。
- CFG:写产生式 → 消左递归/提左公因子 → 选 LL/LR/Earley/CYK。
- 证明边界并用边界串测试:泵引理/闭包性质证“不属于”,构造证“属于”;覆盖空串、最长串、嵌套深度、Unicode。
3.4 与相邻技术的组合
- 词法/语法分析:正则负责 token,CFG 负责结构;两层分工明确。
- 正则引擎:NFA/DFA 引擎线性扫描;回溯引擎支持反向引用但可能指数爆炸。
- 计算理论:自动机层级是可计算性与复杂性的前置;图灵机是下一层模型。
3.5 选型维度
| 维度 | 取值 | 影响 |
|---|---|---|
| 是否需要嵌套 | 否 / 是 | 正则 vs CFG |
| 是否需要计数 | 否 / 是 | 有限状态不够,需要栈 |
| 性能 | 线性 / 可接受多项式 | DFA/LL/LR vs CYK/Earley |
| 歧义 | 可接受 / 必须消除 | 文法设计与分析器选择 |
| 工具生态 | 正则库 / 解析器生成器 | 实现成本 |
| Unicode/本地化 | 简单 / 复杂 | 字符、码点、规范化 |
3.6 决策规则
- 扁平模式(标识符、日期、IP、日志字段):正则/DFA。
- 嵌套结构(括号、JSON、表达式、HTML 子集):CFG + 解析器,不要用正则硬解。
- 需要任意计算/验证程序性质:图灵机模型,进入可计算性讨论。
- 正则引擎选择:输入不可信、模式复杂时优先 NFA/DFA 引擎(RE2 类),避免回溯。
- 文法有歧义:先加优先级/结合性,或换 LR;不要靠“试试看”。
3.7 替代方案对比
| 方案 | 优势 | 代价 | 适用 |
|---|---|---|---|
| DFA | 线性、无回溯、可预测 | 状态可能爆炸 | 词法、协议、过滤 |
| NFA | 构造简单、表达直观 | 模拟要多状态 | 正则匹配、Thompson |
| 回溯正则 | 支持反向引用/环视 | 最坏指数、易被攻击 | 受控输入、复杂模式 |
| CFG + LL | 线性、错误恢复好 | 文法受限、需消除左递归 | 编程语言前端 |
| CFG + LR | 表达力强、线性 | 表生成复杂、冲突处理 | 工业级解析器 |
| Earley/CYK | 通用 CFG | 最坏 O(n³) | 自然语言、原型 |
| 图灵机 | 通用计算 | 不可判定、不可工程化 | 理论边界 |
3.8 何时不该用
- 用正则解析嵌套括号/HTML/JSON:正则语言表达不了任意深度嵌套。
- 用 CFG 解析固定 token:过度设计,DFA 更快。
- 用回溯正则处理不可信长输入:可能被构造为指数爆炸。
- 用泵引理证明语言正则:它只是必要条件,不能证明“属于”。
4 边界
4.1 典型故障
| 症状 | 根因 | 处理 |
|---|---|---|
| 正则匹配卡死/CPU 飙高 | 嵌套量词触发回溯爆炸 | 改 NFA 引擎、限制输入、原子组 |
| NFA 转 DFA 内存爆 | 子集构造状态指数增长 | 惰性构造、最小化、换引擎 |
| 正则匹配不到嵌套结构 | 正则语言无栈记忆 | 改用 CFG/解析器 |
| 解析器报冲突 | 文法有歧义/左递归 | 加优先级、消左递归、换 LR |
| 递归下降栈溢出 | 深层嵌套/左递归 | 显式栈、消除左递归 |
| Unicode 匹配错位 | 按字节/码元处理 | 按码点、规范化、明确编码 |
| 锚点/贪婪匹配错 | ^/$/* 语义误解 | 用非贪婪/多行模式并测试 |
| 文法等价性判断不了 | CFG 等价不可判定 | 用测试/受限文法,不要承诺通用判定 |
4.2 反模式
| 做法 | 后果 | 替代 |
|---|---|---|
| 用正则解析 HTML/JSON | 嵌套和转义处理不全 | 用解析器 |
| 在生产用回溯正则跑用户输入 | ReDoS 风险 | NFA 引擎/输入上限 |
| 用泵引理证明正则性 | 逻辑方向错误 | 构造 DFA/NFA |
| 递归下降前不消左递归 | 无限递归 | 改写文法 |
4.3 可观测信号
正则引擎的回溯步数/匹配耗时、DFA 状态数、子集构造的集合数、解析器的冲突数/错误恢复位置、分析表大小、CYK 的 O(n³) 耗时。线上看匹配 P99、CPU 占用、超时率。
4.4 安全 / 性能 / 一致性边界
- 安全:不可信输入 + 回溯正则是 ReDoS 的经典组合;限制输入长度和回溯步数。
- 正确性:正则语言与 CFL 的边界是理论结论,不是实现细节;不要用“测试通过”替代层级判断。
- 一致性:Unicode 规范化、大小写折叠、locale 会改变“同一个字符串”的判断。