如何确定正则表达式是否与另一个正则表达式正交？

Question

我想我的问题最好用一个(简化的)例子来解释.

正则表达式1:

^\d+_[a-z]+$

正则表达式2:

^\d*$

正则表达式1 永远不会匹配正则表达式2匹配的字符串.因此,假设正则表达式1 与正则表达式2 正交.

正如许多人通过正交问我的意思,我会试着澄清一下:

设S1是正则表达式1匹配的(无限)字符串集. S2是正则表达式2匹配的字符串集.如果 S1和S2的交点为空,则正则表达式2与正则表达式1正交.正则表达式^\d_a $ 不是正交的,因为字符串'2_a'在集合S1 和 S2中.

如果两个正则表达式彼此正交,那么如何以编程方式确定它？

最好的情况是一些实现如下方法的库:

/**
 * @return True if the regex is orthogonal (i.e. "intersection is empty"), False otherwise or Null if it can't be determined
 */
public Boolean isRegexOrthogonal(Pattern regex1, Pattern regex2);

Answer 1

通过"正交"你的意思是"交叉点是空集"我接受了吗？

我会为交集构造正则表达式,然后转换为普通形式的常规语法,看看它是否为空语言...

再说一遍,我是一个理论家......

Answer 2

我会为交集构造正则表达式,然后转换为普通形式的常规语法,看看它是否为空语言...

这似乎是用大炮射击麻雀.为什么不构建产品自动机并检查接受状态是否可以从初始状态到达？这也会立即在十字路口给你一个字符串,而不必先构造一个正则表达式.

我会有点惊讶地发现有一个多项式时间解决方案,而且我不会惊讶地发现它等同于停止问题.

我只知道一种方法,它涉及从正则表达式创建DFA,这是指数时间(在退化情况下).这是还原到停机问题,因为一切都是,但停机问题是不是还原到它.

如果是最后一个,则可以使用任何RE可以转换为有限状态机的事实.如果两个有限状态机具有相同的节点集,则它们是相等的,具有连接这些节点的相同弧.

因此,考虑到我认为您正在使用的正交定义,如果将RE转换为FSM并且这些FSM不相等,则RE是正交的.

那不对.您可以在边缘标记的多图形意义上使用两个非同构的DFA(FSM),但接受相同的语言.此外,如果不是这样,您的测试将检查两个正则表达式是否接受不相同,而OP需要非重叠语言(空交集).

另外,请注意\ 1,\ 2,...,\ 9结构不是常规的:它不能用连接,联合和*(Kleene星)表示.如果你想包括替换,我不知道答案是什么.同样令人感兴趣的是,无上下文语言的相应问题是不可判定的:没有算法采用两个无上下文语法G1和G2,并且如果L(G1)∩L(g2)≠Ø则返回true.

Answer 3

这个问题发布已经两年了,但我很高兴地说现在只需在这里调用"genex"程序即可确定:https://github.com/audreyt/regex-genex

$ ./binaries/osx/genex '^\d+_[a-z]+$' '^\d*$'
$

空输出意味着没有与两个正则表达式匹配的字符串.如果它们有任何重叠,它将输出整个重叠列表:

$ runghc Main.hs '\d' '[123abc]' 
1.00000000      "2"
1.00000000      "3"
1.00000000      "1"

希望这可以帮助!

Answer 4

我终于找到了我正在寻找的图书馆：

dk.金砖国家.自动机

用法：

/**
 * @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();
}

应该注意的是，该实现不支持也不能支持复杂的正则表达式功能，例如反向引用。请参阅博客文章“A Faster Java Regex Package”，其中介绍了dk.brics.automaton。