两个正则表达式的交集

Question

我正在寻找一个函数（最好是PHP），如果存在的字符串符合regexpA和regexpB，则返回true。

示例1：

$regexpA = '[0-9]+';
$regexpB = '[0-9]{2,3}';

< p > hasRegularsIntersection($regexpA,$regexpB) 返回 TRUE，因为 '12' 匹配了这两个正则表达式

示例 2：

$regexpA = '[0-9]+';
$regexpB = '[a-z]+';

hasRegularsIntersection($regexpA,$regexpB) 返回FALSE，因为数字永远不会与字面量匹配。

感谢任何解决此问题的建议。

Henry

- Henry

---

嗯...大多数正则表达式（或真正的正则表达式）等价于有限自动机。我想知道，如果给定两个在相同字母表上的这样的自动机，是否可以判断是否存在某个字符串被两者都接受。就我个人而言，我没有看到一种通用的方法，除非暴力枚举所有长度为1、2、3、4、5...的字符串，但总的来说这可能需要“永远”才能检查完。 - Hamish Grubijan

我非常确定你必须使用暴力破解。 - rfusca

@rfusca：在无限可能输入的列表上进行暴力破解是显然不可判定的。如果没有交集，暴力算法将永远不会终止。 - sepp2k

@Hamish：完全可以找到两个有限自动机（FA）的交集（因此也是两个正则语言的交集）。唯一的问题是，今天的大多数编程语言中的正则表达式引擎实际上具有允许您匹配非正则语言的功能（反向引用是常见的一个功能）。我很确定php的正则表达式引擎就是其中之一。因此，如果Henry使用有限自动机创建解决方案，则该解决方案将无法适用于所有正则表达式，仅适用于仅使用正则特性的那些表达式。 - sepp2k

@sepp2k，我很想知道如何找到两个FA的交集，并检查生成的Frankenstein是否接受任何内容。被接受的语言可以是无限的，至少FA可以用有限数量的位表示。 - Hamish Grubijan

Answer 1

对于实际上是规则的正则表达式（即不使用不规则功能如反向引用的正则表达式），您可以执行以下操作：

1. 将正则表达式转换为有限自动机（例如，可以在此处找到该算法（第9章））。
2. 构建自动机的交集（您需要为两个自动机状态的笛卡尔积中的每个状态创建一个状态。然后根据原始自动机的转换规则在状态之间进行转换。例如，如果您在状态x1y2中，并输入a，第一个自动机具有输入x的转换x1-> x4，第二个自动机具有y2-> y3，则转换为状态x4y3）。
3. 检查新自动机中是否存在从起始状态到结束状态的路径。如果存在，则两个正则表达式相交，否则它们不相交。

- sepp2k

---

或者，使用《龙书》中的正则表达式转DFA算法来创建DFA，您可以一步完成：如果任何接受状态由两个表达式的位置组成，则这两个表达式相交。 - Ron Burk

Answer 2

理论.

Java库.

用法:

/**
 * @return true if the two regexes will never both match a given string
 */
public boolean isRegexOrthogonal( String regex1, String regex2 ) {
   Automaton automaton1 = new RegExp(regex1).toAutomaton();
   Automaton automaton2 = new RegExp(regex2).toAutomaton();
   return automaton1.intersection(automaton2).isEmpty();
}

- Karol Król

Answer 3

一个正则表达式指定了一个有限状态机，可以识别可能无限的字符串集合。 字符串集合可能是无限的，但状态数必须是有限的，因此您可以逐个查看状态。

以第二个示例为例：在第一个表达式中，要从状态0到状态1，字符串必须以数字开头。在第二个表达式中，要从状态0到状态1，字符串必须以字母开头。因此，您知道没有字符串会使您从两个表达式的状态0到状态1。你已经得到了答案。

以第一个示例为例：如果字符串以数字开头，则可以使用任何一个正则表达式将其从状态0转换为状态1。因此，现在您可以消除每个正则表达式的状态0，并且只需为两个（现在状态较小的）有限状态机回答问题。

这看起来很像众所周知的“停机问题”，您知道对于图灵机或等效机而言，在一般情况下是不可解的。但实际上，对于有限状态机，停机问题是可解的，因为存在有限数量的状态。

我相信您可以用非确定性FSM解决这个问题。 如果您的正则表达式每个状态到下一个状态仅有一个转换，那么确定性FSM可以解决它。但是，正则表达式意味着例如，如果您在状态2，则如果字符是数字，则转到状态3，否则如果字符是字母，则转到状态4。

所以这是我会做的：

1.为只有一个从一个状态到下一个状态的FSM子集解决它。例如正则表达式匹配“Bob”和“bob”，第二个正则表达式仅匹配“bob”和“boB”。

2.查看是否可以在有限状态机中实现该解决方案。我认为这应该是可能的。状态的输入是表示一个FSM的转换和第二个FSM的转换的一对。例如：State 0：如果（r1，r2）是（（“B”或“b”），“b”）则State 1。 State 1：如果（r1，r2）是（（“o”），（“o”））则State 2。等等。

3.现在针对更一般的情况，例如第二个状态返回到第二个状态或较早状态；例如，正则表达式1仅识别“meet”，但正则表达式2识别具有无限数量“e”的“meeeet”。您将不得不将它们缩小为正则表达式1仅识别“t”和正则表达式2仅识别“t”。我认为这可以通过非确定性FSM解决。

那就是我的直觉。 我不认为它是NP完全的，只是因为我的直觉告诉我您应该能够在每个步骤中将每个正则表达式缩短一个状态。

- Mark Lutton

---

正如sepp2k所指出的那样，这仅适用于确实只识别正则表达式的正则表达式。 - Mark Lutton

Answer 4

这是可能的。我在学习语义网技术时，曾经遇到过使用Pellet OWL推理器的情况。

这里有一个例子，展示了如何将正则表达式解析为树形结构。你可以（理论上）将两个正则表达式解析成树形结构，并查看一个树是否是另一个树的子集，即一个树是否可以在另一个树的节点中找到。

如果找到了，则另一个正则表达式将匹配（不仅仅是）第一个正则表达式将匹配的子集。

这不是一个很好的解决方案，但也许能帮到你。

- mqchen

---

这很有趣，但是...一旦你有了这棵树，接下来该怎么做呢？ - Hamish Grubijan

查看两个正则表达式的语法树并不能告诉你它们是否等价。两个正则表达式可以有完全不同的语法树，但仍然是等价的（例如 /(1+|0+)+/ 和 /0(0|1)*|1(1|0)*/）。 - sepp2k

嗯，我有点困惑。/(1+|0+)+/和/0(0|1)*|1(1|0)*/怎么可能匹配同一个字符串呢？第一个正则表达式要求字符串以1开头，而另一个则要求以0开头。（我现在有点累，所以可能完全错了...） - mqchen

@mq.chen：这两个正则表达式都等同于/(1|0)+/（或者/(0|1)+/，是同一件事情）。请注意竖杠符号“|”，这两个正则表达式都可以以1或0开头。 - sepp2k