与两个正则表达式本身的DFA相比，描述两个正则表达式的交点的DFA可能成倍增大。 （Here's一个不错的Python库，用于计算它。）是否有一种方法可以计算交集的DFA大小，而无需占用指数资源？
Universality：是LA =Σ*吗？ […]对于正则表达式，普遍性问题已经是单例字母的NP完全问题。
如果我没看错，它说确定正则表达式是否生成所有字符串的问题已知是NP完全的。
现在，您的问题是：考虑已知两个输入正则表达式生成相同正则语言的情况（也许表达式是相同的）。然后，您的问题就减少了：此RE的DFA大小是多少？判断RE是否生成至少一些字符串（即，语言是否为空）相对简单。如果语言不为空，则当且仅当RE生成所有字符串时，与RE对应的最小DFA才具有一种状态。
因此，如果您的问题有一个通用的多项式时间解，您将能够解决正则表达式的普遍性，维基百科说这是不可能的。
（（如果您不是问最小的DFA，而是由特定的最小化技术产生的DFA，我认为您必须指定最小化技术）。