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

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

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

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

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

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

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

我认为这个问题可能是停止问题.罢工>

EDIT:

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

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

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

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

EDIT:

因此，要构建笛卡尔积机，您需要两个 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) 相交。整洁吧？