如何确定regex是否与另一个regex正交?

你说的“正交”是指“交集是空集”我接受它?

我将构造交集的正则表达式,然后转换为正常形式的正则语法,看看它是否是空语言…

再说一次,我是个理论家…

我将构造交集的正则表达式,然后转换为正常形式的正则语法,看看它是否是空语言…

好像是用大炮射麻雀。为什么不直接构造产品自动机并检查从初始状态是否可以到达接受状态?这也会直接给你一个交叉点的字符串,而不需要先构造一个正则表达式。

当我得知有一个多项式时间解时,我会有点惊讶,当我得知它相当于暂停问题时,我一点也不会惊讶。

我只知道一种方法,它涉及从regexp创建一个dfa,这是指数时间(在退化情况下)。这可以归结为停顿问题,因为一切都是,但停顿问题是 不 理论均可以还原为 它 .

如果是最后一个,那么您可以使用这样一个事实:任何re都可以转换为有限状态机。如果两个有限状态机具有相同的节点集,并且具有连接这些节点的相同圆弧,则它们是相等的。

因此,考虑到我认为你使用的正交定义,如果你把你的res转换成fsms,而这些fsms不相等,那么res是正交的。

那不正确。您可以有两个边缘标记为多重图意义的非同构的dfas(fsms),但接受相同的语言。另外,如果不是这样,您的测试将检查是否接受两个regexp- 完全相同的 ,而op想要非- 重叠 语言(空交集)。

另外,请注意\1、\2、…、\9结构不是常规的:它不能用连接、联合和*(kleene-star)来表示。如果你想包括后替换,我不知道答案是什么。另一个令人感兴趣的事实是,上下文无关语言的对应问题是不可确定的:没有一种算法采用两个上下文无关语法g1和g2,并返回真正的iff l(g1)_(g2)__。

这个问题发布已经两年了,但我很高兴地说,现在可以通过在这里调用“genex”程序来确定这一点: https://github.com/audreyt/regex-genex

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

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

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

希望这有帮助!

让我先说,我不知道如何构造这样的算法,我也不知道任何实现它的库。然而,我一点也不惊讶地发现,对于任意复杂的一般正则表达式来说,不存在这样的表达式。

每一个正则表达式都定义了一个正则语言,它包含了所有可以由表达式生成的字符串,或者如果您愿意的话,也包括所有与正则表达式“匹配”的字符串。把语言看作一组字符串。在大多数情况下,集合将无限大。您的问题是,正则表达式给出的两个集合的交集是否为空。

至少在第一个近似中,我无法想象一种不计算集合就能回答这个问题的方法,对于无限集合来说,这比你所需要的时间要长。我认为可能有一种方法可以计算一个有限的集合,并确定什么时候一个模式被阐述到另一个regex所要求的之外,但这并不简单。

例如,只需考虑简单表达式 (ab)* 和 (aba)*b . 决定生成的算法是什么 abab 从第一个表达式,然后停止,不检查 ababab , abababab 等等,因为他们永远不会工作?在找到匹配项之前,不能只生成字符串和检查,因为当语言不相交时,这永远不会完成。我无法想象在一般情况下会有什么效果,但在这种情况下,还有比我更好的人。

总之,这是个难题。当我得知有一个多项式时间解时,我会有点惊讶,当我得知它相当于暂停问题时,我一点也不会惊讶。尽管,考虑到正则表达式不是图灵完备的,但看起来至少有可能存在一个解决方案。

这个 fsmtools 可以在有限状态机上执行各种操作,唯一的问题是将正则表达式的字符串表示形式转换为fsmtools可以使用的格式。对于简单的情况,这是绝对可能的,但是在像look ahead、behind这样的高级功能的存在下,这是很棘手的。

你也可以看看 OpenFst 尽管我从未用过。但它支持交叉。

在\1,2位上有很好的作用…这是上下文无关的,因此无法解决。小贴士:并不是所有的事情都可以简化为停止…例如,程序等效。布莱恩·波斯托

[我正在回复评论]

IIRC a^n b^m a^n b^m 不是上下文无关的,因此 (a\*)(b\*)\1\2 也不是因为它是一样的。伊斯特尔 { ww | w ∈ L } 即使我是“好的”,也不是“好的”,因为我是 regular , context-free .

我修改了我的声明:一切 在重新 可简化为暂停问题;-)

你可以用类似的东西 Regexp::Genex 要生成测试字符串以匹配指定的regex,然后在第二个regex上使用测试字符串来确定两个regex是否正交。

在某些情况下,证明一个正则表达式与另一个正则表达式是正交的可能是微不足道的,例如在同一位置的互斥字符组。除了最简单的正则表达式,这是一个非常重要的问题。对于严肃的表达式,包括groups和backreference,我会尽可能地说,这可能是不可能的。

我相信 kdgregory 是正确的,你用正交来表示 Complement .

这是正确的吗?

我将执行以下操作:

• 使用如下结构将每个regex转换为fsa:

  struct FSANode
  {
      bool accept;
      Map<char, FSANode> links;
  }
  List<FSANode> nodes;
  FSANode start;
  

请注意,这并不是一件小事,但对于简单的regex来说,不应该那么困难。

• 创建新的组合节点,如:

  class CombinedNode
  {
      CombinedNode(FSANode left, FSANode right)
      {
          this.left = left;
          this.right = right;
      }
  
      Map<char, CombinedNode> links;
      bool valid { get { return !left.accept || !right.accept; } }
  
      public FSANode left;
      public FSANode right;
  }
  

建立链接的基础上遵循相同的字符在左侧和右侧,你会得到两个fsanodes,使一个新的组合节点。

然后从combinednode(leftstart,rightstart)开始,找到跨度集,如果有任何无效的combinednode,则该集不是“正交的”。

将每个正则表达式转换为DFA。从一个dfa的accept状态创建一个epsilon转换到第二个dfa的start状态。实际上,您已经通过添加epsilon转换创建了一个NFA。然后将NFA转换为DFA。如果开始状态不是接受状态,并且接受状态是可到达的,那么这两个正则表达式不是“正交的”。(因为它们的交集不是空的。)

有将正则表达式转换为dfa和将nfa转换为dfa的已知过程。你可以看一本书,比如sipser的《计算理论导论》中的程序,或者只是在网上搜索。毫无疑问,许多本科生和研究生必须为一个或另一个“理论”课做这件事。

我终于找到了我要找的图书馆:

dk.brics.automaton

用途:

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

应该注意的是,该实现不支持也不支持像back-reference这样的复杂regex特性。查看博客帖子 "A Faster Java Regex Package" 它介绍 dk.brics.自动机 .

这似乎是这个词的另一种用法 orthogonal 我已经习惯了。

如果它们以任何方式重叠,你认为它们是正交的吗?或者如果一个是另一个的子集?或者简单地说,如果它们不能用于匹配相同的文本?

如果是最后一个,那么您可以使用这样一个事实:任何re都可以转换为有限状态机。如果两个有限状态机具有相同的节点集,并且具有连接这些节点的相同圆弧,则它们是相等的。

因此,考虑到我认为你使用的正交定义,如果你把你的res转换成fsms,而这些fsms不相等,那么res是正交的。

我说得太早了。我在最初的文章中所说的话是行不通的,但是如果您可以将正则表达式转换为dfa形式,那么您将尝试执行一个过程。

你可以在我在第一篇文章《计算理论导论》第二版中提到的书中找到这个过程。在第46页,脚注中有详细内容。

该过程将为您提供一个新的DFA,它是两个DFA的交集。如果新的DFA有一个可到达的接受状态,那么交集是非空的。