用于计算描述两个正则表达式交集的 DFA 大小的多项式时间算法？
Polynomial time algorithm for computing the size of the DFA describing the intersection of two regular expressions?
与正则表达式本身的 DFA 相比，描述两个正则表达式交集的 DFA 可能呈指数级增长。 （Here's 一个很好的 Python 计算它的库。）有没有一种方法可以计算交集的 DFA 的大小而不需要指数资源？
Universality: is LA = Σ* ? […] For regular expressions, the universality problem is NP-complete already for a singleton alphabet.
如果我没看错，它说确定正则表达式是否生成所有字符串的问题已知是 NP 完全问题。
现在，对于您的问题：考虑已知两个输入正则表达式生成相同正则语言（可能表达式相同）的情况。那么你的问题就简化为：这个 RE 的 DFA 的大小是多少？判断 RE 是否至少生成一些字符串（即语言是否为空）相对简单。如果语言不为空，则当且仅当 RE 生成所有字符串时，对应于 RE 的最小 DFA 才有一个状态。
因此，如果您的问题有多项式时间的一般解决方案，您将能够解决正则表达式的普遍性问题，维基百科说这是不可能的。
（如果您不是在询问最小 DFA，而是通过特定最小化技术生成的 DFA，我认为您必须指定最小化技术）。
与正则表达式本身的 DFA 相比，描述两个正则表达式交集的 DFA 可能呈指数级增长。 （Here's 一个很好的 Python 计算它的库。）有没有一种方法可以计算交集的 DFA 的大小而不需要指数资源？
Universality: is LA = Σ* ? […] For regular expressions, the universality problem is NP-complete already for a singleton alphabet.
如果我没看错，它说确定正则表达式是否生成所有字符串的问题已知是 NP 完全问题。
现在，对于您的问题：考虑已知两个输入正则表达式生成相同正则语言（可能表达式相同）的情况。那么你的问题就简化为：这个 RE 的 DFA 的大小是多少？判断 RE 是否至少生成一些字符串（即语言是否为空）相对简单。如果语言不为空，则当且仅当 RE 生成所有字符串时，对应于 RE 的最小 DFA 才有一个状态。
因此，如果您的问题有多项式时间的一般解决方案，您将能够解决正则表达式的普遍性问题，维基百科说这是不可能的。
（如果您不是在询问最小 DFA，而是通过特定最小化技术生成的 DFA，我认为您必须指定最小化技术）。