正则语言闭包性质 | Codeboy's Blog

形式陈述

设 $K,L\subseteq\Sigma^*$ 是正则语言。则下列语言运算的结果仍然正则：

K\cup L,\quad K\cap L,\quad \Sigma^*\setminus K, \quad K\setminus L,

KL,\quad K^*,\quad K^R.

此外，若 $h:\Sigma^*\to\Gamma^*$ 是由符号映射延拓的同态，则 $h(K)$ 正则；若 $T\subseteq\Gamma^*$ 正则，则逆像 $h^{-1}(T)$ 也正则。这里的布尔组合都是有限次运算，补集的全集始终是声明的 $\Sigma^*$ 。

布尔闭包可用以笛卡尔积为状态集的乘积 DFA 统一证明。若

M_K=(Q_K,\Sigma,\delta_K,s_K,F_K),\qquad M_L=(Q_L,\Sigma,\delta_L,s_L,F_L),

就令乘积状态为 $(p,q)$ ，并同步更新

\delta((p,q),a)=(\delta_K(p,a),\delta_L(q,a)).

把接受谓词分别取为“ $p\in F_K$ 或 $q\in F_L$ ”“且”“恰有一侧”，即可得到并、交与对称差。补集在完整 DFA 上交换接受态和拒绝态；差集由 $K\cap\overline L$ 得到。

连接与星在ε-NFA上更自然。连接时，从 $K$ 机器的每个接受态加 ε-边到 $L$ 机器初态；取星时，增加可接受空字的新初态，并用 ε-边进入组件和返回重复。反转时反向所有边，用新初态经 ε-边连接原接受态，并把原初态作为唯一接受态。构造所得机器仍有限，再由DFA–NFA 等价可知结果正则。

对同态像，可把每条标号 $a$ 的边替换成一条读取 $h(a)$ 的路径；若 $h(a)=\varepsilon$ ，就使用 ε-边。对逆像，若 $M$ 是识别 $T$ 的 DFA，则在源字母 $a$ 上定义新转移

\delta_h(q,a)=\delta_M^*(q,h(a)).

读完源字 $w$ 后，新机器所在状态正是 $M$ 读完 $h(w)$ 的状态，因此识别 $h^{-1}(T)$ 。

直觉

闭包定理说明有限状态描述可以模块化组合。两个布尔条件要同时监视，就记录两台机器的状态对；两个片段要先后出现，就允许第一台完成时静默进入第二台；一个片段要重复，就把出口接回入口。“仍然有限”的结论具体落实为这些可执行的机器变换，每个新状态保存的信息也随构造明确给出。

不同运算应选择不同表示。交集在 DFA 上只需同步运行，连接在 ε-NFA 上只需接线，表达式上的并和星则几乎直接写出。Kleene 定理保证这些表示最终属于同一语言类，所以证明时不必执着于全程只用一种机器。

闭包只回答能否留在语言类内，不承诺表示规模温和。两个 DFA 的乘积最多有 $|Q_K||Q_L|$ 个状态；NFA 连接很小，若随后确定化却可能指数膨胀。语言仍正则与编译产物是否适合部署，是两个需要分别验证的问题。

例子与边界

词法分析器可以先构造所有 ASCII 标识符的语言 $I$ ，再构造有限关键字集合

W=\{\texttt{if},\texttt{else},\texttt{return},\ldots\}.

普通标识符语言就是 $I\setminus W$ ，仍然正则。实现上可让标识符 DFA 与关键字 trie 的 DFA 同步运行；输入结束时，前者接受且后者拒绝才返回 IDENT。差集准确表达了“形状合法但不是保留字”，无需把关键字排除规则手写进每条路径。

闭包也能反向提供非正则性证书。设

E=\{w\in\{0,1\}^*:|w|_0=|w|_1\}.

若假设 $E$ 正则，那么它与正则语言 $0^*1^*$ 的交集也应正则；但交集恰为 $\{0^n1^n:n\ge0\}$ ，后者可由泵引理或 Myhill–Nerode 证明不正则。因此 $E$ 不正则。闭包在这里负责过滤掉无关排列，把困难核心显露出来。

补集构造必须先补全 DFA。若某状态在字符 x 上没有边，直接翻转接受态不会让含 x 的运行突然有终点；正确做法是加入拒绝死状态并补齐所有缺边，再交换接受集合。对 NFA 直接翻转终态同样错误，因为“存在接受分支”的否定是“所有分支拒绝”。

有限闭包不能推广为任意并。每个 $\{0^n1^n\}$ 都是有限语言，因而正则，但它们对全部 $n$ 的并是非正则语言 $\{0^n1^n:n\ge0\}$ 。同理，闭包清单没有列出的运算不能靠类比断言；必须给出有限构造或反例。

推论与应用

闭包构造直接导出正则语言的多项判定流程。两个 DFA 的等价性等价于其对称差为空；包含关系 $K\subseteq L$ 等价于 $K\cap\overline L=\varnothing$ 。空性只需检查初态能否到达接受态，所以失败时还能从乘积图还原一个具体反例字。

字符串约束求解、词法规则组合和有限日志监控都依赖这些构造。若规格转向无限执行轨迹，仍需重新证明相应 $\omega$ -语言类的闭包；有限字 DFA 的终态翻转和连接接线不能自动成为 Büchi 接受条件下的正确算法。

上下文无关语言的闭包与这里有一个具体分界：两个 CFL 的交可以是非 CFL，例如分别要求 $a,b$ 等长与 $b,c$ 等长的两种语言，其交为 $\{a^nb^nc^n:n\ge0\}$ 。正则语言却对有限交与补都封闭。CFL 与一个正则过滤器求交仍然封闭，因为只需给单栈机器增加有限的乘积控制。

参考资料

John E. Hopcroft, Rajeev Motwani, and Jeffrey D. Ullman, Introduction to Automata Theory, Languages, and Computation, 3rd ed., Pearson, 2006, §3.2 and Chapter 4.
Michael Sipser, Introduction to the Theory of Computation, 3rd ed., Cengage, 2013, §§1.2–1.4.

形式陈述 ​

反向链接

形式陈述