Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|cite|improve this question
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
up vote 2 down vote accepted

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.

share|cite|improve this answer
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

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.