Consider the language $L$ over the alphabet $\{0, 1\}$, given below: $$L = \{w \in \{0, 1\}^* \mid w \text{ does not contain three or more consecutive 1's}\}.$$ The minimum number of states in a Deterministic Finite-State Automaton (DFA) for $L$ is __________.

The language $L$ consists of all strings over $\{0, 1\}$ that do not contain the substring $111$.

To construct the minimal DFA for $L$, we track the number of consecutive $1$'s at the end of the processed prefix:

1. State $q_0$ (Start state, Accepting): Represents strings ending in $0$ or the empty string $\epsilon$ (zero consecutive $1$'s).

   • Transition on $0$: goes to $q_0$

   • Transition on $1$: goes to $q_1$

2. State $q_1$ (Accepting): Represents strings ending in a single $1$ (one consecutive $1$).

   • Transition on $0$: goes to $q_0$

   • Transition on $1$: goes to $q_2$

3. State $q_2$ (Accepting): Represents strings ending in $11$ (two consecutive $1$'s).

   • Transition on $0$: goes to $q_0$

   • Transition on $1$: goes to $q_3$

4. State $q_3$ (Dead / Trap state, Non-accepting): Represents strings containing the forbidden substring $111$.

   • Transition on $0$: goes to $q_3$

   • Transition on $1$: goes to $q_3$

### Myhill-Nerode Equivalence Classes: The prefixes $\{\epsilon, 1, 11, 111\}$ are pairwise distinguishable:

• $111 \notin L$, while $\epsilon, 1, 11 \in L$ (distinguished by the empty string $\epsilon$).

• $\epsilon$ and $1$ are distinguished by $z = 11$ ($\epsilon \cdot 11 = 11 \in L$, but $1 \cdot 11 = 111 \notin L$).

• $\epsilon$ and $11$ are distinguished by $z = 1$ ($\epsilon \cdot 1 = 1 \in L$, but $11 \cdot 1 = 111 \notin L$).

• $1$ and $11$ are distinguished by $z = 1$ ($1 \cdot 1 = 11 \in L$, but $11 \cdot 1 = 111 \notin L$).

Thus, exactly 4 states are required in the minimal DFA.