Подтвердить что ты не робот

Регулярные выражения Эквивалентность

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

4b9b3361

ОТВЕТЫ

Ответ 1

Чтобы проверить эквивалентность, вы можете вычислить минимальные DFA для выражения и сравнить их.

Ответ 2

Проверка на равенство является одним из классических свойств регулярных выражений. (N.B. Это не выполняется, если вы действительно говорите о регулярных выражениях Perl или каком-то другом технически нерегулярном суперязыке.)

Поверните свои RE на обобщенные конечные автоматы A и B, затем постройте новый автомат A-B, чтобы принимающие состояния A имели нулевые переходы в начальные состояния B и что принимающие состояния B инвертированы. Это дает вам автомат, который принимает все те строки, принятые A, за исключением всех тех, которые были приняты B.

Сделайте то же самое для B-A и уменьшите оба до чистых FA. Если FA не имеет принимающих состояний, доступных из состояния начала, тогда он принимает пустой язык. Если вы можете показать, что оба A-B и B-A пустые, вы показали, что A = B.

Edit Хе-хе, я не могу поверить, что никто не заметил гигантскую ошибку там, конечно же, намеренную: -p

Автоматы A-B, как описано, будут принимать те строки, первая половина которых принимается A, а вторая половина не принимается B. Построение желаемого A-B - несколько более сложный процесс. Я не могу думать об этом с ног до головы, но я знаю, что он хорошо определен (и, вероятно, включает в себя создание состояний для представления продуктов принятия состояний в и неприемлемых состояний в B).

Ответ 3

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

Некоторые из конструкций, используемых в реальных regex libs реального мира (в частности, обратные ссылки), дают им возможность выражать нерегулярные языки, поэтому алгоритм DFA не будет работать для них. Например, регулярное выражение: ([a-z]*) \1 соответствует двойному вхождению одного и того же слова, разделенного пробелом (a a и b b, но не b a и a b). Это вообще не может быть распознано конечным автоматом.