Регулярные выражения Эквивалентность
https://stackoverflow.com/questions/560263
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianВопрос
Есть ли способ узнать, эквивалентны ли два произвольных регулярных выражения?Мне кажется, это сложная проблема, но может быть есть какой-то механизм упрощения DFA или что-то в этом роде?
Решение
Чтобы проверить эквивалентность, вы можете вычислить минимальные DFA выражения и сравните их.
Другие советы
Тестируемость равенства — одно из классических свойств регулярных выражений.(Н.Б.Это не справедливо, если вы на самом деле говорите о регулярных выражениях Perl или о каких-то других технических средствах. нерегулярный сверхязык.)
Превратите свои RE в обобщенные конечные автоматы A и B, затем постройте новый автомат A-B так, чтобы принимающие состояния A имели нулевые переходы в начальные состояния B и чтобы принимающие состояния B были инвертированы.Это дает вам автомат, который принимает все строки, принятые A, за исключением всех тех, которые принимаются B.
Сделайте то же самое для B-A и сократите оба до чистых ЖК.Если FA не имеет принимающих состояний, доступных из начального состояния, то он принимает пустой язык.Если вы можете показать, что и A-B, и B-A пусты, вы доказали, что A = B.
Edit Хех, я не могу поверить, что никто не заметил там гигантскую ошибку - преднамеренную, конечно :-p
Описанные автоматы A-B будут принимать те строки, первая половина которых принимается A, а вторая половина не принимается B.Создание желанный A-B — немного более сложный процесс.Я не могу придумать это сразу, но я знаю, что оно четко определено (и, вероятно, включает в себя создание состояний для представления продуктов принятия состояний в A и непринятия состояний в B).
Это действительно зависит от того, что вы подразумеваете под регулярными выражениями.Как указывали другие авторы, сокращение обоих выражений до минимального DFA должно работать, но это работает только для чистых регулярных выражений.
Некоторые конструкции, используемые в реальных библиотеках регулярных выражений (в частности, обратные ссылки), дают им возможность выражать нерегулярные языки, поэтому алгоритм DFA для них не работает.Например, регулярное выражение: ([a-z]*) \1 соответствует двойному вхождению одного и того же слова, разделенному пробелом (a a и b b но нет b a ни a b).Это вообще не может быть распознано конечным автоматом.
Эти две темы Perlmonks обсуждают этот вопрос (в частности, читайте ответы blokhead):
