ISRO CS 2023 Q.55: solution and answer

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

1. Name the states: $q_0$ (initial), $q_1$ (final, double circle) and $q_2$ (bottom state).

2. Read the transitions from the diagram: $q_0\stackrel{a}{\to }{q}_1$, $q_0\stackrel{b}{\to }{q}_2$, $q_1\stackrel{b}{\to }{q}_1$, $q_1\stackrel{a}{\to }{q}_2$, and $q_2$ loops to itself on both $a$ and $b$.

3. $q_2$ is a dead (trap) state: once entered it is never left, and it is not final, so any string that reaches it is rejected.

4. From $q_0$ the only way to avoid the trap is to read $a$ first, so every accepted string starts with $a$ and is then in $q_1$. The start state is not final, so the empty string is rejected.

5. In $q_1$, reading $b$ keeps the automaton in $q_1$, while reading $a$ sends it to the trap. So after the first $a$ only $b$'s may follow, and the string is accepted exactly when it ends in $q_1$. The language is $$L=\{a{b}^n:n\ge 0\}=a{b}^{\ast }.$$

6. Check the other options. $a^{\ast }{b}^{\ast }$ would accept $\epsilon$ and $b$, but $q_0$ is not final and $b$ from $q_0$ goes to the trap. $(ab{)}^{\ast }$ would accept $abab$, but the second $a$ is read in $q_1$ and goes to the trap. $a^{\ast }b$ would accept $aab$, but $aa$ already reaches the trap. Only $a{b}^{\ast }$ matches.