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: Describe the structure of strings in L

The language L consists of all binary strings that do not contain 111 as a substring. Hence, the only relevant information needed while reading a string is the length of the current suffix of consecutive 1’s, up to length 3.

---

Step 2: Identify necessary distinct situations

While scanning the input from left to right, the string can be in exactly one of the following situations:

• No trailing 1’s (last symbol was 0 or input just started)
• Exactly one trailing 1
• Exactly two trailing 1’s
• Three consecutive 1’s have appeared (string is invalid)

Each situation must be represented by a different state, since future acceptance depends on it.

---

Step 3: Construct the automaton

Define the states:

• q₀: no trailing 1
• q₁: one trailing 1
• q₂: two trailing 1’s
• q_d: forbidden pattern already seen

Input behavior:

• On input 0: reset trailing 1’s → move to q₀ (q_d stays in q_d)
• On input 1: advance to the next state in the chain q₀ → q₁ → q₂ → q_d

Accepting states are q₀, q₁, and q₂.

---

Step 4: Argue minimality

Each state represents a unique future behavior:

• From q₀, the string may still contain up to two 1’s safely
• From q₁, only one more 1 is allowed
• From q₂, no more 1’s are allowed
• From q_d, the string is already rejected regardless of future input

No two of these states can be merged without changing the language accepted. Therefore, the automaton must contain at least four states.

---

Final Answer:

Minimum number of states = 4