0
$\begingroup$

The question is to design a DFA that accepts a language in which the count of substring "$110$" is no less than the count of substring "$011$". For example, $110$, "0101", "0111101110" is good but "011011" is bad.

The restriction of the language equivalently means whenever a "011" is encountered, only this pattern "$0111^*0$" is allowed, so that a "$011$" is matched with a "$110$". There is no other restriction.

I tried to give a regular expression as $(1^*0111^*0)^* + 1^*0^*$, but I tried very hard but failed to convert this to a DFA. Is there a systematic way to convert such a regular expression to a DFA?

$\endgroup$

marked as duplicate by Hendrik Jan, Evil, David Richerby, Raphael Oct 16 '16 at 18:49

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.

  • $\begingroup$ @HendrikJan this is a duplicate of different questions. RE -> DFA (at the end is the question about systematic conversion). So it goes for the reference one. $\endgroup$ – Evil Oct 16 '16 at 0:04
  • 1
    $\begingroup$ For example here. $\endgroup$ – Evil Oct 16 '16 at 0:15