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