complexity-theory - 用于计算描述两个正则表达式交集的 DFA 大小的多项式时间算法？

Question

与正则表达式本身的 DFA 相比，描述两个正则表达式交集的 DFA 可能呈指数级增长。（这里有一个很好的 Python 库来计算它。）有没有一种方法可以在不需要指数资源的情况下计算交集的 DFA 大小？

标签： complexity-theoryregular-language

Answer 1

来自维基百科：

普遍性：是 LA = Σ* 吗？[…] 对于正则表达式，对于单例字母表来说，普遍性问题已经是 NP 完全的。

如果我没看错，它说确定正则表达式是否生成所有字符串的问题已知是 NP 完全的。

现在，对于您的问题：考虑已知两个输入正则表达式生成相同正则语言的情况（也许表达式相同）。那么你的问题就归结为：这个 RE 的 DFA 的大小是多少？判断 RE 是否至少生成一些字符串（即语言是否为空）相对简单。如果语言不为空，则当且仅当 RE 生成所有字符串时，对应于 RE 的最小 DFA 具有一种状态。

因此，如果您的问题具有一般多项式时间解决方案，您将能够解决正则表达式的普遍性，而维基百科说这是不可能的。

（如果您不是询问最小 DFA，而是由特定最小化技术产生的 DFA，我认为您必须指定最小化技术）。