你如何检查两个正则表达式是否描述相同的模式？

Question

有时你可能会为同一个任务设计出两个不同的正则表达式，我想知道如何检查这两个正则表达式是否描述了相同的模式？

• 有没有一些算法可以进行检查？

• 有没有一些(在线)工具可以进行检查？

例如，在这里有两个正则表达式Can we rewrite lookbehind in terms of the if-then-else?，我想知道它们是否相同。

谢谢。

- Tim

---

我会说那些点踩的人不懂正则表达式，并且不希望别人学习它。 - Tim

使用Python，你可以看一下这里：https://dev59.com/aWEi5IYBdhLWcg3wUa46。 - ForguesR

@ForguesR: 我有时可能需要使用PCRE(PHP)风格的正则表达式（具有比Python风格更多的功能），但我并不很了解PHP。因此，在线工具将是最好的选择。 - Tim

OP：这是一个非常困难的问题。对于计算机科学（理论上的）正则表达式，https://dev59.com/BXRB5IYBdhLWcg3wpotm 和 http://math.stackexchange.com/questions/46975/how-to-prove-two-regular-expressions-are-identical-in-mathematical-way 提供了一些资源。我不知道实际“正则表达式”（如PCRE）是否已经或者能否证明它们在数学意义下等同，因为它们有许多扩展而在定义上并不是真正的正则表达式；鉴于PCRE的强大功能，我怀疑这可能是一个NP完全问题。 - Amadan

@Amadan：PCRE 描述的是哪种语言类型？是无上下文语言、有上下文无关语言还是其他什么类型的语言？因此，我想问这个问题：如何确定由两个 PCRE 正则表达式描述的 xxx 语言是否相同？ - Tim

Answer 1

正则语言的等价性是可判定的（见Hopcroft，Motwani，Ullman：自动机理论、语言和计算导论，第4.4章），这也是最小化DFA的基础。直观地说，如果最小化后的DFA相等（重命名状态除外），那么由正则语言生成/接受的语言也是相同的。所以，你的第一个问题的答案是肯定的。

我确信有在线工具可以做到这点，但在最坏的情况下，您可以要求“flex”或类似工具来最小化自动机，并实现一个简单的工具来检查它们是否可以一致地重命名。

这个SO条目也相关：

正则表达式等价性

- user1666959

---

OP所询问的PCRE，据我所知，至少不完全可以用DFA表示。例如，递归模式。 - Amadan

@amadan：OP 的问题是关于正则语言的（第一个问题），请注意回答的第一段末尾的小心翼翼的限定词。我不清楚 OP 需要多少（1）、他愿意付出多少努力（2）以及他对这些问题的理解程度有多少，因此在深入探讨一个或两个继承者的弱二阶理论或其他同样晦涩难懂的内容之前，我向他指出了相关且非常好的文献。 - user1666959

没错。你可能会注意到我在问题评论中早在三个小时前就指出了同样的事情，所以我并不是不同意你的观点。我只是确保他明白真正的正则表达式和程序员所说的正则表达式之间存在巨大的区别，特别是因为他明确提到了PCRE风格。 - Amadan