有没有一种方法可以否定一个正则表达式？

Question

有没有一种方法可以否定一个正则表达式？

regexalgorithmregular-language

16

给定描述正则语言的正则表达式R（没有花哨的反向引用），是否有一种算法方法来构建描述除R描述的所有单词的语言的正则表达式R*？这应该是可能的，因为Wikipedia说：

引用：

常规语言在各种操作下都是封闭的，也就是说，如果语言K和L是常规的，那么以下操作的结果也是常规的：[...]补集¬L

例如，给定字母表{a,b,c}，语言(abc*)+的反转是(a|(ac|b|c).*)?

正如DPenner在评论中已经指出的那样，正则表达式的反转可能比原始表达式指数级更大。这使得反转正则表达式不适合实现用于搜索目的的负部分表达式语法。是否有一种算法可以保留正则表达式匹配的O(n*m)运行时特性（其中n是正则表达式的大小，m是输入的长度），并允许否定的子表达式？

- fuz

7

从正则表达式构建NFA，从NFA构建DFA（应该有一个算法来实现此步骤），将非终止状态变为终止状态，反之亦然，然后从DFA推导出正则表达式。 - nhahtdh

1

与NFA相关的DFA的每个状态都是NFA幂集的可达成员。这使得状态数的上限为2^n，其中n是NFA的状态数。通过构建一个正则语言，可以到达NFA状态的每个子集，从而实现这一点。有一个简单的例子，但我找不到它了。 - fuz

8

请参阅理论计算机科学堆栈溢出上相关问题。NFA->DFA->反转->正则表达式是最坏情况下的最优解。 - thiton

1

这一切都归结为一个编程问题。您可以使用普通（也称为真正常规）正则表达式做很多有趣的事情，而使用“增强”正则表达式则无法做到这一点，例如让不受信任的用户使用它们来搜索内容，因为它们具有保证的线性运行时间。我所知道的所有普通正则表达式工具包都不支持反向匹配，即使它们可以转换为普通正则表达式。很好知道是否有一种算法可以实现“匹配反向”运算符，而不会破坏线性时间复杂度。 - fuz

1

@FUZxxl：考虑对普通正则表达式的扩展，其中可以有普通的正则表达式或仅包含普通正则表达式（甚至没有其他断言）的负向先行断言。我认为复杂性将是相同的。只有当您混合使用普通正则表达式和先行断言时，复杂性才会被打破。 - nhahtdh

显示剩余28条评论

2个回答

1

维基百科表示：......如果存在至少一个正则表达式可以匹配特定集合，则存在无限数量的这样的表达式。我们可以从这个陈述中推断出，存在着描述除R所描述的所有单词的语言的无限数量表达式。

同样地，（正如@nhahtdh试图解释的那样），解决这个问题的最简单算法是将评估范围扩展到正则表达式语言本身之外的上下文中。也就是说：匹配您想要排除的字符串（表示要处理的有限子集）使用原始的正则表达式，然后将任何匹配失败视为实际匹配（其他无限可能性的集合）。因此，如果匹配的结果为负，则您的候选字符串是有效解决方案的子集。

- Alex Filipovici

不是的。只需尝试将字符串与(普通)正则表达式匹配。如果无法匹配，则表示匹配。这仅适用于您特别想要否定整个普通正则表达式的情况。它不能连接。 - nhahtdh

@nhahtdh，我试图重新表述答案。无论如何，我没有看到这个问题的真正应用。 - Alex Filipovici

请查看此评论。 - nhahtdh

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Patrick87 · Accepted Answer

很遗憾，nhahdtdh在评论中给出的答案已经是我们所能做到的（目前为止）。给定正则表达式是否生成所有字符串是PSPACE-完全问题。由于NP中的所有问题都是PSPACE-完全的，因此解决普遍性问题的有效方法将意味着P = NP。

如果您的问题有一个有效的解决方案，您能够解决普遍性问题吗？当然可以。

使用您的高效算法来生成否定的正则表达式;

确定所得到的正则表达式是否生成了空集。

请注意，“给定正则表达式是否生成空集”这个问题相当简单：

1.正则表达式{}生成空集。

2.(r + s)生成空集当且仅当r和s都生成空集。

3.(rs)生成空集当且仅当r或s生成空集。

4.没有其他表达式生成空集。

基本上，很容易判断一个正则表达式是否生成空集：只需要开始评估正则表达式即可。

（请注意，虽然上述过程在输出长度方面是高效的，但如果输出长度比输入长度快多项式级别，则可能在输入长度方面不是高效的。然而，如果是这种情况，我们将得到相同的结果，即您的算法并不真正高效，因为它需要指数步骤才能从给定的输入生成指数级更长的输出。）