鉴于两个正则表达式，确定一个是否是其他的补充

Question

我想知道如何判断一些正则表达式是否是另一个正则表达式的补充。假设我有2个正则表达式r_1和r_2。我当然可以从每个DFA中创建一个DFA，然后检查以确保L（r_1）！= L（r_2）。但这并不一定意味着r_1是r_2的补充，反之亦然。此外，似乎许多不同的正则表达式可能是单个正则表达式的相同补充。所以我想知道如果给出两个正则表达式，我可以确定一个是否是另一个的补充。这对我来说也是新的，所以也许我错过了一些显而易见的东西。

编辑：我应该指出，我不是简单地试图找到正则表达式的补充。我有两个正则表达式，我将确定它们是否是彼此的补充。

Answer 1

这是一种概念上简单的方法，如果不是非常有效（不一定是更有效的解决方案......）：

1. 分别为正则表达式r和s构造NFA M和N.您可以使用有限自动机描述相同语言的证明中引入的结构来完成此操作。
2. 确定M和N以得到M'和N'。我们不妨在这一点上继续并最小化它们......给予M''和N''。
3. 使用机器M''和N''上的笛卡尔积机构造构造机器C.接受将由对称差异或XOR标准确定：产品机器中的接受状态对应于状态对（m，n），其中两个状态中的一个恰好在其自动机中接受。
4. 最小化C并调用结果C'
5. 如果L（r）= L（s）'，那么C'的初始状态将是接受的，并且C'将具有始于初始状态的所有转变也终止于初始状态。如果是这种情况，

为什么要这样做？两组的对称差异恰好是一组中的一切（不是两者，也不是两者）。如果L（s）和L（r）是互补的，则不难看出对称差异包括所有字符串（根据定义，集合的补集包含不在集合中的所有内容）。假设现在存在非互补集，其对称差异是所有字符串的宇宙。这些集合不是互补的，因此（1）它们的并集是非空的，或者（2）它们的并集不是所有字符串的宇宙。在情况（1）中，对称差异将不包括共享元素;在情况（2）中，对称差异将不包括缺失的字符串。因此，只有互补集的对称差异等于所有字符串的范围;并且所有字符串集的最小DFA将始终具有自循环的接受初始状态。

Answer 2

补码：L（r_1）==！L（r_2）