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

例如,这两个正则表达式可以显示为没有交叉的强力,因为两个解集是可计算的,因为它是有限的.

^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(11)*$} ∩ {11,^(11)*$} = {}
.....

在另一个similar question中,一个answer是计算交集正则表达式.这可以做吗？如果是这样,怎么写一个算法来做这样的事情呢？

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

编辑：

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