Suppose I have a simple regular expression describing a language like $(a+b)^* a?b (a+b)^*$ (a language in $\Sigma = \{a,b\}$ consisting of all words with substring $a?b$). I haven't found a general way to negate any regular expression, and it seems that no such way exists. There is similar question: A regular expression for the words that don't contain the sequence $ab$ over $\{a,b,c\}$, but the way described there quickly becomes very complicated when regular expression length increases. How to deal with this?
[Math] Negate regular expression
regular expressions
Best Answer
Convert the regular expression to a finite automaton accepting $L$. Then interchange accepting and non-accepting states, which produces an automaton accepting $\Sigma^*\setminus L$. Finally, convert the automaton to a regular expression.