# Negate regular expression

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?

-
Isn't $a?b=\{ab,b\}$? Then you want all words not containing $b$, i.e. $a^*$. – Hagen von Eitzen Sep 9 '12 at 10:55
No, $a?b = a \{a,b\} b$ ($?$ is any symbol). – aplavin Sep 9 '12 at 10:56
D'oh, if you've encountered DOS wildcards and PERL r.e. in real life, you are doomed to mix things sooner or later. :) – Hagen von Eitzen Sep 9 '12 at 10:58
However @Hagen's meaning of ? is the usual meaning for ? in "regular expressions", and the "any character" meaning is only commonly used in simple patterns that have no repetition constructs and so are not called "regular expressions". – Henning Makholm Sep 9 '12 at 14:38
@HenningMakholm, I have some books about theory of formal languages, and the meaning of $?$ is "any character" in many of them. But in programming-related fields yes, it's as Hagen wrote. – aplavin Sep 9 '12 at 15:48

## 1 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.

-
It's not so easy to build a DFA for $a?b$, and for NFA it's not easy to build a regex... – aplavin Sep 9 '12 at 11:02
@chersanya: The regex-to-DFA is easy enough (and in most practical cases ends with a nice smallish automaton), but DFA-to-regex is very complicated and tends to produce huge resulting regexes. Unfortunately it's the best avaliable general procedure for negating regexes. – Henning Makholm Sep 9 '12 at 14:35