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

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

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

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

В другом подобном вопросе один ответ должен был рассчитать регулярное выражение пересечения. Можно ли это сделать? Если да, то как написать алгоритм, чтобы сделать такую вещь?

~~Я думаю, что эта проблема может быть доменом проблема с остановкой.~~

EDIT:

Я использовал принятое решение для создания DFA для примера проблемы. Довольно легко понять, как вы можете использовать BFS или DFS на графике состояний для M_3, чтобы определить, доступно ли конечное состояние из M_3.

Ответ 1

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

Построить DFA M1 для первого языка.
Построить DFA M2 для второго языка. Подсказка: Теорема Клин и построение машины Power Set.
Построить DFA M3 для M1, пересечь M2. Подсказка: Cartesian Product Machine construction
Определите, является ли 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, где...

E3 = E
Q3 = Q1 x Q2 (упорядоченные пары)
q0 '' = (q0, q0 ')
A3 = {(x, y) | x в A1 и y в A2}
f3 (s, (x, y)) = (f1 (s, x), f2 (s, y))

Если бы я не совершал никаких ошибок, L (M3) = L (M1) пересекали L (M2). Аккуратно, да?

Ответ 2

Я создал ссылку PHP ответа Patrick87. В дополнение к внедрению Intersection через Cartesian Product Machine я также применил альтернативный алгоритм для поиска пересечений DFA, используя De Morgan.

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

* ! is defined as negation

Это очень хорошо подходит для DFA, поскольку отрицание полностью определенного DFA (с учетом всех возможных состояний перехода) заключается только в том, чтобы добавить все не конечные состояния в конечный набор состояний и удалить все текущие конечные состояния из конечного состояния set (окончательный → окончательный, окончательный → не окончательный). Союз DFA можно легко сделать, превратив их в NFA, а затем создав новый стартовый node, который соединяет объединенные стартовые узлы DFA с помощью лямбда-преобразований.

В дополнение к решению проблемы пересечения библиотека которую я создал, также может определять NFA для DFA и преобразовывать Regex в NFA.

EDIT:

Я создал webapp, который допускает такие преобразования в языках регулярных выражений, используя то, что я узнал, из этого вопроса (и других).