regex - 正则表达式比较

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/

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