2
$\begingroup$

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.

$\endgroup$
  • 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$ – Yuval Filmus 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
3
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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