2
$\begingroup$

This question already has an answer here:

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?

$\endgroup$

marked as duplicate by Raphael Sep 12 '14 at 12:29

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

4
$\begingroup$

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.
$\endgroup$
0
$\begingroup$

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.

$\endgroup$
  • 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 '14 at 9:30

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