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

Question

给定两个正则表达式,是否可以检测是否存在与它们匹配的任何可能的字符串？

例如,给定的正则表达式A和.,我可以看到这个字符串"A"匹配他们俩.这是一个简单的案例.

我的问题是针对更广泛的情况 - 给定任何两个有效的正则表达式,是否有可能明确地说是否有任何可能的字符串与两个正则表达式相匹配？假设没有要测试的输入字符串样本集.我只有正则表达式.我不一定需要生成匹配的字符串 - 我只需要确定有可能的字符串匹配两者.

将接受任何常见正则表达式规范的讨论 - .NET,Java,PERL,sed,grep等.

Answer 1

基本上，您想测试两个 RegExp的交集是否为非空。由于交集 - 就像补码一样 - 是一个潜在的昂贵操作（它需要 NFA 的确定性），所以它没有在许多 RegExp 实现中实现。我知道的一个例外是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));
}