Question

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

Hint:

For “forbid $k$ consecutive symbols” over $\{0,1\}$, a minimal DFA typically needs $k+1$ states: one for each count of trailing forbidden symbols ($0$ to $k-1$) plus a dead state.

Answer 1

Step 1: Design a DFA that accepts L.
Track the number of consecutive trailing 1's seen so far (capped at 3):
\[ \begin{array}{ll} q_0: & \text{no trailing 1 (last symbol 0 or start)} \\ q_1: & \text{exactly one trailing 1} \\ q_2: & \text{exactly two trailing 1's} \\ q_d: & \text{dead state: three (or more) consecutive 1's occurred} \end{array} \]
Transitions:
- On input 0: \(q_0 \to q_0\), \(q_1 \to q_0\), \(q_2 \to q_0\), \(q_d \to q_d\).
- On input 1: \(q_0 \to q_1\), \(q_1 \to q_2\), \(q_2 \to q_d\), \(q_d \to q_d\).
Accepting states: \(q_0, q_1, q_2\) (since no run of three 1's yet).
This DFA has 4 states and accepts exactly \(L\).

Step 2: Prove minimality (Myhill–Nerode).
Consider prefixes \(\epsilon, 1, 11, 111\). For each, there exists a distinguishing suffix that separates it from the others wrt membership in \(L\):

- \(\epsilon\) vs \(1\): suffix \(11\). \(\epsilon 11 \in L\) but \(1 11 = 111 \notin L\).
- \(1\) vs \(11\): suffix \(1\). \(1 1 = 11 \in L\) but \(11 1 = 111 \notin L\).
- \(11\) vs \(111\): suffix \(\epsilon\). \(11 \in L\) but \(111 \notin L\).

Thus these four prefixes are pairwise distinguishable ⇒ at least 4 equivalence classes, so any DFA for \(L\) needs \(\geq 4\) states. Our 4-state DFA is therefore minimal.

\[ \boxed{4} \]