Consider the following language. $$L = \{w \in \{0, 1\}^* \mid w \text{ ends with the substring } 011\}$$ Which one of the following deterministic finite automata accepts $L$?

To design a minimal DFA that accepts all strings ending with the substring $011$, we define states representing the longest suffix of the input read so far that is a prefix of $011$ [1]:

• State $q_0$ (Start state): Represents suffix $\epsilon$ (no prefix of $011$ matched).

• State $q_1$: Represents suffix $0$.

• State $q_2$: Represents suffix $01$.

• State $q_3$ (Accept state): Represents suffix $011$.

Let us determine the transitions for each state:

1. From $q_0$:

   • On $0 \to q_1$ (suffix becomes $0$)

   • On $1 \to q_0$ (suffix remains $\epsilon$)

2. From $q_1$ (suffix $0$):

   • On $0 \to q_1$ (suffix remains $0$)

   • On $1 \to q_2$ (suffix becomes $01$)

3. From $q_2$ (suffix $01$):

   • On $0 \to q_1$ (suffix becomes $0$)

   • On $1 \to q_3$ (suffix becomes $011$)

4. From $q_3$ (suffix $011$):

   • On $0$: Suffix becomes $0110$. The longest suffix of $0110$ that is a prefix of $011$ is $0$, so it must transition to $q_1$.

   • On $1$: Suffix becomes $0111$. The longest suffix of $0111$ that is a prefix of $011$ is $\epsilon$, so it must transition back to the start state $q_0$.

Evaluating the options based on transitions from $q_3$:

• (A) has a self-loop on $1$ at $q_3$, so it would incorrectly accept strings ending in $0111$.

• (B) has a self-loop on $0, 1$ at $q_3$, which accepts any string containing $011$ as a substring.

• (C) has a transition on $1$ from $q_3$ to $q_2$, which would incorrectly accept $01111$.

• (D) correctly transitions on $0$ to $q_1$ and on $1$ to $q_0$.

Thus, option D is the correct DFA [1].