闭包性质

我们知道，正则语言在并集、连接和Kleene星号运算下仍然是正则的，因为我们能够为其构造出接受这些语言的NFA。描述“运算后仍保持在同一类语言中”这一性质的术语称为封闭性（closure）；正如整数在加法、减法和乘法下封闭一样，我们也说正则语言在并集、连接和Kleene星号运算下是封闭的。

注：如果一个集合在某个运算下的结果仍然属于该集合，则称该集合对该运算是封闭的。

接下来，我们将深入探讨正则语言的封闭性及其他性质，并开发用于判断正则语言的算法。最后，我们会介绍一些非正则的形式语言。

逆转有限自动机

我们知道，通过将接受某一语言的DFA中每个状态的可接受性取反，可以得到其补语言的自动机，从而证明正则语言在补运算下是封闭的。因此，任何正则语言的补语言也是正则的。

我们还可以通过“逆转”自动机的方式来证明：将正则语言中的所有字符串逆转后所形成的新语言仍是正则语言。要逆转一台自动机，需执行以下步骤：

• 移除所有“陷阱状态”（因为当箭头方向反转后，这些状态将无法到达）。
• 如果存在多个接受状态，则创建一个新的唯一接受状态，并通过λ转移从原来的各个接受状态指向它。
• 将原始的起始状态设为新的唯一接受状态。
• 将原始的（现在唯一的）接受状态设为新的起始状态。
• 反转所有边的方向（如果图是广义转移图GTG，则同时反转边上标注的字符串）。

示例：逆转接受语言 $aa^*c^*b^*$ 的自动机

为了说明这一点，我们来逆转一个接受语言 $L = aa^*c^*b^*$ 的自动机。

由于存在多个接受状态，我们首先创建一个唯一的接受状态，并添加来自原接受状态的λ转移。同时移除陷阱状态。

接着，我们反转所有箭头方向，并交换初始状态与终止状态的角色，从而得到如下用于逆转语言的NFA。

该自动机接受的语言为 $b^*c^*a^*a$，这是原语言字符串逆转后的正则表达式。

正则语言的封闭性

由于语言本质上是集合，我们也可以考虑其他集合运算下的封闭性。利用如下集合恒等式，容易证明：只要正则语言在并集和补运算下封闭，就能推出它们在交集和差集运算下也封闭。

由于右侧表达式中使用的运算都保持正则性，因此左侧对应的集合也必然是正则语言。

综上所述，正则语言类在以下运算下是封闭的：

• 并集
• 连接
• Kleene星号
• 补集
• 逆转
• 交集
• 集合差
• 集合对称差

需要注意的是，正则语言的任意子集通常并不一定是正则语言。例如，语言 $\{a^n b^n \mid n \geq 0\}$ 是 $a^*b^*$ 的子集。虽然 $a^*b^*$ 是正则语言，但 $\{a^n b^n \mid n \geq 0\}$ 却不是正则语言。

注意：正则语言的任意子集不一定是正则语言。

集合运算的构造方法

我们可以通过适当修改或组合自动机来实现正则语言的并、连接、Kleene星号、补集和逆转运算。然而，如何构造两个正则语言的交集呢？解决方法是同时追踪两台自动机的状态变化，仅当两台自动机都处于接受状态时，复合状态才被定义为接受状态。

该过程类似于Rabin-Scott的子集构造法，通过构建乘积表（product table），可同时获得并集、交集及各种差集。乘积表方法使用DFA（而非NFA），以两个自动机的起始状态组成的复合状态作为初始状态。对于每一个输入符号，我们追踪两台自动机分别会转移到哪个状态。由于需要精确跟踪每一步状态转移，我们必须使用DFA。

乘积表示例

我们来为两个DFA构造乘积表。第一个DFA接受所有长度为偶数的字符串，如下所示：

第二个DFA接受所有以 $b$ 结尾的字符串，如下所示：

为了同时追踪这两台机器，我们以复合状态 $\{E, q_0\}$ 作为乘积表的初始状态。

读入任意符号后，第一台自动机切换状态（从 $E$ 到 $O$），第二台自动机根据输入 $a$ 或 $b$ 分别转移到 $q_0$ 或 $q_1$。我们将新出现的复合状态加入表格，并继续追踪它们的后续转移。

此时出现了新的状态 $\{E, q_1\}$。继续追踪其转移路径后，得到最终的乘积表如下：

我们通过设定不同的接受状态来实现不同的集合运算。若要求并集，则只要复合状态中包含 $E$ 或 $q_1$ 中的任一接受状态即可，即 $\{E,q_0\}$、$\{O,q_1\}$ 和 $\{E,q_1\}$ 为接受状态。若要求交集，则必须两个分量都为接受状态，因此只有 $\{E,q_1\}$ 是接受状态。

对于第一个语言减去第二个语言的差集，我们需要第一个自动机接受而第二个拒绝，因此只有 $\{E,q_0\}$ 是接受状态。反之，第二个减第一个的差集仅由 $\{O,q_1\}$ 接受。对称差集是上述两个差集的并集，因此 $\{E,q_0\}$ 和 $\{O,q_1\}$ 都应设为接受状态。

关键在于：乘积表/自动机的结构对所有集合运算都是相同的，区别仅在于如何设定复合状态的接受性。

下图展示了交集对应的转移图：

记住：乘积表可用于确定任意两个正则语言的并集、交集和差集。

示例：构造两个语言差集的自动机

我们来构造一个定义在 $\Sigma = \{0,1\}$ 上的语言的自动机，该语言接受所有以 $1$ 开头且不包含子串 $00$ 的字符串。由于这是两个正则语言的差集，结果必定也是正则语言。我们先分别为这两个语言构造自动机。

语言 $L$：所有以 $1$ 开头的比特串，其自动机如下图所示：

语言 $M$：所有包含子串 $00$ 的比特串，其自动机如下图所示：

我们从复合初始状态开始构造乘积表，并追踪可能的路径：

我们关注的是两个语言的差集 $L - M$，因此只保留第一个自动机处于接受状态、而第二个处于非接受状态的复合状态，即 $\{x_1,y_0\}$ 和 $\{x_1,y_1\}$ 为接受状态。对应的转移图如下：

下表总结了如何根据乘积表中的状态来确定两个正则语言 $L$ 和 $M$ 各种集合运算的接受状态：