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

Question

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

Answer 1

Для проверки эквивалентности можно вычислить minimal DFAs для выражений и сравнить их ,

Answer 2

Эти два Perlmonks темы обсудить этот вопрос (в частности, прочитать ответы blokhead в):

• Comparative satisfiability of regexps
• Testing regex equivalence

Answer 3

Испытание равенства является одним из классических свойств регулярных выражений. (NB Это не имеет место, если вы на самом деле говорите о Perl регулярных выражениях или каком-либо других технически нерегулярной superlanguage.)

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

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

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

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

Answer 4

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

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