GATE 2023 CS Q.14: solution and answer

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

1. Read the transitions from the figure: $\delta (s,1)=p$, $\delta (s,0)=r$, $\delta (p,0)=p$, $\delta (p,1)=q$, $\delta (q,1)=p$, $\delta (q,0)=r$, $\delta (r,0)=\delta (r,1)=r$. The start state is $s$ and the only final state is $p$.

2. State $r$ is a trap (dead) state: once the machine enters it, it never leaves, so no accepted string passes through $r$. From $s$, the symbol $0$ leads to $r$, so every accepted string must begin with $1$ and move to $p$.

3. Every accepted string ends in $p$. Looking at the loops through $p$ that avoid $r$: reading $0$ from $p$ returns to $p$. Reading $1$ from $p$ goes to $q$. From $q$, reading $0$ goes to $r$, so the only usable move is $1$, back to $p$. The ways to go from $p$ back to $p$ are therefore the blocks $0$ and $11$.

4. The language is the first symbol $1$ followed by any sequence of blocks $0$ or $11$: $$L(\mathcal{A})=1(0+11{)}^{\ast }.$$

5. Check the options on short strings. (B) begins with $0$, which the DFA sends to $r$ and rejects, so (B) is wrong. (A) $1(0^{\ast }11{)}^{\ast }$ does not generate $10$: after the leading $1$ the remaining $0$ is not of the form $0^{\ast }11$. The DFA accepts $10$ ($s\to p\to p$), so (A) is wrong. (D) $1(110^{\ast }{)}^{\ast }$ also does not generate $10$, so (D) is wrong. (C) generates $1$, $10$, $111$, $1011$, $1110$, and the DFA accepts each of these. It also rejects $11$, $101$ and $1101$ (they end in $q$), and (C) cannot generate them either. So (C) is correct.