相关疑难解决方法(0)

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

常规语言在各种操作下关闭,也就是说,如果语言K和L是常规语言,则以下操作的结果也是如此:[...]补语¬L

例如,给定字母{a,b,c},语言的反转(abc*)+是(a |(ac | b | c).*)？

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

?: Q × ? ? Q用英语怎么说？描述什么×和?意思也会有所帮助.

鉴于:

我不知道接受的语言是什么.

从它看,你可以得到几个最终结果:

1.) bb
2.) ab(a,b)
3.) bbab(a, b)
4.) bbaaa

绘制minimal的直接简单方法是什么DFA,它接受与给定语言相同的语言Regular Expression(RE).
我知道可以通过以下方式完成:

Regex ---to----? NFA ---to-----? DFA ---to-----? minimized DFA

但是有没有捷径？像(a+b)*ab