Из Википедия:
Универсальность: LA = Σ *? […] Для регулярных выражений проблема универсальности уже NP-полна для одноэлементного алфавита.
Если я правильно понял, это говорит о том, что проблема определения того, порождает ли регулярное выражение все Известно, что строки являются NP-полными.
Теперь к вашей проблеме: рассмотрим случай, когда известно, что два входных регулярных выражения генерируют один и тот же регулярный язык (возможно, выражения идентичны). Тогда ваша проблема сводится к следующему: каков размер DFA для этого RE? Относительно просто сказать, генерирует ли RE хотя бы несколько строк (т. Е. Является ли язык пустым). Если язык не пустой, то минимальный DFA, соответствующий RE, имеет одно состояние тогда и только тогда, когда RE генерирует все строки.
Таким образом, если бы ваша задача имела общее решение за полиномиальное время, вы могли бы решить универсальность для регулярных выражений, что, по словам Википедии, невозможно.
(Если вы не спрашивая о минимальных DFA, но DFA, создаваемых с помощью определенной c методики минимизации, я думаю, вам придется указать метод минимизации).