检测两个正则表达式是否可能匹配相同的字符串。

Question

给定两个正则表达式，有可能检测出是否存在任何可以匹配它们两个的字符串吗？例如，给定正则表达式 A 和 . ，我可以看到字符串 "A" 匹配了它们两个。这是一个简单的例子。我的问题是对于更广泛的情况--是否有任何一对有效的正则表达式，可以明确地说是否存在任何可能的字符串可以同时匹配它们两个？假设没有输入字符串样本集来测试，我只有这些正则表达式。我不一定要产生匹配的字符串--我只需要确定是否存在可能的字符串可以同时匹配两个正则表达式。接受任何常见正则表达式规范的讨论--.NET、Java、PERL、sed、grep 等。

- Michael Gunter

---

当你说“是否可能”时，你是指程序员可以找出答案，还是指需要算法的建设性证明？ - Bob Dalgleish

无论哪种方式，我甚至都不确定在正则表达式的广度范围内是否理论上可能。 - Michael Gunter

使用每个正则表达式匹配的位置和长度来确定重叠。 - alpha bravo

@alpha：请重新阅读帖子。我已经修改了一下，让它更加清晰明了。 - Michael Gunter

很抱歉，对于“常见情况”，没有办法：正则表达式可以匹配无限的字符串集合 - 因此它是一个非确定性问题（因为交集可能在有限的算法步骤下无法计算）。 - Alma Do

Answer 1

基本上，您想测试两个正则表达式的交集是否非空。由于交集（就像补集一样）是一个潜在的昂贵操作（它需要确定NFA），因此它并没有在许多正则表达式实现中实现。我知道的一个例外是BRICS Automaton Library，它允许启用交集运算符&。

要测试所述属性，您可以像这样使用BRICS（Java）库：

RegExp re = new RegExp("(.) & (a)", RegExp.INTERSECTION); // Parse RegExp
Automaton a = re.toAutomaton(); // convert RegExp to automaton

if(a.isEmpty()) { // Test if intersection is empty
  System.out.println("Intersection is empty!");
}
else {
  // Print the shortest accepted string
  System.out.println("Intersection is non-empty, example: " + a.getShortestExample(true));
}

- misberner

Answer 2

是的，从理论上讲是可能的。

但基本上需要尝试所有可能的选项，并查看哪些与这两个正则表达式匹配。但这更是一个理论计算机科学问题，使用现代编程语言中的正则表达式将成为NP问题（http://en.wikipedia.org/wiki/NP_(complexity)）

如果您更多地谈论形式语言理论对于正则语言的定义，那么我会说通过将两个正则表达式转换为DFA并同时遍历它们，来查看哪些东西可以匹配。

- Wolph