Взаимоисключающие регулярные выражения
Если у меня есть список регулярных выражений, есть ли простой способ решить, что никакие два из них обоих не возвратятся достойный той же строки?
Таким образом, список действителен, если и только если для всех строк максимум одного объекта в списке будет соответствовать всей строке.
Кажется, что это будет очень твердо (возможно, невозможный?) для доказательства окончательно но я, может казаться, не ищу никому работу на предмете.
Причина, которую я спрашиваю, состоит в том, что я работаю над токенизатором, который принимает regexes, и я хотел бы удостовериться, что только один маркер за один раз может соответствовать главе входа.
3 ответа
Если вы работаете с чистыми регулярными выражениями (без обратных ссылок или других функций, которые заставляют их распознавать контекстно-свободные или более сложные языки), то, о чем вы спрашиваете, возможно. Что вы можете сделать, так это преобразовать каждое регулярное выражение в DFA, а затем (поскольку обычные языки закрыты при пересечении) объединить их в DFA, который распознает пересечение двух языков. Если этот DFA имеет путь от начального состояния к принимающему, эта строка принимается обоими входными регулярными выражениями.
Проблема в том, что первым шагом обычного алгоритма регулярное выражение-> DFA является преобразовать регулярное выражение в NFA, а затем преобразовать NFA в DFA. Но этот последний шаг может приведет к экспоненциальному увеличению числа состояний DFA, так что это будет только возможно для очень простых регулярных выражений.
Если вы работаете с расширенным синтаксисом регулярных выражений, все ставки отключены: контекстно-свободные языки не закрываются при пересечении, поэтому этот метод не сработает.
В статье Wkipedia о регулярных выражениях говорится, что
можно написать алгоритм, который для двух заданных регулярных выражений решает, являются ли описанные языки по существу одинаковыми, сводит каждое выражение к минимальному детерминированному конечному автомату состояний и определяет, являются ли они изоморфными (эквивалентными).
но не дает никаких дальнейших подсказок.
Конечно, легкий способ, который вы ищете, - это провести много тестов - но мы все знаем недостатки тестирования как метода доказательства.
Вы не можете сделать это, глядя только на регулярное выражение.
Рассмотрим случай, когда у вас есть [0-9] и [0-9]+. Очевидно, что это разные выражения, но при применении к строке "1" они оба дают одинаковый результат. При применении к строке "11" они дают разные результаты.
Дело в том, что регулярное выражение - это недостаточная информация. Результат зависит как от регулярного выражения, так и от целевой строки.