Project ForgeTheory of Computation
Finite Automata & Regular Languages
GATE 2023
Medium
Consider the language L over the alphabet {0,1}, given below: L = {w∈{0,1}* | 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 ____.
4
Explanation
The minimal DFA needs to track the length of the current run of trailing 1's, up to the threshold of 3: states for 0, 1, or 2 consecutive trailing 1's (all accepting), plus one absorbing dead/reject state reached once 3 consecutive 1's occur (non-accepting, stays dead forever). That's exactly 4 states.
Source: GATE CS 2023 (2023)
This question is part of a 15-day revision cycle — sign in and Project Forge will bring it back the day before you'd forget it.