GATE 2023 CS – Question 63
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 ______.
Practise this question in The GATE Grind →
Show answer and explanation
Correct answer: 4
Explanation
Track the number of **consecutive 1s at the end** of the string read so far, but a third consecutive 1 is a failure.
States:
- $q_0$: last symbol was 0 (or start), 0 trailing 1s. Accepting.
- $q_1$: 1 trailing 1. Accepting.
- $q_2$: 2 trailing 1s. Accepting.
- $q_3$: three consecutive 1s have occurred. Dead (non-accepting) state.
Transitions: 0 sends $q_0,q_1,q_2\to q_0$; 1 sends $q_0\to q_1$, $q_1\to q_2$, $q_2\to q_3$; $q_3$ loops on both.
All four states are distinguishable ($q_3$ is rejecting; $q_2$ is distinguished from $q_0$, $q_1$ by the string `1`, and $q_1$ from $q_0$ by the string `11`). Minimum DFA: **4** states.