regex - 有没有办法否定正则表达式？

Question

给定一个描述正则语言的正则表达式 R(没有花哨的反向引用)。是否有一种算法方法可以构造一个正则表达式 R* 来描述除 R 描述的所有单词之外的所有单词的语言？应该可以是 Wikipedia说:

The regular languages are closed under the various operations, that is, if the languages K and L are regular, so is the result of the following operations: […] the complement ¬L

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

---

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

Answer 1

不幸的是，nhahdtdh 在评论中给出的答案是我们所能做的(到目前为止)。给定的正则表达式是否生成所有字符串都是 PSPACE 完全的。由于 NP 中的所有问题都是 PSPACE 完全的，因此普适性问题的有效解决方案意味着 P=NP。

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

1. 使用您的高效算法为否定生成正则表达式；
2. 判断生成的正则表达式是否生成空集。

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

1. 正则表达式 {} 生成空集。
2. (r + s) 生成空集当且仅当 r 和 s 生成空集。
3. (rs) 生成空集当且仅当 r 或 s 生成空集。
4. 没有其他任何东西生成空集。

基本上，判断正则表达式是否生成空集非常容易:只需开始评估正则表达式即可。

(请注意，虽然上述过程在输出长度方面是有效的，但如果输出长度比输入长度快多项式，则它在输入长度方面可能效率不高。但是，如果那是在这种情况下，无论如何我们都会得到相同的结果，即您的算法并不是真正有效，因为从给定输入生成指数级更长的输出需要指数级的许多步骤)。