时间戳

首页 > 解决方案 > 给定两个正则表达式，确定一个是否是另一个的补充

regex - 给定两个正则表达式，确定一个是否是另一个的补充

问题描述

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

编辑：我应该指出，我不只是试图找到正则表达式的补码。给了我两个正则表达式，我要确定它们是否是互补的。

标签： regexcomputation-theorydfa

解决方案

这是一种概念上很简单的方法，即使不是非常有效（并不是说一定有更有效的解决方案......）：

  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）中，对称差异将不包括丢失的字符串。因此，只有互补集的对称差等于所有弦的全域；

推荐阅读