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

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

11 голосов
/ 12 октября 2011

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

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

^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.

DFA solution

Ответы [ 2 ]

17 голосов
/ 12 октября 2011

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

  1. Создайте DFA M1 для первого языка.
  2. Создайте DFA M2 для второго языка. Подсказка: машинное построение теоремы и набора мощности Клини
  3. Построить DFA M3 для M1, пересекающего M2. Подсказка: декартово произведение Машиностроение
  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) |x в A1 и y в A2}
  5. f3 (s, (x, y)) = (f1 (s, x), f2 (s, y))

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

2 голосов
/ 05 февраля 2012

Я создал реализацию PHP ответа Patrick87.Помимо реализации пересечения с помощью декартовой машины продуктов, я также реализовал альтернативный алгоритм поиска пересечений DFA с использованием De Morgan . 

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

* ! is defined as negation

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

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

EDIT:

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

...