15

我想我的问题最好用一个（简化的）例子来解释。

正则表达式 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);
4

13 回答 13

9

“正交”是指“交叉点是空集”我接受吗？

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

再说一次，我是理论家...

于 2009-01-28T20:38:55.330 回答
7

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

这似乎是用大炮射麻雀。为什么不直接构建产品自动机并检查是否可以从初始状态到达接受状态？这也将立即在交集处为您提供一个字符串，而无需先构造正则表达式。

得知有多项式时间解决方案我会有点惊讶，而得知它等同于停止问题我一点也不惊讶。

我只知道一种方法，它涉及从正则表达式创建 DFA，这是指数时间（在退化的情况下）。它可以还原为停机问题，因为一切都可以，但是停机问题不能还原为它。

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

因此，鉴于我认为您使用的正交定义，如果您将 RE 转换为 FSM 并且这些 FSM 不相等，则 RE 是正交的。

这是不正确的。您可以有两个在边缘标记的多图意义上是非同构的 DFA (FSM)，但接受相同的语言。此外，如果不是这种情况，您的测试将检查两个正则表达式是否接受不相同，而 OP 想要不重叠的语言（空交集）。

另外，请注意 \1, \2, ..., \9 结构不是规则的：它不能用连接、联合和 *（Kleene 星号）表示。如果你想包括反向替换，我不知道答案是什么。同样有趣的是，上下文无关语言的相应问题是不可判定的：没有算法可以采用两个上下文无关文法 G1 和 G2 并返回真当且仅当 L(G1) ∩ L(g2) ≠ Ø。

于 2009-02-01T17:09:59.003 回答
7

这个问题发布已经两年了，但我很高兴地说，现在只需在此处调用“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"

希望这可以帮助！

于 2011-05-23T16:01:56.093 回答
2

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

您可能还会看看OpenFst，尽管我从未使用过它。不过，它支持交叉点。

于 2009-02-01T16:36:59.647 回答
2

\1, \2 位的优点...这是上下文无关的，因此无法解决。次要观点：并非一切都可以归结为停止......例如程序等效...... – Brian Postow

[我正在回复评论]

IIRC，a^n b^m a^n b^m不是上下文无关的，因此(a\*)(b\*)\1\2也不是，因为它是相同的。{ ww | w ∈ L }即使 L 是“nice”，ISTR也不是“nice”，因为它是regular,中的一个很好context-free。

我修改了我的声明：RE中的所有内容都可以归结为停止问题；-)

于 2009-02-04T08:46:55.413 回答
2

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

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

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

于 2012-10-09T23:30:35.977 回答
1

您也许可以使用Regexp::Genex之类的东西来生成测试字符串以匹配指定的正则表达式，然后在第二个正则表达式上使用测试字符串来确定这两个正则表达式是否正交。

于 2009-01-28T20:17:33.173 回答
1

在某些情况下，证明一个正则表达式与另一个正则表达式正交可能是微不足道的，例如相同位置的互斥字符组。对于除了最简单的正则表达式之外的任何其他表达式，这都是一个不平凡的问题。对于带有组和反向引用的严肃表达，我什至会说这可能是不可能的。

于 2009-01-28T20:23:14.020 回答
1

我相信kdgregory是正确的，您使用 Orthogonal 来表示Complement。

它是否正确？

于 2009-01-28T20:44:29.373 回答
1

首先让我说我不知道​​如何构建这样的算法，我也不知道有任何实现它的库。但是，得知任意复杂性的一般正则表达式不存在这样的情况，我一点也不感到惊讶。

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

至少在第一个近似值上，我无法想象在不计算集合的情况下回答这个问题的方法，对于无限集合来说，这需要比你更长的时间。我认为可能有一种方法可以计算有限的集合并确定何时对模式进行了超出其他正则表达式的要求，但这并不简单。

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

总而言之，这是一个难题。得知有多项式时间解决方案我会有点惊讶，而得知它等同于停止问题我一点也不惊讶。虽然，鉴于正则表达式不是图灵完备的，但似乎至少有可能存在解决方案。

于 2009-01-28T20:46:50.087 回答
1

我会做以下事情：

  • 使用如下结构将每个正则表达式转换为 FSA：

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

请注意，这不是微不足道的，但对于简单的正则表达式来说应该不是那么困难。

  • 创建一个新的组合节点，如：

    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;
}

根据左侧和右侧的相同字符构建链接，您将获得两个 FSANode，它们构成一个新的 CombinedNode。

然后从CombinedNode(leftStart, rightStart)开始，找到spanning set，如果有无效的CombinedNode，则该set不是“正交的”。

于 2009-01-28T20:56:46.183 回答
1

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

有将正则表达式转换为 DFA 以及将 NFA 转换为 DFA 的已知过程。您可以查看 Sipser 的“计算理论导论”之类的书来了解这些过程，或者只是在网上搜索。毫无疑问，许多本科生和研究生必须为一个或另一个“理论”课这样做。

于 2009-02-01T17:21:24.457 回答
0

我说得太早了。我在原始帖子中所说的内容不会奏效，但是如果您可以将正则表达式转换为 DFA 形式，那么您可以尝试执行此操作。

您可以在我在第一篇文章中提到的书中找到该过程：Sipser 的“计算理论导论”第 2 版。它在第 46 页，脚注中有详细信息。

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

于 2009-02-01T17:51:02.417 回答