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

Question

给出一个描述常规语言的正则表达式R(没有花哨的反向引用).有没有一种算法来构造一个正则表达式R*来描述除R描述的所有单词之外的所有单词的语言？它应该是可能的维基百科说:

常规语言在各种操作下关闭,也就是说,如果语言K和L是常规语言,则以下操作的结果也是如此:[...]补语¬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)生成空集 iffr或者s生成空集。
4. 没有其他东西会生成空集。

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

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