给定一个正则表达式R它描述了一种常规语言（没有花哨的反向引用）。有没有一种算法方法来构造正则表达式R*描述除以下描述的单词之外的所有单词的语言R？应该可以作为维基百科 http://en.wikipedia.org/wiki/Regular_language says:
常规语言在各种操作下是封闭的，也就是说，如果语言K and L是正则的，所以以下运算的结果也是正则的：[...] 补码¬L
例如，给定字母表{a,b,c}，语言的逆(abc*)+ is (a|(ac|b|c).*)？
正如 DPenner 已经在评论中指出的那样，正则表达式的逆表达式可以比原始表达式指数大。这使得逆正则表达式不适合实现用于搜索目的的负部分表达式语法。有没有一种算法可以保留O(n*m)运行时特性（其中n是正则表达式的大小，m是正则表达式匹配的输入长度）并允许否定子表达式？
不幸的是，nhahdtdh 在评论中给出的答案已经是我们所能做的最好的了（到目前为止）。给定的正则表达式是否生成所有字符串都是 PSPACE 完整的。由于 NP 中的所有问题都是 PSPACE 完备的，因此普遍性问题的有效解决方案意味着 P=NP。
如果你的问题有一个有效的解决方案，你能解决普遍性问题吗？当然你会的。
- 使用高效的算法生成否定的正则表达式；
- 确定生成的正则表达式是否生成空集。
请注意，“给定一个正则表达式，它是否生成空集”这个问题相当简单：
- 正则表达式
{}生成空集。
-
(r + s)生成空集当且仅当r and s生成空集。
-
(rs)生成空集 iff 或者r or s生成空集。
- 没有其他东西会生成空集。
基本上，很容易判断正则表达式是否生成空集：只需开始评估正则表达式即可。
（请注意，虽然上述过程在输出长度方面是有效的，但如果输出长度比输入长度快超过多项式，则在输入长度方面可能效率不高。但是，如果是这种情况，无论如何，我们都会得到相同的结果，即您的算法并不是真正有效，因为它需要指数级的许多步骤才能从给定的输入生成指数级更长的输出）。
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
