GATE 2023 CS Q.63: solution and answer

GATE 2023 · CSQ.63 · 2 marks · NAT

Consider the language $L$ over the alphabet ${0, 1}$ , given below:

L = {w \in {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 ______.

See the question in the paper

Tap to open full size

Answer and solution

ANSWER

The minimum DFA for $L$ has 4 states: three accepting states that count a run of 0, 1 or 2 consecutive 1's, and one non-accepting dead state.

Official answer: 4Source: Official answer key, GATE 2023 CS (IIT Kanpur)

A DFA for $L$ only has to remember how many 1's have been read in a row (0, 1 or 2), and whether a run of three 1's has already occurred.
Let $q_{0}$ mean the current run of 1's has length 0 (the last symbol was 0, or nothing has been read yet). Let $q_{1}$ mean the run has length exactly 1, and $q_{2}$ mean it has length exactly 2. Let $d$ mean three consecutive 1's have been seen. Once that happens, no later symbols can fix it, so $d$ is a dead state.
Transitions: $δ (q_{0}, 0) = q_{0}$ , $δ (q_{0}, 1) = q_{1}$ ; $δ (q_{1}, 0) = q_{0}$ , $δ (q_{1}, 1) = q_{2}$ ; $δ (q_{2}, 0) = q_{0}$ , $δ (q_{2}, 1) = d$ ; $δ (d, 0) = δ (d, 1) = d$ . The start state is $q_{0}$ .
Accepting states are $q_{0}, q_{1}, q_{2}$ , because every string that reaches them has no run of three 1's. The dead state $d$ is non-accepting.
Distinguishability check with suffixes. The empty string $ε$ separates $d$ from the other three states, since $d$ rejects and the others accept. The suffix $1$ separates $q_{2}$ from $q_{1}$ and from $q_{0}$ : from $q_{2}$ it leads to $d$ and is rejected, while from $q_{1}$ it leads to $q_{2}$ and from $q_{0}$ to $q_{1}$ , both accepted. The suffix $11$ separates $q_{1}$ from $q_{0}$ : from $q_{1}$ it leads to $d$ and is rejected, while from $q_{0}$ it leads to $q_{2}$ and is accepted.
All four states are pairwise distinguishable, so no two can be merged and this DFA is minimal. A complete DFA needs the dead state, so the minimum number of states is $4$ .

KEY IDEA

The language needs only a counter of the current run of 1's (0, 1, 2) plus one dead state for "three in a row seen". Minimality follows from showing every pair of states is distinguishable by a suffix.

WATCH OUT FOR

Leaving out the dead state and answering 3. A complete DFA must define a transition from every state on every symbol, so the trap state for "three consecutive 1's seen" counts as a fourth state.

From the GATE 2023 CS paper. Every question of this paper · Download the full paper · All 18 Finite automata questions, with notes

GATE 2023 CS Q.63: solution and answer

Answer and solution

More Finite automata questions