给定一个描述正则语言的正则表达式R（没有花哨的反向引用）。有没有一种算法方法来构造一个正则表达式R*来描述除R描述的所有单词的语言吗？正如维基百科所说，这应该是可能的：
正则语言在各种运算下是封闭的，也就是说，如果语言K和L是正则的，那么以下运算的结果也是：[…] 补码¬L
例如，给定字母表{a,b,c} ，语言(abc*)+的逆是(a|(ac|b|c).*)？
正如 DPenner 在评论中已经指出的那样，正则表达式的逆可以比原始表达式大得多。这使得反转正则表达式不适合实现用于搜索目的的否定部分表达式语法。是否有一种算法可以保留正则表达式匹配的O(n*m)运行时特性（其中n是正则表达式的大小，m是输入的长度）并允许否定子表达式？
不幸的是，nhahdtdh 在评论中给出的答案是我们所能做的（到目前为止）。给定的正则表达式是否生成所有字符串是 PSPACE 完整的。由于 NP 中的所有问题都是 PSPACE 完全的，因此对普遍性问题的有效解决方案将意味着 P=NP。
如果你的问题有一个有效的解决方案，你能解决普遍性问题吗？你当然会。
请注意，“给定一个正则表达式，它是否会生成空集”这个问题相当简单：
{}生成空集。(r + s)生成空集当且仅当且仅r生成s空集。(rs)生成空集当且仅当r或s生成空集。基本上，很容易判断正则表达式是否生成空集：只需开始评估正则表达式即可。
（请注意，虽然上述过程在输出长度方面是有效的，但在输入长度方面可能效率不高，如果输出长度比输入长度快多项式。但是，如果是这种情况，无论如何，我们都会得到相同的结果，即您的算法并不是真正有效的，因为从给定的输入生成指数级更长的输出需要指数级的许多步骤）。
维基百科说：......如果至少存在一个匹配特定集合的正则表达式，那么存在无限数量的此类表达式。我们可以从这个陈述中推断出，除了 R 所描述的那些之外，还有无数个描述所有词的语言的表达式。
同样，（正如@nhahtdh 试图解释的那样）解决这个问题的最简单算法是将评估范围扩展到正则表达式语言本身的上下文之外。即：使用原始正则表达式匹配要排除的字符串（表示要使用的有限子集），然后将任何匹配失败视为实际匹配（在无限的其他可能性中）。因此，如果匹配结果是否定的，则您的候选字符串是有效解决方案的子集。