计算两个无限正则表达式解集是否不相交

Question

计算两个任意正则表达式是否有任何重叠的解决方案（假设可能）。

例如，这两个正则表达式可以通过暴力证明没有交集，因为两个解集是可计算的，因为它是有限的。

^1(11){0,1000}$ ∩     ^(11){0,1000}$        = {}
{1,111, ..., ..111} ∩ {11,1111, ..., ...11} = {}
{}                                          = {}

但是用 * 替换 {0,1000} 消除了暴力解决方案的可能性，因此必须创建更智能的算法。

^1(11)*$ ∩ ^(11)*$ = {}
{1,^1(11)*$} ∩ {^(11)*$} = {}
{1,^1(11)*$} ∩ {11,^11(11)*$} = {}
{1,111,^111(11)*$} ∩ {11,^(11)*$} = {}
.....

在另一个类似问题中，有一个答案是计算交集正则表达式。这可能吗？如果是这样，人们将如何编写算法来完成这样的事情？

我认为这个问题可能是停止问题的领域。

编辑：

我已使用公认的解决方案为示例问题创建 DFA。很容易看出如何在 M_3 的状态图上使用 BFS 或 DFS 来确定 M_3 的最终状态是否可达。

Answer 1

它不属于停机问题的范围；判断正则语言的交集是否为空可以如下解决：

1. 为第一种语言构造一个DFA M1。
2. 构建第二语言的 DFA M2。 提示：克林定理和幂集机器构造
3. 为 M1 与 M2 相交构造 DFA M3。 提示：笛卡尔积机器构造
4. 判断L(M3)是否为空。 提示：如果 M3 有 n 个状态，并且 M3 不接受任何长度不大于 n 的字符串，则 L(M3) 为空...为什么？

这些事情中的每一个都可以通过算法完成和/或检查。此外，自然地，一旦 DFA 识别出您的语言的交集，您就可以构建一个正则表达式来匹配该语言。如果您从正则表达式开始，您就可以制作 DFA。这绝对是可以计算的。

编辑：

因此要构建笛卡尔积机，您需要两个 DFA。令 M1 = (E, q0, Q1, A1, f1) 且 M2 = (E, q0', Q2, A2, f2)。在这两种情况下，E 是输入字母表，q0 是起始状态，Q 是所有状态的集合，A 是接受状态的集合，f 是转移函数。构造 M3，其中...

1. E3 = E
2. Q3 = Q1 x Q2（有序对）
3. q0'' = (q0, q0')
4. A3 = {(x, y) | A1 中的 x 和 A2 中的 y}
5. f3(s, (x, y)) = (f1(s, x), f2(s, y))

如果我没有犯任何错误，L(M3) = L( M1) 与 L(M2) 相交。整洁吧？

Answer 2

我创建了 Patrick87 答案的 PHP 实现。除了通过笛卡尔积机实现交集之外，我还实现了一种替代算法，使用

Intersection( DFA_1, DFA_2 ) === ! UNION( ! DFA_1, ! DFA_2 )

* ! is defined as negation

这对于 DFA 来说非常有效，因为完全定义的 DFA（定义了每个可能的过渡状态）的否定只是将所有非最终状态添加到最终状态集中，并从最终状态集中删除所有当前的最终状态（非最终状态）。 -最终->最终，最终->非最终）。通过将 DFA 转换为 NFA，然后创建一个新的起始节点，通过 lambda 变换连接联合 DFA 的旧起始节点，可以轻松完成 DFA 的并集。

除了解决交集问题之外，我创建的库还能够将 NFA 确定为 DFA，并且将正则表达式转换为 NFA。

编辑：

我创建了一个 webapp ，它允许使用我从这个问题（和其他问题）中学到的知识对正则表达式语言进行这种转换。