从理论上说，正则表达式的等效性是一个很难解决的难题，它具有天真的解决方案，并且具有指数级的时空复杂度。但是出于实际目的，对正则表达式是否有近似的等效度量？
我正在考虑从第一个正则表达式生成随机字符串，然后对照另一个进行检查，然后以其他方式重复它。有没有更优雅的支票？
相关链接：
Regular expressions Equivalence
https://cstheory.stackexchange.com/questions/20401/sub-optimal-regex-equivalence
PS：我欢迎使用通用的解决方案和想法来用Java编写该方法。
最佳答案
我认为您的解决方案将无法完美运行。
假设您想比较".*1"和".*2"这样的正则表达式，
使用您的幼稚算法，它将继续执行而不会停止。
最好使用NFA，并将两个正则表达式都最小化。
如果达到类似的DFA，则可以比较两个正则表达式。
请参考this等同于DFA。
我可以建议的另一种方法：
假设让S1和S2为要比较的正则表达式。
据我所知S1将产生一种语言L1（由S1产生的字符串集），
并且S2将产生一种语言L2。
我们可以检查两种语言的等效性。
有关更多详细信息，请参考Deciding equivalence of regular languages。
关于java - 近似正则表达式对等，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/20902342/