第 4 章 正则语言的性质

泵引理、封闭性、判定性质与 DFA 最小化

Source scope
主要依据教材第 4 章：中文印刷页 85–113，对应 PDF p.98–126。本文将教材中的定理、构造和证明方法整理成可独立学习的版本。

1 0. 本章解决四类问题

学会识别正则语言之后，更重要的是回答：

1. 非正则性：怎样证明一个语言不可能由有限自动机识别？
2. 封闭性：对正则语言做某种运算，结果仍正则吗？
3. 判定性：给定自动机，能否算法化地判断空性、成员性、等价性？
4. 最小化：一个正则语言至少需要多少个 DFA 状态？

2 1. 正则语言的泵引理

2.1 1.1 定理陈述

若 \(L\) 是正则语言，则存在整数 \(n\ge1\)（泵长度），使得任意满足

\[ w\in L,\qquad |w|\ge n \]

的串都可分解为

\[ w=xyz \]

并满足：

1. \(|xy|\le n\)；
2. \(|y|>0\)；
3. 对所有 \(i\ge0\)， \[xy^iz\in L.\]

2.2 1.2 为什么成立

设一个识别 \(L\) 的 DFA 只有 \(n\) 个状态。处理长度至少为 \(n\) 的串时，观察读完前 \(0,1,\dots,n\) 个字符后的 \(n+1\) 个状态。

根据鸽巢原理，必有两个时刻落在同一状态。两次访问同一状态之间读到的非空片段就是 \(y\)。

既然读 \(y\) 会从某状态回到自己，就可以把这个环走任意多次：

\[ xy^iz. \]

2.3 1.3 泵引理证明非正则的逻辑顺序

这是最容易写反量词的一类证明。

要证 \(L\) 非正则：

1. 假设 \(L\) 正则；
2. 令 \(n\) 为泵长度；
3. 由我们选择一个长度至少 \(n\) 的 \(w\in L\)；
4. 对任意满足条件的分解 \(w=xyz\)；
5. 找到某个 \(i\)，使 \(xy^iz\notin L\)；
6. 矛盾。

关键是：分解不是我们选的。

2.4 1.4 典型例子：\(\{0^m1^m\mid m\ge0\}\)

假设该语言正则，泵长度为 \(n\)。取

\[ w=0^n1^n. \]

因为 \(|xy|\le n\)，所以 \(y\) 完全落在前面的 0 区，设 \(y=0^k\)，\(k>0\)。

取 \(i=0\)：

\[ xy^0z=0^{n-k}1^n, \]

0 和 1 数量不同，不在语言中。矛盾。

2.5 1.5 泵引理的限制

泵引理提供的是正则语言的必要条件，不是充分条件。

因此：

• 违反泵引理 $ Rightarrow$ 非正则；
• 满足某种“看起来可泵”的性质，并不能直接推出正则。

3 2. 正则语言的封闭性

3.1 2.1 布尔运算

若 \(L_1,L_2\) 正则，则下列语言也正则：

\[ L_1\cup L_2, \quad L_1\cap L_2, \quad \overline{L_1}, \quad L_1-L_2. \]

3.1.1 乘积自动机

设

\[ A_1=(Q_1,\Sigma,\delta_1,q_1,F_1), \quad A_2=(Q_2,\Sigma,\delta_2,q_2,F_2). \]

构造状态集合

\[ Q_1\times Q_2 \]

并定义

\[ \delta((p,q),a)=(\delta_1(p,a),\delta_2(q,a)). \]

只需改变接受集合即可得到并/交/差等语言。

3.2 2.2 补运算

对一个完整 DFA，把接受和非接受状态互换即可识别补语言：

