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

Question

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

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

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

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

Answer 1

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

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

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

Answer 2

Wkipedia article on regular expressions делает состояние

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

, но не дает никаких дополнительных подсказок.

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

Answer 3

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

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

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