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
    Oct 5 '13 at 20:36
  • $\begingroup$ Are you aiming at a regular expression or a DFA? $\endgroup$ Oct 5 '13 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
    Oct 5 '13 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
    Oct 5 '13 at 21:40

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$.


This site is temporarily in read only mode and not accepting new answers.

Not the answer you're looking for? Browse other questions tagged .