Вычислить, не пересекаются ли два бесконечных набора решений регулярных выражений

Вычислите, имеют ли два произвольных регулярных выражения какие-либо перекрывающиеся решения (при условии, что это возможно).

Например, можно показать, что эти два регулярных выражения не пересекаются с помощью грубой силы, потому что два набора решений вычислимы, потому что они конечны.

^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 для примера проблемы. Довольно легко увидеть, как вы можете использовать BFS или DFS на графике состояний для M_3 , чтобы определить, достижимо ли конечное состояние из M_3 .