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 trailing consecutive 1s: 0, 1 or 2, plus a dead state after three 1s. These four states are all distinguishable, so the minimum DFA has 4 states.