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

我有一个正则表达式的容器。我想分析它们以确定是否可以生成一个匹配多于一个的字符串。考虑到这个用例，我写了自己的正则表达式引擎，在C++或Python中有没有简单的方法来解决这个问题？如何检测两个正则表达式在可匹配的字符串中是否重叠？

2009-12-04 Joseph Garvin

为了解决这个问题，通过正则表达式来确定你的意思可能很重要。你在谈论特定编程语言使用的正则表达式语法吗？或者更确切地说，“真正的”正则表达式只使用连接，交替和Kleene星？ – PeterAllenWebb 2009-12-04 21:27:35

我很想知道这是可能的最强大的正则表达式类型。 – 2009-12-07 15:06:25

嗨约瑟夫，我实际上正在研究与这个问题有关的博士论文。我想知道你是否可以详细说明你正在追求什么应用。如果需要，我们可以通过电子邮件进一步讨论：buffalo dot edu的mwehar。 – 2016-09-26 05:28:08

有没有简单的方法。

只要你的正则表达式只使用标准功能（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：

正规语言的一些类可以只能由确定性有限自动机，其大小在最短相当于普通表达式的大小增长成倍描述。标准示例是，其中语言L_k由组成，所有字符串在字母{a，b} 的第k个最后一个字母等于a。

顺便说一下，你应该使用OpenFST。您可以创建自动文本作为文本文件，并玩弄最小化，交叉等操作，以查看它们对于您的问题有多高效。已经有开源的regexp-> nfa-> dfa编译器（我记得有一个Perl模块）;修改一个输出OpenFST自动机文件并播放。

幸运的是，有可能避免子集的态爆炸和相交2 NFA直接使用相同的建设作为DFA：

如果A ->a B（在一个NFA，你可以去从状态A到B在交叉

(C,Z)输出字母 'a'）

和X ->a Y（在其他NFA）

(A,X) ->a (B,Y)然后是最后当且仅当C ^在一个NFA中是最后的，而Z在另一个中是最后的。

要关闭此过程，请从两个NFA的启动状态开始，例如， (A,X) - 这是交叉点NFA的开始状态。每次你第一次访问一个状态时，通过上述规则为离开这两个状态的每一对弧产生一个弧，然后访问这些弧到达的所有（新）状态。您将存储事实，即您扩展了状态的弧（例如，在一个散列表中），并最终探索从一开始就可以访问的所有状态。

如果允许小量的转变（即不输出字母），这很好：

如果在第一NFA A ->epsilon B，那么对于每一个国家(A,Y)到达，加上弧形(A,Y) ->epsilon (B,Y)，同样在epsilons第二名NFA。

在将正则表达式转换为NFA时，Epsilon转换对于获得两个NFA的联合是有用的（但不是必需的）;每当你有变化regexp1|regexp2|regexp3，你采取联盟：一个NFA的开始状态有一个epsilon过渡到代表交替的正则表达式的每个NFA。确定NFA的空白很容易：如果您从开始状态进行深度优先搜索时达到最终状态，则它不是空的。

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

来源

2009-12-04 20:34:03

优秀的答案，虽然这几乎正是我希望避免需要编码自己;）OpenFST看起来很整洁。 – 2009-12-12 20:14:16

从理论上讲，你所描述的问题是不可能的。在实践中，如果您拥有使用有限子集或正则表达式语法的可管理数量的正则表达式和/或可用于匹配正则表达式容器的有限字符串选择，那么您可能会能够解决它。

假设您不是试图解决抽象的一般情况，可能有些事情可以解决实际应用。也许如果你提供了一个有代表性的正则表达式样本，并描述了你将要匹配的字符串，可以创建一个启发式来解决这个问题。

来源

2009-12-04 20:58:18 ironchefpython

识别上下文无关语言或更差语言的“正则表达式”使得无法证明交集中没有字符串。显然，这些并不是真正的“正则表达式”，而是受其启发的东西。但是完整的正则表达式语言可以捕获到w/NFA，以及大多数人实际使用的“正则表达式”。 – 2009-12-04 21:03:29

我同意正则表达式可以分解为NFA，我只是认为原始海报可能有一个更具体的用例，比如“c [aeiou] t”和“d [aeiou] g”等正则表达式，以及允许的字符串是英文字典。 – ironchefpython 2009-12-04 21:13:15

This regex inverter（使用pyparsing编写）适用于re语法的有限子集（例如，不允许*或+） - 您可以将两个re倒置为两个集合，然后查找集合交集。

来源

2009-12-04 21:38:43 PaulMcG

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

回答

相关问题