Regular expression for a string not containing a set of substrings

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.

• 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? – Shaull Oct 5 '13 at 20:36
• Are you aiming at a regular expression or a DFA? – Yuval Filmus Oct 5 '13 at 21:19
• 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. – flashburn Oct 5 '13 at 21:30
• 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? – 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$.