\[ F' = Q-F. \]

若输入表示是 NFA，不能直接把双圈翻转；应先确定化。

3.3 2.3 反转

若 \(L\) 正则，则

\[ L^R=\{w^R\mid w\in L\} \]

也正则。

一种构造：把 NFA 的边全部反向，原接受状态变为新初始来源，原初态变成接受状态；若原来有多个接受状态，引入新的 \(\varepsilon\) 初态。

3.4 2.4 同态与逆同态

同态 \(h\) 由字母映射扩展到串：

\[ h(a_1a_2\cdots a_k)=h(a_1)h(a_2)\cdots h(a_k). \]

正则语言对同态和逆同态都封闭。

逆同态：

\[ h^{-1}(L)=\{w\mid h(w)\in L\}. \]

它在后面不可判定性、编译与编码问题中非常重要。

4 3. 正则语言的判定性质

因为正则语言有 DFA 这种有限表示，许多问题可以直接转成有限图上的算法。

4.1 3.1 成员性

给定 DFA \(A\) 和串 \(w\)，计算

\[ \hat\delta(q_0,w) \]

并检查是否落入 \(F\)。时间复杂度为 \(O(|w|)\)。

4.2 3.2 空性

\(L(A)=\emptyset\) 当且仅当从初态不可达任何接受状态。

因此做一次 DFS/BFS 即可。

4.3 3.3 无穷性

一个 DFA 的语言无限，当且仅当存在某个从初态可达、又能到达接受状态的环。

直觉：只要在“有效路径”上有环，就能把环重复任意多次产生无限多不同长度的串。

5 4. 状态等价与 DFA 最小化

5.1 4.1 不可区分状态

对 DFA 中状态 \(p,q\)，若对任意 \(w\in\Sigma^*\)，都有

\[ \hat\delta(p,w)\in F \iff \hat\delta(q,w)\in F, \]

则称 \(p,q\) 等价或不可区分。

若存在某个 \(w\) 使一边接受一边拒绝，则 \(w\) 是区分这两个状态的区分串。

5.2 4.2 表填充算法

常用算法：

1. 列出所有无序状态对 \(\{p,q\}\)；
2. 若一个接受、一个不接受，立即标记为可区分；
3. 反复检查未标记对：若对某个符号 \(a\)， \[ \{\delta(p,a),\delta(q,a)\} \] 已标记，则标记 \(\{p,q\}\)；
4. 收敛后，未标记对即为等价状态。

5.3 4.3 最小化算法

完整流程：

1. 删除不可达状态；
2. 求状态等价类；
3. 每个等价类合并为一个状态；
4. 继承转移关系。

5.4 4.4 为什么不能比最小 DFA 更小

最小 DFA 的每个状态代表一种不同的“未来行为”。如果两个状态被错误合并，就存在某个后缀能把它们区分，合并后将无法同时给出正确答案。

这与后面 Myhill–Nerode 思想一致：

一个正则语言需要多少状态，本质上取决于有多少种互不等价的右上下文。

6 5. 证明策略选择

面对“某语言是否正则”，不要默认先用泵引理。

推荐顺序：

1. 能直接构造 DFA/RE：直接证明正则；
2. 能通过闭包性质从已知语言得到：用闭包；
3. 若要证非正则：优先考虑闭包反证；
4. 再考虑泵引理。

例如若 \(L\) 与一个正则语言相交后得到已知非正则语言，则 \(L\) 不可能正则。

7 6. 常见错误

• 泵引理中自己选择 \(x,y,z\)；
• 忘记 \(|y|>0\)；
• 证明补封闭时直接翻转 NFA 接受状态；
• 最小化前不删除不可达状态；
• 把“等价状态”与“状态名字相似”混为一谈；
• 判定无穷性时只检查有没有环，而忽略该环是否位于可接受路径上。

本章概念关系图。

8 7. 本章知识地图

Regular Language
├─ 非正则证明：Pumping Lemma
├─ 封闭性：Boolean / reverse / homomorphism / inverse homomorphism
├─ 判定：membership / emptiness / infiniteness / equivalence
└─ 规范表示：DFA minimization