ISRO CS 2023 Q.56: solution and answer

ISRO 2023 · CSQ.56 · 1 mark · MCQ

Consider the Nondeterministic Finite-State Automaton (NFA) below. States with a small incoming arrow are initial states, while a double circle state denotes a final state. The number of states in the MINIMAL Deterministic Finite-State Automaton (DFA) for this language is:

ISRO CS 2023 question 56: An NFA with three states in a row, left to right. — Figure from the ISRO CS 2023 paper. It is part of the question.

(A)
2
(B)
4
(C)
6
(D)
8

Answer and solution

ANSWER

The minimal DFA has $4$ states, option (b).

Official answer: BSource: ISRO's revised and final answer key of 16 February 2024

Name the states $q_{0}$ (initial, loops on $a, b$ ), $q_{1}$ (reached from $q_{0}$ on $b$ ) and $q_{2}$ (final, reached from $q_{1}$ on $a$ or $b$ ).
The only way to accept is to finish in $q_{2}$ , and the move into $q_{2}$ consumes the last symbol of the string. The move before it must have been $q_{0} \to q_{1}$ on a $b$ . So the second-to-last symbol must be $b$ .
Hence $L = {w : ∣ w ∣ \geq 2 and the second-to-last symbol of w is b}$ , which is $(a + b)^{*} b (a + b)$ .
Subset construction. Start state ${q_{0}}$ : on $a$ it goes to ${q_{0}}$ , on $b$ to ${q_{0}, q_{1}}$ .
${q_{0}, q_{1}}$ : on $a$ to ${q_{0}, q_{2}}$ , on $b$ to ${q_{0}, q_{1}, q_{2}}$ . ${q_{0}, q_{2}}$ : on $a$ to ${q_{0}}$ , on $b$ to ${q_{0}, q_{1}}$ . ${q_{0}, q_{1}, q_{2}}$ : on $a$ to ${q_{0}, q_{2}}$ , on $b$ to ${q_{0}, q_{1}, q_{2}}$ . Exactly 4 subsets are reachable, and the final ones are ${q_{0}, q_{2}}$ and ${q_{0}, q_{1}, q_{2}}$ .
Read each subset as the last two symbols read: ${q_{0}}$ is $aa$ (also the start), ${q_{0}, q_{1}}$ is $ab$ , ${q_{0}, q_{2}}$ is $ba$ , ${q_{0}, q_{1}, q_{2}}$ is $bb$ . A string is accepted exactly when the last two symbols are $ba$ or $bb$ .
Distinguish the states. A final state differs from a non-final one by the empty string, so ${aa, ab}$ are separated from ${ba, bb}$ .
$aa$ and $ab$ : append $b$ . From $aa$ we reach $ab$ (reject), from $ab$ we reach $bb$ (accept). So $b$ separates them.
$ba$ and $bb$ : append $a$ . From $ba$ we reach $aa$ (reject), from $bb$ we reach $ba$ (accept). So $a$ separates them.
All 4 states are pairwise distinguishable, so the DFA is minimal. Equivalently, the Myhill-Nerode classes of $L$ are determined by the last two symbols, giving $2^{2} = 4$ classes. The minimal DFA has 4 states, option (b).

KEY IDEA

The NFA accepts strings whose second-to-last symbol is $b$ , so a DFA must remember the last two symbols, which gives $2^{2} = 4$ distinguishable states (Myhill-Nerode).

WATCH OUT FOR

Expecting the DFA to have $2^{3} = 8$ states because the NFA has 3 states, or stopping at the subset construction without noting that only 4 subsets are reachable. A worst-case bound is not the count of reachable, distinguishable states.

From the ISRO CS 2023 paper. Every question of this paper · The full paper (PDF, ISRO) · All 5 ISRO Finite automata questions, with notes

ISRO CS 2023 Q.56: solution and answer

Answer and solution

More ISRO Finite automata questions