GATE CSE 2023 Q63: Minimum DFA states for strings without three consecutive 1s

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 _______.

Try it: numerical answer: type the value

Your answer

Numerical answer. No negative marking.

Show answer and explanation

Answer: 4 (official GATE 2023 final answer key)

Concept used: States track the length of the current run of trailing 1s, plus a dead state once 111 appears.

First step: List the distinguishable situations: ends in no 1, one 1, two 1s, or has already seen 111.

Full step-by-step solution

Detailed working, common mistakes and linked mock tests will be available with a free GATEiit account. Log-in is coming soon.

Share this question

Source: official GATE 2023 CS question paper and final answer key, organised by IIT Kanpur. Question paper · Answer key