假设我们有正则表达式：
你好W. * rld
你好，世界
。*世界
。* W. *
我想减少匹配任意输入所需的正则表达式的数量。
为此，我需要查找一个正则表达式是否与另一个表达式匹配的任何输入匹配。那可能吗？
比利3
最佳答案
任何正则表达式都可以链接到DFA-您可以最小化DFA，并且由于最小形式是唯一的，因此您可以决定两个表达式是否等效。 Dani Cricco指出了Hopcroft O（n log n）算法。 Hopcroft和Craft还有另一种改进的算法，可以测试O（n）中两个DFA的等效性。
为了对此问题进行一个很好的调查并找到一种有趣的方法，我推荐arXiv的论文Testing the Equivalence of Regular Languages。
以后的编辑：如果您对正则表达式的包含而不是等价感兴趣，我遇到了一篇可能感兴趣的论文：Inclusion Problem for Regular Expressions-我只浏览了一下，但似乎包含解决该问题的多项式时间算法。
关于regex - 是否存在可以确定一种常规语言是否匹配任何输入，另一种常规语言匹配的算法？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/3630203/