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

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)*$} = {}
.....

在另一个similar question一answer是计算交集正则表达式。那可能吗？如果是这样，如何编写算法来做这样的事情？

我认为这个问题可能是 halting problem 的域.

编辑:

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

Answer 1

它不在停机问题的范围内；判断正则语言的交集是否为空可以这样解决:

1. 为第一语言构建 DFA M1。
2. 为第二种语言构建 DFA M2。 提示:Kleene 定理和幂集机构造
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) 相交。整洁吧？