我有一个正则表达式容器。我想对它们进行分析，以确定是否有可能生成一个匹配多个字符串的字符串。考虑到没有用这个用例编写我自己的regex引擎，在C++或Python中是否有简单的方法可以解决此问题？
最佳答案
没有简单的方法。
只要您的正则表达式仅使用标准功能(我认为Perl允许您在匹配中嵌入任意代码)，您就可以从每个代码中生成一个nondeterministic finite-state automaton (NFA)，它对RE匹配的所有字符串进行紧凑编码。
给定任何一对NFA，可以确定它们的交点是否为空。如果交集不为空，则某些字符串匹配该对中的两个RE(反之亦然)。
标准可判定性的证明是先将它们确定为DFA，然后构造一个新的DFA，其状态是两个DFA的状态对，并且其最终状态恰好是该对中的两个状态都在其原始DFA中处于最终状态。另外，如果您已经展示了如何计算NFA的补数，则可以(用DeMorgan的法则样式)通过complement(union(complement(A),complement(B)))获得交点。
不幸的是，NFA-> DFA涉及潜在的指数爆炸(因为DFA中的状态是NFA中状态的子集)。从Wikipedia:
顺便说一句，您绝对应该使用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转换(不输出字母)，那很好:
如果在第一个NFA中添加了A ->epsilon B，则对于到达的每个状态(A,Y)，添加弧形(A,Y) ->epsilon (B,Y)，第二个NFA中也添加了epsilons。
当将正则表达式转换为NFA时，Epsilon转换在合并两个NFA时非常有用(但不是必需的)。每当您有交替regexp1|regexp2|regexp3时，就采用并集:NFA，其起始状态向代表该交替中的正则表达式的每个NFA都有一个epsilon过渡。
确定NFA是否为空很容易:如果您从起始状态开始进行深度优先搜索时达到了最终状态，那么它就不是空的。
这个NFA交集类似于有限状态换能器的组成(换能器是一个NFA，它输出成对的符号对，它们成对连接以匹配输入和输出字符串，或将给定的输入转换为输出)。
关于c++ - 如何检测两个正则表达式在它们可以匹配的字符串中是否重叠？，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/1849447/