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

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

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

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

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

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

Это не лучшее решение, но, возможно, оно вам поможет.

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

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

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

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

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

Вот что я бы сделал:

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

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

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

Такова моя интуиция, во всяком случае.

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