java - 近似正则表达式等价

Question

理论上，正则表达式等价是一个具有指数空间和时间复杂度的朴素解决方案的难题。但出于实际目的，正则表达式是否有近似等价的度量？

我正在考虑从第一个正则表达式生成随机字符串，然后对照另一个正则表达式进行检查，然后以其他方式重复它。有更优雅的检查吗？

相关链接:

• Regular expressions Equivalence
• https://cstheory.stackexchange.com/questions/20401/sub-optimal-regex-equivalence

PS:我想用 java 编写该方法，但欢迎一般解决方案和想法。

Answer 1

我认为你的解决方案不会完美地工作。

假设您想比较 ".*1" 和 ".*2" 等正则表达式，使用你的天真的算法，它将继续执行而不会停止。

最好使用 NFA ，并将两个正则表达式最小化。

如果您达到类似的 DFA ，那么您可以比较这两个正则表达式。

引用this 与 DFA 等价。

我可以建议的另一种方式:

假设让 S1 和 S2 为要比较的正则表达式。据我所知 S1 将产生一种语言 L1 (由 S1 产生的字符串集)，并且 S2 将产生一种语言 L2 。

我们可以检查两种语言的等效性。

引用Deciding equivalence of regular languages 了解更多详情。