Often we are asked to write regular expression for the set of words that contain a certain string pattern, like $aba$. But what about the opposite?
Is there any generic way to write a regular expression for the set of all words that do not contain a certain pattern?


2 Answers 2


Maybe the easiest (though not necessarily fastest, if done by hand) way to do this is to make use of the many equivalent formalisms for regular languages:

  1. Create an NFA that accepts all words that contain the pattern. (This NFA will consist of a chain of transitions that are labeled with the pattern and additionally can loop in the initial or final state on every symbol.)
  2. Transform that NFA into a (complete) DFA using a standard algorithm.
  3. Make all the accepting states of the DFA non-accepting and vice versa.
  4. Translate the inverted DFA into a RE using a standard algorithm.

It's not clear from the question whether you want to know if such a regexp exists, or to find a small regexp.

If you just want to know whether such a regexp exists, the answer is yes; it follows from closure properties for regexps, such as that the complement of a regular language is regular.

If you want to find a minimal regexp, or a small regexp, see Is regex golf NP-Complete? or Smallest DFA that accepts given strings and rejects other given strings.

  • 3
    $\begingroup$ I think the question asks for a generic procedure to generate any RE for the language, not necessarily a short one. $\endgroup$
    – FrankW
    Sep 12, 2014 at 9:30

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