您如何检测两个正则表达式在它们可以匹配的字符串中是否重叠？

您如何检测两个正则表达式在它们可以匹配的字符串中是否重叠？

没有简单的方法。

只要您的正则表达式仅使用标准功能（我认为Perl允许您将任意代码嵌入匹配中），您就可以从每个代码中产生一个不确定的有限状态自动机（NFA），该自动机会紧凑地编码RE匹配的所有字符串。

对于任何一对NFA，可以确定它们的交点是否为空。如果交集不为空，则某些字符串匹配该对中的两个RE（反之亦然）。

标准可判定性证明是先将它们确定为DFA，然后构造一个新的DFA，其状态是两个DFA的状态对，而最终状态恰好是该对中的两个状态都在其原始DFA中处于最终状态。另外，如果您已经展示了如何计算NFA的补数，那么您可以（DeMorgan的法律风格）通过来获得交集

complement(union(complement(A),complement(B)))

。

不幸的是，NFA->
DFA涉及潜在的指数爆炸（因为DFA中的状态是NFA中状态的子集）。从维基百科：

某些类的正则语言只能用确定性有限自动机来描述，该自动机的大小在最短等价正则表达式的大小中呈指数增长。标准示例是语言L_k，该语言L_k由字母{a，b}上所有倒数第二个等于a的字符串组成。

顺便说一句，您绝对应该使用OpenFST。您可以将自动机创建为文本文件，并进行诸如最小化，交集等 *** 作，以查看它们对您的问题的效率如何。已经存在开源的regexp->
nfa-> dfa编译器（我记得一个Perl模块）。修改一个以输出OpenFST自动机文件并播放。

幸运的是，可以避免状态子集爆炸，并使用与DFA相同的结构直接相交两个NFA：

如果

A ->a B

（在一个NFA中，您可以从状态A转到B，输出字母“ a”）

和

X ->a Y

（在另一个NFA中）

然后

(A,X) ->a (B,Y)

在十字路口

(C,Z)

如果C在一个NFA中是最终的，而Z在另一个NFA中是最终的，则是最终的。

要开始该过程，请从两个NFA的一对开始状态开始，例如

(A,X)

-这是交叉点-NFA
的开始状态。每次您第一次访问一个状态时，都要根据上述规则为离开这两个状态的每对弧线生成一条弧线，然后访问这些弧线到达的所有（新）状态。您将存储以下事实：您扩展了状态的弧（例如在哈希表中），并最终从头开始探索所有可到达的状态。

如果允许epsilon转换（不输出字母），则可以：

如果

A ->epsilon B

在第一个NFA中，则对于

(A,Y)

到达的每个状态，

(A,Y) ->epsilon(B,Y)

在第二个NFA中添加圆弧，并类似地为epsilon 添加。

当将正则表达式转换为NFA时，Epsilon转换在将两个NFA合并时非常有用（但不是必需的）。每当您进行轮换时，您都

regexp1|regexp2|regexp3

可以采用并集：NFA，其起始状态向表示轮换中的正则表达式的每个NFA都有一个epsilon过渡。

确定NFA是否为空很容易：如果您从起始状态开始进行深度优先搜索时就达到了最终状态，那么它就不是空的。

这个NFA交集类似于有限状态换能器的组成（换能器是一个NFA，它输出成对的符号对，这些符号对成对连接以匹配输入和输出字符串，或将给定的输入转换为输出）。