I'm trying to figure out how to build a regular expression for a language that doesn't contain strings that contain $101$ or $001$. The alphabet is defined as $\{0, 1\}$. I'm stuck on trying to figure out the DFA. Any help would be appreciated.

  • 1
    $\begingroup$ Recall that DFAs are closed under complementation. Can you think of a DFA for the complement of the language? If not, can you think of an NFA for the complement? $\endgroup$
    – Shaull
    Commented Oct 5, 2013 at 20:36
  • $\begingroup$ Are you aiming at a regular expression or a DFA? $\endgroup$ Commented Oct 5, 2013 at 21:19
  • $\begingroup$ I'm aiming at the regular expression. I figured out a DFA. It has a lot of accepting states. My regular regular expressions is pretty long. I think I'm doing something wrong but I don't know what exactly. $\endgroup$
    – flashburn
    Commented Oct 5, 2013 at 21:30
  • $\begingroup$ My DFA contains a lot of final states. I know how to convert a DFA into a regular expression when there is only one final state, but I don't know how to do it when there are many. Can someone give me suggestions? $\endgroup$
    – flashburn
    Commented Oct 5, 2013 at 21:40

1 Answer 1


Hint. Let $A = \{0,1\}$. A regular expression for the complement of your language $L$ is $A^*(101 + 001)A^* = A^*A01A^*$. Now, as Shaull reminded you, $L$ and its complement have the same minimal complete DFA, up to the final states. It is actually relatively small.

If you prefer, you could also take a purely combinatorial approach. Observe that the strings you want to avoid are $101$ and $001$. It means that if a word $u$ of $L$ contains the pattern $01$, then $01$ has to be a prefix of $u$. Now find a regular expression for the set of words not containing the pattern $01$ and from there you should be able to find a regular expression for $L$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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