正则表达式比较

Question

有没有什么办法可以比较两个正则表达式的包含，部分重叠，不相交，即我想知道如何比较两个正则表达式。其次，如果正则表达式1包含在正则表达式2中，我可以组合两个正则表达式吗？

Answer 1

假设你有两个表达式A和B，并想看看A是否匹配B所做的事情的一个子集。

您需要计算B的最小化DFA，然后将两个表达式组合成A和B的并，然后计算新表达式的最小化DFA。如果这两个DFA相等，则A匹配B的子集。

本质上，如果不经过构造最小化自动机的过程，您就不能正确地检查这一点。然而，它将为这个问题提供一个可验证的真实答案。

组合这两个表达式可以通过创建一个像(A)|(B)这样的新表达式来完成，如果您的引擎支持的话，也许可以用括号代替非捕获变体。

如果你决定全程去做算法，我写了一系列关于这个过程的文章：

http://binarysculpting.com/2012/02/11/regular-expressions-how-do-they-really-work-automata-theory-for-programmers-part-1/

http://binarysculpting.com/2012/02/15/converting-dfa-to-nfa-by-subset-construction-regular-expressions-part-2/

http://binarysculpting.com/2012/03/21/dfa-state-minimization/

要比较两个自动机，您只需检查状态和转换是否相同。它们应该完全相等。