Пересечение двух регулярных выражений

Для регулярных выражений, которые фактически являются регулярными (т. Е. Не используют нерегулярные функции, такие как обратные ссылки), вы можете сделать следующее:

1. Преобразуйте регулярное выражение в конечные автоматы (алгоритм для этого можно найти здесь (глава 9), например).
2. Постройте пересечение автоматов (у вас есть состояние для каждого состояния в декартовом произведении состояний двух автоматов. Затем вы переходите между состояниями согласно исходным правилам перехода автоматов. Например, если вы находитесь в состоянии x1y2, вы получить вход a, первый автомат имеет переход x1-> x4 для ввода x, а второй автомат имеет y2-> y3, вы переходите в состояние x4y3).
3. Проверьте, есть ли путь от начального состояния до конечного состояния нового автомата. Если есть, два регулярных выражения пересекаются, иначе они этого не делают.

Теория.

Библиотека Java.

Применение:

 /** * @return true if the two regexes will never both match a given string */ public boolean isRegexOrthogonal( String regex1, String regex2 ) { Automaton automaton1 = new RegExp(regex1).toAutomaton(); Automaton automaton2 = new RegExp(regex2).toAutomaton(); return automaton1.intersection(automaton2).isEmpty(); } 

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

Взяв второй пример: в первом выражении, чтобы перейти из состояния 0 в состояние 1, строка должна начинаться с цифры. Во втором выражении, чтобы перейти из состояния 0 в состояние 1, строка должна начинаться с буквы. Итак, вы знаете, что нет строки, которая приведет вас из состояния 0 в состояние 1 в выражения BOTH. У вас есть ответ.

Взяв первый пример: вы знаете, что если строка начинается с цифры, вы можете перейти из состояния 0 в состояние 1 с помощью обычного выражения. Итак, теперь вы можете устранить состояние 0 для каждого и просто ответить на вопрос для каждого из двух (в настоящее время одного состояния) конечных автоматов.

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

Я считаю, что вы можете решить это с помощью недетерминированного FSM. Если у вашего регулярного выражения был только один переход от каждого состояния к другому, детерминированный FSM мог бы его решить. Но регулярное выражение означает, что, например, если вы находитесь в состоянии 2, тогда, если caracter – это цифра, вы переходите в состояние 3, иначе, если символ – это письмо, которое вы переходите в состояние 4.

Итак, вот что я сделал бы:

1. Решите его для подмножества FSM, которые имеют только один переход из одного состояния в другое. Например, регулярное выражение, которое соответствует как «Bob», так и «bob», и второе регулярное выражение, которое соответствует только «bob» и «boB».

2. Посмотрите, можете ли вы реализовать решение на конечной машине. Я думаю, это должно быть возможно. Вход в состояние представляет собой пару, представляющую переход для одного FSM и переход для второго. Например: состояние 0: если (r1, r2) есть ((«B» или «b»), «b»), то состояние 1. Состояние 1: Если (r1, r2) есть ((«o»), ( «o»)), затем состояние 2. и т. д.

3. Теперь для более общего случая, где, например, состояние два возвращается к состоянию два или более раннее состояние; например, regex 1 распознает только «встречу», но regex 2 распознает «meeeet» с неограниченным количеством e. Вы должны были бы уменьшить их до регулярного выражения 1, распознающего «t» и regex 2, распознающих «t». Я думаю, что это может быть разрешено недетерминированным FSM.

В любом случае, это моя интуиция.

Я не думаю, что это NP-полно, только потому, что моя интуиция подсказывает мне, что вы должны иметь возможность сократить каждое регулярное выражение одним состоянием с каждым шагом.

Возможно. Я столкнулся с ним один раз с аргументом Pellet OWL, изучая семантические веб-технологии.

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

Если он будет найден, то другое регулярное выражение будет соответствовать (а не только), а также подмножеству, с которым будет соответствовать первое регулярное выражение.

Это не очень много решений, но, возможно, это поможет вам.