Problem constructing a DFA

Question

I have just started learning about DFAs and regular languages, and have had some success with constructing simple ones such as ensuring an even number of 1's and 0's but have got a bit confused trying to design a DFA which will accept two (or more) consecutive 0's and no consecutive 1's. my terrible attempt. I am aware this is not correct but could someone help point out in what ways I have went wrong? Thank you in advance.

Answer 1

Because you have the transition $q_1\overset{1}\longrightarrow q_1$, your DFA will accept $11001$: since this has two consecutive $1$s, it should not be accepted. And because the only way to reach the acceptor state $q_4$ is via the transition $q_3\overset{1}\longrightarrow q_4$, every string that is accepted must contain a $1$, meaning that $00$, which ought to be accepted, won’t be.

If $q_1$ is the initial state, the $0$- and $1$-transitions out of it clearly must go to different states. Moreover, neither of them can go back to $q_1$. I already pointed out why the $1$-transition can’t go back to $q_1$. The $0$-transition from $q_1$ can’t loop back to $q_1$, because then $q_1$ would have to be both an acceptor state (to accept $00$) and a non-acceptor state (to reject $0$). Thus, we can start like this:

$$\begin{array}{c|c|c} \text{state}&0&1\\ \hline q_1&q_2&q_3\\ \end{array}$$

I’ll start by following the $0$ branch. A second $0$ must take us to an acceptor state, so it will have to be a new state, $\color{crimson}{q_4}$. (I’ll use color to mark an acceptor state.) A $1$, though gets us no further towards an acceptable string than an initial $1$ would have done: we might as well go to $q_3$.

$$\begin{array}{c|c|c} \text{state}&0&1\\ \hline q_1&q_2&q_3\\ q_2&\color{crimson}{q_4}&q_3\\ \end{array}$$

Getting a $0$ while in $q_3$ is no different from getting an initial $0$: we still haven’t had two consecutive $0$s, but we also aren’t dead yet with two consecutive $1$s. Thus, we can go to $q_2$. Getting a $1$, though, is fatal: it should send us to a ‘garbage’ state, a non-accepting dead end state. Since that state is a dead end, every input should just loop it back to itself. I’ll make that one $q_5$.

$$\begin{array}{c|c|c} \text{state}&0&1\\ \hline q_1&q_2&q_3\\ q_2&\color{crimson}{q_4}&q_3\\ q_3&q_2&q_5\\ q_5&q_5&q_5 \end{array}$$

Now what should happen when we’re at $\color{crimson}{q_4}$? That means that we’ve seen at least two consecutive $0$s and have not seen two consecutive $1$s, so further inputs of $0$ without intervening $1$s should be accepted, and we should be able to loop at $\color{crimson}{q_4}$. An input of $1$ still leaves us with an acceptable word, so it has to go to an acceptor state (and therefore not to $q_3$), but it clearly can’t loop at $\color{crimson}{q_4}$: that would let us accept $0011$, for instance. It needs to go to a new acceptor state, $\color{crimson}{q_6}$.

$$\begin{array}{c|c|c} \text{state}&0&1\\ \hline q_1&q_2&q_3\\ q_2&\color{crimson}{q_4}&q_3\\ q_3&q_2&q_5\\ \color{crimson}{q_4}&\color{crimson}{q_4}&\color{crimson}{q_6}\\ q_5&q_5&q_5 \end{array}$$

If we’re at $\color{crimson}{q_6}$, we’ve seen at least one pair of consecutive $0$s, but we’ve just read a $1$. A $0$ input at this point leaves us with an acceptable string that does not end in $1$, so we can go back to $\color{crimson}{q_4}$; a $1$ input, on the other hand, kills the string, and we can go to $q_5$, the garbage state.

$$\begin{array}{c|c|c} \text{state}&0&1\\ \hline q_1&q_2&q_3\\ q_2&\color{crimson}{q_4}&q_3\\ q_3&q_2&q_5\\ \color{crimson}{q_4}&\color{crimson}{q_4}&\color{crimson}{q_6}\\ q_5&q_5&q_5\\ \color{crimson}{q_6}&\color{crimson}{q_4}&q_5 \end{array}$$

Each state actually encodes a specific status:

• $q_1$: no input yet
• $q_2$: current input ends in $0$, we’ve not yet seen two consecutive $0$s, and we’ve not yet seen two consecutive $1$s
• $q_3$: current input ends in $1$, we’ve not yet seen two consecutive $0$s, and we’ve not yet seen two consecutive $1$s
• $\color{crimson}{q_4}$: current input ends in $0$, we’ve seen two consecutive $0$s, and we’ve not seen two consecutive $1$s
• $q_5$: we’ve seen two consecutive $1$s, and the string is dead
• $\color{crimson}{q_6}$: current input ends in $1$, we’ve seen two consecutive $0$s, and we’ve not seen two consecutive $1$s

When designing a DFA, it’s often helpful to think through what statuses are significant and to assign a state to each in just this way.