1

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?

Community
  • 1
aplavin
  • 591
  • Isn't $a?b={ab,b}$? Then you want all words not containing $b$, i.e. $a^*$. – Hagen von Eitzen Sep 09 '12 at 10:55
  • No, $a?b = a {a,b} b$ ($?$ is any symbol). – aplavin Sep 09 '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 09 '12 at 10:58
  • 1
    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". – hmakholm left over Monica Sep 09 '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 09 '12 at 15:48

1 Answers1

2

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.

Hagen von Eitzen
  • 374,180
  • 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 09 '12 at 11:02
  • 2
    @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. – hmakholm left over Monica Sep 09 '12 at 14:35