Взаимоисключающие регулярные выражения

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

То есть список действителен тогда и только тогда, когда для всех строк максимум один элемент в списке будет соответствовать всей строке.

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

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


regex mutual-exclusion
person captncraig    schedule 03.06.2010    source источник
comment
возможный дубликат Как определить, перекрываются ли два регулярных выражения в строках, которым они могут соответствовать?   -  person ire_and_curses    schedule 03.06.2010
comment
Думаю, я неправильно понял. Вы имеете в виду, что два заданных регулярных выражения должны быть полностью взаимоисключающими для любой входной строки? То есть, что из 2 ^ 32 возможных четырехбайтовых строк регулярное выражение может соответствовать только одной возможности? Разве это не то же самое, что сказать: найти именно эту строку?   -  person Abel    schedule 03.06.2010
comment
Я имею в виду, что пересечение регулярных выражений должно быть равно нулю. Ни одна строка не соответствует более чем 1 регулярному выражению.   -  person captncraig    schedule 03.06.2010
comment
Кроме того, я должен отметить, что я говорю о допустимых регулярных выражениях С#.   -  person captncraig    schedule 03.06.2010
comment
Тогда я боюсь, что мой первоначальный ответ все еще остается в силе (и последний абзац ответа Джима). Вы не можете этого сделать просто из-за самой природы этих регулярных выражений C# (которые являются NFA). (PS: я удалил свой, так как он был слишком дерьмовым. Иди к Джиму)   -  person Abel    schedule 03.06.2010

Ответы (3)


arrow_upward
7
arrow_downward

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

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

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

person Jim Lewis    schedule 03.06.2010
comment
Интригующая мысль. Я думаю, что вы фактически скрещиваете мечи с Джеффри Фридлом, который сказал (стр. 157), что говорить о сопоставлении DFA очень скучно. Вы только что снова сделали его интересным (примите, что DFA все еще сильно вас ограничивает)! - person Abel; 03.06.2010
comment
Вот чего я боялся. Хотя очень интересный ответ. - person captncraig; 03.06.2010

arrow_upward
1
arrow_downward

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

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

но не дает никаких дополнительных намеков.

Конечно, самый простой способ — запустить множество тестов, но все мы знаем о недостатках тестирования как метода доказательства.

person High Performance Mark    schedule 03.06.2010
comment
Я полагаю, что CaptnCraig хочет знать, есть ли у языков непустое пересечение, а не идентичны ли они. - person Jim Lewis; 03.06.2010

arrow_upward
0
arrow_downward

Вы не можете сделать это, просто взглянув на регулярное выражение.

Рассмотрим случай, когда у вас есть [0-9] и [0-9]+. Очевидно, что это разные выражения, но при применении к строке «1» они оба дают одинаковый результат. Применительно к строке «11» они дают разные результаты.

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

person Seth    schedule 03.06.2010
comment
Применительно к строке 11 они дают разные результаты. на самом деле: это не так, они дают тот же результат. Если вы не добавите привязку. - person Abel; 03.06.2010
comment
Для чистых регулярных выражений то, что запрашивает CaptnCraig, возможно (но может быть неэффективным). Он хочет знать, есть ли у двух регулярных языков (заданных регулярными выражениями) непустое пересечение. Для вашего примера ответ - да. - person Jim Lewis; 03.06.2010
comment
@Abel: я думаю, он имел в виду, что часть строки, которой они соответствуют, отличается. Хотя они оба совпадут. - person Matti Virkkunen; 03.06.2010
comment
Извините, мой вопрос был плохим. Возможно, я хотел спросить, что только один соответствует позиции 0. - person captncraig; 03.06.2010
comment
@Jim: как, по-вашему, можно найти пересечение двух бесконечных множеств? Можете ли вы уточнить? @Matti: действительно, они соответствуют разным частям (если только у вас не жадный движок, но это редко, но бывает) :) - person Abel; 03.06.2010
comment
@CaptnCraig: возможно, вы можете обновить свой q. с примерами? Позиция 0 совпадает с первым символом? Или первая струна? - person Abel; 03.06.2010
comment
@Abel: преобразуйте каждое регулярное выражение в DFA, объедините DFA для создания DFA, распознающего пересечение, затем проверьте, не пусто ли пересечение. Регулярные языки замкнуты относительно пересечения, и это можно доказать за конечное время, даже если языки бесконечны. - person Jim Lewis; 03.06.2010
comment
У меня сложилось впечатление, что регулярным выражениям разрешено перекрываться, но с учетом входных строк им разрешено соответствовать только одному из них и только одному из них. Пока вы доказываете (не)пересечение, пересечение может быть разрешено, если правило основано на входных строках. То есть k* и j* хороши, если введено cat, khaki, joe, а регулярные выражения пересекаются. - person Abel; 03.06.2010