The GATE Grind

GATE 2023 CS – Question 63

Theory of Computation · Regular Expressions and Finite Automata · 2 marks · Numerical answer

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.

More Regular Expressions and Finite Automata questions

All Regular Expressions and Finite Automata questions →