1. 形式语言的基本概念
1.1 字母表、符号串与语言
形式语言理论用最少的数学装备描述「什么样的字符串是合法的」，三个基础定义如下：
- 字母表 Σ：非空有穷的符号集合，例如
Σ = {0, 1}或Σ = {a, b, c}。 - 符号串：由 Σ 中符号组成的有穷序列，长度记作
|w|；长度为 0 的串称为空串，记作ε。 - Σ*：Σ 上所有符号串构成的集合，包含 ε。它是无穷但可数的。Σ⁺ 则表示 Σ* 去掉 ε。
- 语言 L：Σ* 的一个子集，即
L ⊆ Σ*。
语言作为集合，天然带有集合运算，同时还有几个专属运算：
| 运算 | 定义 | 例子（L={ab}，M={c}） |
|---|---|---|
| 连接 LM | { xy | x∈L, y∈M } | {abc} |
| 幂 Lⁿ | L 自连接 n 次，L⁰={ε} | L² = {abab} |
| Kleene 闭包 L* | L⁰ ∪ L¹ ∪ L² ∪ … | {ε, ab, abab, …} |
| 反转 Lᴿ | 每个串倒序 | {ba} |
| 同态 h(L) | 对每个符号做替换 | h(a)=0 → {0b} |
关键直觉：几乎所有「语言」都是无穷集合（例如所有合法 C 程序），所以不能枚举，只能用有限规则去描述无穷集合——这就是文法与自动机的意义。
1.2 文法的四元组定义
文法 G 是一个四元组：
G = (V, T, P, S)
- V：变元（非终结符）的有穷集合，常写作大写字母
A, B, S。 - T：终结符的有穷集合，
V ∩ T = ∅。 - P：产生式（规则）的有穷集合，形如
α → β，其中 α 至少含一个变元。 - S：开始符号，
S ∈ V。
推导记作 ⇒：若 uαv 中 α→β 是产生式，则 uαv ⇒ uβv。⇒* 表示零步或多步推导。文法生成的语言为：
L(G) = { w ∈ T* | S ⇒* w }
1.3 为什么工程师要学形式语言
编译器前端的词法分析器本质是 DFA、语法分析器本质是下推自动机；正则引擎（grep、sed、PCRE）就是正则语言的实现或其超集；协议与格式解析（JSON、HTTP 头部、CSV）都靠文法描述；能力边界判断则让你知道「正则做不到什么」，才不会写出注定失败的解析器。
2. 乔姆斯基层级
2.1 四级文法与对应自动机
Noam Chomsky 在 1956 年按产生式的限制强度划分出四级文法，每级恰好对应一类计算模型：
| 类型 | 名称 | 产生式限制 | 对应自动机 | 典型语言 |
|---|---|---|---|---|
| 0 型 | 无限制文法 | α → β，α 含变元 | 图灵机 | 递归可枚举语言 |
| 1 型 | 上下文有关文法 | αAβ → αγβ，γ ≠ ε | 线性有界自动机 | {aⁿbⁿcⁿ} |
| 2 型 | 上下文无关文法 | A → γ（A 为单变元） | 下推自动机 | {aⁿbⁿ} |
| 3 型 | 正则文法 | A → aB 或 A → a | 有限自动机 | {aⁿ}、标识符 |
包含关系是严格的：
3 型 ⊊ 2 型 ⊊ 1 型 ⊊ 0 型
2.2 严格性的见证语言
每一层「严格包含」都可以用具体语言见证，这是理解层级的关键：
{aⁿbⁿ | n ≥ 0}是 2 型但不是 3 型——有限状态记不住「已经数了多少个 a」。{aⁿbⁿcⁿ | n ≥ 0}是 1 型但不是 2 型——一个栈只能配平两种符号。{ww | w ∈ {a,b}*}不是上下文无关的，但可用线性有界自动机识别。- 停机问题语言
HALT是 0 型（递归可枚举）但不是递归的，即不可判定。
2.3 上下文有关文法的等价形式
1 型文法要求「不收缩」（|β| ≥ |α|），工程上更常用等价的单调文法（non-contracting）：只要每条规则右部不短于左部即可（允许 S → ε 的特例），这是证明题里常用的简化手段。
3. 有限自动机
3.1 DFA 的形式定义
确定有限自动机（DFA）是五元组：
M = (Q, Σ, δ, q₀, F)
- Q：有穷状态集。
- Σ：输入字母表。
- δ：转移函数
Q × Σ → Q，每个状态每个符号恰好一条出边。 - q₀：初始状态。
- F ⊆ Q：接受状态集。
确定性体现在：给定当前状态与输入符号，下一状态唯一。
例：识别「含有偶数个 0」的二进制串。
| 状态 | 输入 0 | 输入 1 |
|---|---|---|
| →q₀（偶，接受） | q₁ | q₀ |
| q₁（奇） | q₀ | q₁ |
DFA 可以用 200 行 C 实现核心逻辑：
/* DFA: 识别含偶数个 '0' 的二进制串 */
#include <stdio.h>
typedef enum { EVEN = 0, ODD = 1 } State;
int accepts_even_zeros(const char *s) {
State st = EVEN; /* 初始状态 q0 */
for (; *s; ++s) {
if (*s == '0') st = (st == EVEN) ? ODD : EVEN; /* δ 转移表 */
else if (*s != '1') return 0; /* 非法符号 */
}
return st == EVEN; /* 终态是否属于 F */
}
3.2 NFA 与 ε 转移
非确定有限自动机（NFA）放宽了确定性：
δ : Q × (Σ ∪ {ε}) → 2^Q
一次输入可以转移到多个状态，甚至不消耗输入就转移（ε 转移）。NFA 不增加表达能力，只增加描述便利性。
3.3 子集构造法（NFA → DFA）
核心思想：DFA 的一个状态对应 NFA 的一个状态集合。算法步骤：
- 计算初始状态闭包
ε-closure({q₀})，作为 DFA 起始状态。 - 对每个未处理的状态集 T 与每个符号 a，计算
ε-closure(move(T, a))。 - 若得到新集合，加入 DFA 状态表；重复直到不动。
- DFA 接受状态 = 任何含 NFA 接受状态的集合。
def subset_construction(nfa):
"""nfa: dict {state: {symbol: set(states)}}，'ε' 表示空转移"""
def closure(states):
stack, seen = list(states), set(states)
while stack:
s = stack.pop()
for nxt in nfa.get(s, {}).get('ε', ()): # 沿 ε 传递闭包
if nxt not in seen:
seen.add(nxt); stack.append(nxt)
return frozenset(seen)
start = closure({nfa['start']})
dfa, queue = {start: {}}, [start]
while queue:
cur = queue.pop()
for sym in nfa['alphabet']: # 遍历字母表，避免漏死状态
move = set()
for s in cur:
move |= nfa.get(s, {}).get(sym, set())
if not move:
continue
tgt = closure(move)
dfa[cur][sym] = tgt
if tgt not in dfa:
dfa[tgt] = {}; queue.append(tgt)
return dfa
复杂度提醒：n 个状态的 NFA 最坏会生成 2ⁿ 个 DFA 状态（经典例子是 (a|b)*a(a|b)^(n-1)）。这正是「正则引擎要么吃内存、要么吃回溯」的根源。
3.4 状态最小化
DFA 可用 Hopcroft 算法（O(n log n)）最小化，依据是 Myhill-Nerode 定理：L 是正则的当且仅当其等价类（不可区分的后缀集合）个数有限，该数目就是最小 DFA 的状态数。做法是「划分细化」：先按接受/非接受划分，再不断按转移目标所在块分裂。
4. 正则表达式与正则语言
4.1 四种描述的等价性
Kleene 定理：以下四种描述刻画的语言类完全相同，都叫正则语言：
DFA ≡ NFA ≡ 正则表达式 ≡ 右线性文法
证明链条：正则表达式 →（Thompson 构造）→ NFA →（子集构造）→ DFA →（状态消除法）→ 正则表达式。
4.2 Thompson 构造
把正则表达式的每个运算映射为固定的小 NFA 片段，再用 ε 转移拼接：单个符号 a 是一条标记 a 的边；连接 r1r2 是 r1 接受态 ε 连到 r2 起始态；选择 r1|r2 是新起始态 ε 分叉到两者；闭包 r* 是 r 的接受态 ε 回连到自身起始态并 ε 跳到新接受态。产物是 NFA，状态数约等于正则表达式长度，正好衔接 3.3 节的子集构造。
4.3 正则引擎的两条路线
| 路线 | 代表 | 匹配方式 | 复杂度 | 支持特性 |
|---|---|---|---|---|
| DFA 引擎 | RE2、Rust regex | 并行模拟所有状态 | O(n·m) 有保证 | 不支持反向引用、环视 |
| 回溯引擎 | PCRE、Python re、Java | 深度优先尝试 | 最坏 O(2ⁿ) | 反向引用、环视、递归 |
**灾难性回溯（ReDoS）**是回溯引擎的著名缺陷，例如 (a+)+b 匹配 aaaa...a 会指数爆炸。防御手段：改用 RE2 类引擎、限制输入长度、给正则加超时（Python 3.11+ 的 re.match(pattern, s, timeout=0.5)）、或重写为无嵌套量词的形式。
5. 泵引理
5.1 引理陈述
设 L 是正则语言，则存在常数 p（泵长度，可取为最小 DFA 的状态数），使得任意 w ∈ L 且 |w| ≥ p，都可以写成 w = xyz，满足：
① |y| ≥ 1 （y 非空）
② |xy| ≤ p （xy 落在前 p 个字符内）
③ ∀i ≥ 0, xyⁱz ∈ L （y 可以任意「泵」）
直觉：串足够长时，DFA 在读取前 p 个字符时必然重复经过某个状态，中间那段（y）就是一个回路，可以走任意多次。
5.2 证明不属于的套路
泵引理只能用于证明某语言不是正则的，标准反证流程：
- 假设 L 是正则的，取泵长度 p。
- 精心选择
w ∈ L且|w| ≥ p（选对 w 是全部技巧所在）。 - 说明无论怎么把 w 分成 xyz，只要满足 ①②，就一定有某个 i 使
xyⁱz ∉ L。 - 矛盾，故 L 不是正则的。
5.3 两个经典例子
例一：L = {aⁿbⁿ | n ≥ 0} 不是正则的。
取 w = aᵖbᵖ。由条件 ② 知 y 只含 a（因为 xy 落在前 p 个字符内），设 y = aᵏ, k ≥ 1。则 xy⁰z = aᵖ⁻ᵏbᵖ，a 比 b 少，不属于 L，矛盾。
例二：L = {w | w 中 0 和 1 数量相等} 不是正则的。
取 w = 0ᵖ1ᵖ，同上的推理直接给出矛盾。
5.4 泵引理的局限
泵引理是必要条件而非充分条件：存在满足泵引理的非正则语言，典型是 L = { aⁱbʲcᵏ | i=1 时 j=k，或 i≠1 时 j≠k }。要严格证明正则性，应当用 Myhill-Nerode 定理（找出无穷多个两两不可区分的等价类）。
6. 下推自动机与上下文无关文法
6.1 下推自动机
下推自动机（PDA）在有限状态之外增加一个栈，从而获得「计数」能力：
P = (Q, Σ, Γ, δ, q₀, Z₀, F)
- Γ：栈字母表，Z₀：初始栈符号。
- δ：
Q × (Σ ∪ {ε}) × Γ → 2^(Q × Γ*)，读输入、看栈顶、决定新状态与新栈内容。
PDA 分确定性（DPDA）与非确定性（NPDA），关键差别是：NPDA 恰好对应上下文无关语言，而 DPDA 只能识别确定性上下文无关语言（是 CFG 的真子集，例如 {wwᴿ} 是确定性的，{ww} 不是）。
6.2 上下文无关文法与语法分析
CFG 的规则形如 A → γ，左边永远是单个变元，因此替换不依赖上下文。经典例子是 E → E + T | T、T → T * F | F、F → ( E ) | id，这组规则既刻画了算术表达式的语法，又隐含了优先级（乘除低于加法的推导层级）与结合性（左递归 ⇒ 左结合）。
6.3 二义性
若一个串存在两棵不同的语法分析树，则文法二义。上面的 E/T/F 文法对 id + id * id 无二义，但 E → E + E | E * E | id 就是二义的。二义性不可判定：不存在算法能对任意 CFG 判定其是否二义。工程应对是改写文法（分层消歧）或引入优先级声明（yacc 的 %left）。
6.4 乔姆斯基范式与 CYK 算法
把 CFG 规范化为乔姆斯基范式（CNF），所有产生式只有 A → BC（两个变元）与 A → a（一个终结符）两种形状；任何不含 ε 的 CFG 都能等价转成 CNF。CNF 的直接收益是 CYK 算法（Cocke-Younger-Kasami）可以判定 w ∈ L(G)，复杂度 O(n³·|G|)：
def cyk(grammar, w):
"""grammar: {A: [(B, C), ...]} 二元规则; 终结符规则 {A: {'a'}}
w: 待判定字符串（不含 ε）"""
n = len(w)
if n == 0:
return 'S' in grammar.get('__eps__', ())
# table[i][j] = 从 i 起长度 j+1 的子串能由哪些变元生成
table = [[set() for _ in range(n)] for _ in range(n)]
for i, ch in enumerate(w): # 长度 1：查终结符规则
for A, terms in grammar['term'].items():
if ch in terms:
table[i][0].add(A)
for length in range(2, n + 1): # 长度 2..n
for i in range(n - length + 1):
for k in range(1, length): # 分裂点
left, right = table[i][k - 1], table[i + k][length - k]
for A, rules in grammar['bin'].items():
for (B, C) in rules:
if B in left and C in right:
table[i][length - 1].add(A)
return 'S' in table[0][n - 1]
CYK 是自底向上的动态规划：table[i][j] 表示子串 w[i..i+j] 能由哪些变元推导。工程中更常用 Earley 解析器（O(n³) 通用，对多数文法接近线性）或 GLR（处理二义文法）。
6.5 非上下文无关的语言
{aⁿbⁿcⁿ} 需要两个计数器（栈只能配平两种符号），{ww} 读完后栈已清空无法比对第二段，{aⁱbʲcᵏ | 0≤i≤j≤k} 的多变量不等式也超出 CFG 能力。证明手段是 Ogden 引理（泵引理的加强版，可标记特定位置）或 Parikh 定理的推论。
7. 图灵机与可计算性
7.1 图灵机定义
图灵机把 PDA 的栈换成双向无穷纸带，读写头可以左右移动并改写：
M = (Q, Σ, Γ, δ, q₀, q_accept, q_reject)
δ : Q × Γ → Q × Γ × {L, R}
停机意味着进入 q_accept 或 q_reject。注意图灵机允许永不停机，这是可计算性理论的核心复杂性来源。
7.2 丘奇-图灵论题
任何「有效可计算」的函数，都能由图灵机计算。
这不是数学定理（「有效可计算」是直观概念），而是一个论题。其威力在于给出了计算能力的上界：λ 演算、递归函数、寄存器机、细胞自动机、现代编程语言（忽略内存限制）都与图灵机等价。由此推出的实践结论：
- 没有「比图灵机更强的」通用计算机。
- 用任何语言写出的「通用解析器」都受限于同样的可计算性边界。
7.3 停机问题不可判定
定理：HALT = { ⟨M, w⟩ | M 在输入 w 上停机 } 不可判定。
对角化证明（Cantor 对角线法的计算版本）：
假设存在判定器 H(M, w)：H 停机，输出 true 当且仅当 M(w) 停机
构造 D(M)： if H(M, M) == true: while(1); else: return; // 与 H 反着来
把 D 喂给自己 D(D)：
若 H(D,D)==true → D(D) 死循环，与 H 判断矛盾
若 H(D,D)==false → D(D) 停机， 与 H 判断矛盾
两种情形都矛盾，故 H 不存在。
与自指、罗素悖论同源：只要系统足够强到能谈论自己，就会出现这种「不存在的判定器」。
7.4 归约与不可判定性传播
归约是把问题 A 转成问题 B，使得「B 可判定 ⇒ A 可判定」（等价地：A 不可判定 ⇒ B 不可判定），这是证明新问题不可判定的主力工具，例如 HALT ≤m HALT_EMPTY、HALT ≤m PCP（Post 对应问题）、HALT ≤m 二义性判定。
莱斯定理（Rice’s Theorem）把结论推到极致：任何关于程序语言的「非平凡语义性质」都是不可判定的，例如「程序是否输出 42」「两个程序是否等价」「程序是否访问网络」。这解释了为什么静态分析工具必须近似（宁可误报或漏报），而不可能完美。
7.5 判定与识别的区别
**递归语言（可判定）**指存在总是停机的图灵机判定成员资格；**递归可枚举（可识别）**指存在图灵机接受所有成员、但对非成员可能永不停机（停机问题本身即是）；不可识别则连识别器都不存在（如 HALT 的补集）。关键事实：L 可判定 ⇔ L 与 L̄ 都可识别。HALT 可识别但不可判定，所以 HALT 的补集不可识别。
8. 与编译原理的衔接
8.1 词法分析就是 DFA
编译器前端把源码切成 token，本质是用正则语言描述 token，再用 DFA 扫描：
ID = [a-zA-Z_][a-zA-Z0-9_]*
NUMBER = [0-9]+(\.[0-9]+)?
IF = "if"
工具链是 正则表达式 → NFA →（子集构造）→ DFA →（最小化）→ 转移表。flex 生成的就是一张 DFA 转移表，扫描一遍输入即可（最长匹配靠 DFA 状态回退实现）。
8.2 语法分析就是 PDA
语法分析器读 token 流并构造语法树，用的是 PDA 的两种等价实现：
- 自顶向下：递归下降、LL(1)（用预测分析表）、ANTLR（LL(*)）。
- 自底向上：LR(0)/SLR/LALR(1)、yacc/bison（用栈 + 状态机移进-归约）。
移进-归约本质就是 PDA 的操作：栈对应 PDA 的栈，状态对应有限控制，移进 = 读输入，归约 = 按产生式弹栈压入变元。
# flex + bison 的典型流水线
flex lexer.l # 生成 lex.yy.c （DFA 扫描器）
bison -d parser.y # 生成 parser.tab.c / parser.tab.h （LALR 表）
cc lex.yy.c parser.tab.c -o calc
8.3 超出 CFG 的部分
语法分析之后的分析不再是上下文无关的，需要符号表与类型环境：
- 作用域与变量声明：
{a}是否合法取决于 a 是否在作用域内声明（上下文有关）。 - 类型检查：表达式类型依赖标识符类型，需要属性文法（attribute grammar）或手写语义动作。
- 语言特性越界：C 的 typedef 二义（
a * b;是声明还是乘法）需要 lexer hack；C++ 的模板解析更是公认的上下文有关，只能用「无限回溯」或语义反馈勉强处理。
8.4 解析技术的选型
LL(1) 与 LALR(1) 都是 O(n) 且覆盖面足够，是工程主力（手写递归下降 / yacc）；Earley 可处理任意 CFG，多数情况下接近线性；GLR 额外支持二义文法。PEG 严格来说不等价于 CFG（有序选择不满足交换律），但换来线性时间与无二义性，是不少现代语言工具的选择。
9. 常见陷阱
- 把正则当通用解析器：用正则解析嵌套括号、HTML、JSON 是经典错误。
{aⁿbⁿ}已超出正则能力，嵌套结构必须用栈或递归下降。 - 忽略回溯引擎的复杂度：PCRE 类引擎最坏指数级，用户可控输入会直接导致 ReDoS 拒绝服务。
- 误以为泵引理能证明正则性：泵引理只是必要条件，证明「属于」要用 Myhill-Nerode 或直接构造 DFA。
- 混淆「识别」与「判定」：递归可枚举语言只保证对成员停机，对非成员可能永远运行，这是很多「半判定」算法的根源。
- 以为 CFG 能表达所有语法：类型检查、作用域、C++ 模板都超出 CFG，硬套 yacc 会撞墙。
- 忽略 ε 闭包：子集构造与 Thompson 构造中 ε 转移必须做传递闭包，漏掉会得到错误状态集；同时别忘给 DFA 补上「陷阱状态」。
- CNF 转换丢失 ε 规则：CYK 判定空串需要单独处理
S → ε的情形，否则w = ε会误判。
参考文章
继续阅读
探索更多技术文章
浏览归档，发现更多关于系统设计、工具链和工程实践的内容。