给定一个描述常规语言的正则表达式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是输入的长度)的算法,并允许否定的子表达式？
不幸的是,nhahdtdh在评论中给出的答案与我们能做的一样好(到目前为止).给定的正则表达式是否生成所有字符串是PSPACE完成的.由于NP中的所有问题都在PSPACE完成中,所以普遍性问题的有效解决方案将意味着P = NP.
如果有一个有效的解决方案来解决问题,你能解决普遍性问题吗？当然可以.
>使用您的有效算法生成正则表达式的否定;
>确定生成的正则表达式是否生成空集.
请注意,“给定正则表达式,生成空集”的问题是相当简单的：
>正则表达式{}生成空集.
>(r s)生成空集合,如果r和s都生成空集.
>(rs)生成空集合,如果r或s生成空集.
>没有其他东西生成空集.
基本上,很容易判断正则表达式是否生成空集：只需开始评估正则表达式.
(注意,虽然上述过程在输出长度方面是有效的,但是如果输出长度比输入长度多于多数,则输入长度可能不是有效的,但是如果是这样,我们将得到相同的结果,即您的算法不是很有效率,因为从给定的输入生成指数级更长的输出将会呈指数级的很多步骤).
