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

Ответ 1

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

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

Ответ 2

Теория.

Библиотека 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();
}

Ответ 3

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

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

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

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

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

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

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

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

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

Это моя интуиция в любом случае.

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

Ответ 4

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

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

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

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