ISRO CS 2025 Q.79: solution and answer

Official answer: BSource: ISRO's final answer key of 15 May 2026

1. Name the states: $P$ (initial, non-final), $Q$ (final) and $R$ (final). The transitions are $P\stackrel{a}{\to }Q$, $P\stackrel{b}{\to }R$, $Q\stackrel{b}{\to }Q$, $Q\stackrel{a}{\to }R$, and $R\stackrel{a,b}{\to }R$.

2. Minimisation starts by separating final from non-final states. This gives the groups $\{P\}$ and $\{Q,R\}$.

3. Check whether $Q$ and $R$ can be told apart. Two states are distinguishable only if some string takes one of them to a final state and the other to a non-final state.

4. From $R$, every string leads back to $R$, which is final. So $R$ accepts every string, including $\epsilon$.

5. From $Q$, input $b$ stays in $Q$ and input $a$ goes to $R$. Both are final, so every string from $Q$ ends in a final state. $Q$ also accepts every string.

6. So $Q$ and $R$ are equivalent and merge into one final state with a loop on $a,b$.

7. $P$ is non-final and the merged state is final, so $\epsilon$ distinguishes them. $P$ stays separate.

8. The language is ${\Sigma }^{+}$, the set of non-empty strings over $\{a,b\}$. The minimal DFA has 2 states: a non-final start state and a final state looping on $a,b$.