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

Question

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

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

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

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

Answer 1

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

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

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

Answer 2

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

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

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

Answer 3

В статье Wkipedia о регулярных выражениях указано

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

но больше не дает подсказок.

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