形式陈述

正则语言族对有限并、有限交、补、差、连接、Kleene 星、反转、同态和逆同态封闭。并与交可由乘积自动机构造；补要求先把 DFA 补全，再交换接受与非接受状态；连接和星可用带 $\varepsilon$$\epsilon$ 转移的 NFA；逆同态可在输入符号上模拟其像。所谓封闭，是指对族中语言实施相应运算后仍能由有限自动机识别。

直觉

有限自动机只有有限记忆，把若干有限状态控制器做笛卡尔积、增加有限分支或反向追踪，仍然只产生有限状态，因此正则性得以保持。

例子与边界

若 $L_1$$L_1$ 表示含偶数个 1 的串、$L_2$$L_2$ 表示以 0 结尾的串，则 $L_1\cap L_2$$L_1\cap L_2$ 由状态对识别。补运算不能简单对不完整 DFA 翻转终态，否则缺失转移隐含的拒绝汇状态会被漏掉。正则语言并不对任意无限并或无限交封闭：每个单元素语言 $\{0^n1^n\}$$\{0^n{1}^n\}$ 都正则，但它们的可数并 $\{0^n1^n:n\ge0\}$$\{0^n{1}^n:n\ge 0\}$ 非正则。

推论与应用

封闭性既用于模块化构造词法规则，也用于反证：若假设某语言正则并通过与正则语言求交、取逆同态等操作得到已知非正则语言，即可推出矛盾。

参考资料

• John E. Hopcroft, Rajeev Motwani, and Jeffrey D. Ullman, Introduction to Automata Theory, Languages, and Computation, 3rd ed., Pearson, 2006，Chs. 1–9。
• Michael Sipser, Introduction to the Theory of Computation, 3rd ed., Cengage, 2013，Chs. 0–10。