2

The question is to design a language 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?

Tony
  • 5,576

1 Answers1

1

HINT: It’s actually easier to design a suitable DFA directly.

The requirement almost (but not quite: see below) amounts to saying that if the substring $011$ is present, it must extend to a substring $0111^*0$. Suppose for a moment that this is the requirement. Then the DFA should be in an acceptor state until it reads $011$; once it reads $011$, it should remain in a non-acceptor state as long as it continues to read $1$s. As soon as it reads a $0$, however, it’s in the same situation that it would have been in after reading a first input of $0$ and should behave the same way. The $5$-state DFA whose transition table is shown below with acceptor states in red does exactly this.

$$\begin{array}{c|c|c} &0&1\\ \hline \color{crimson}q&q_0&q_1\\ \color{crimson}{q_0}&q_0&q_{01}\\ \color{crimson}{q_1}&q_0&q_1\\ \color{crimson}{q_{01}}&q_0&q_{011}\\ q_{011}&q_0&q_{011} \end{array}$$

However, the actual requirement allows inputs like $1110011$ that have a $110$ before the first $011$, and these are not accepted by the DFA above.

  • Show that every string beginning with $111^*0$ is in the language, and that these are the only strings in the language that are not accepted by the DFA above. Then modify that DFA to accept these strings as well.
Brian M. Scott
  • 616,228