Design the regular expression and DFA that accepts a language in which "110" is no less than "011"

322 Views Asked by At

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?

1

There are 1 best solutions below

0
On

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.