理论上,正则表达式等价是一个具有指数空间和时间复杂度的朴素解决方案的难题。但出于实际目的,正则表达式是否有近似等价的度量?
我正在考虑从第一个正则表达式生成随机字符串,然后对照另一个正则表达式进行检查,然后以其他方式重复它。有更优雅的检查吗?
相关链接:
- 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
。
我们可以检查两种语言的等效性。
关于java - 近似正则表达式等价,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/20902342/