GATE 2024 CS2 Q.22: solution and answer

Official answer: ASource: Official answer key, GATE 2024 CS2 (IISc Bengaluru)

1. Read the DFA: the start state is $q_0$ (not accepting) and $q_1$ is the only accepting state. Both states have a self-loop on 0, and the symbol 1 moves $q_0\to q_1$ and $q_1\to q_0$. So 0 never changes the state and 1 toggles it. The language is the set of strings over $\{0,1\}$ with an odd number of 1s.

2. Derive the expression by state elimination. To go from $q_0$ to $q_1$ for the first time, read any number of 0s at $q_0$ and then a 1. This gives the prefix $0^{\ast }1$.

3. Every way of leaving $q_1$ and returning to $q_1$ is one of two kinds. Either read a 0 (the self-loop), or read a 1 to $q_0$, then $0^{\ast }$ at $q_0$, then a 1 back to $q_1$, which is $10^{\ast }1$. So the loop part is $(0+10^{\ast }1{)}^{\ast }$.

4. Therefore $L=0^{\ast }1(0+10^{\ast }1{)}^{\ast }$, which is option (A).

5. Check the other options with short strings. The string $1$ has one 1 and is accepted. (B) $0^{\ast }(10^{\ast }11{)}^{\ast }{0}^{\ast }$ cannot generate $1$, since every 1 in it comes in a block of three 1s or none. (D) $0(1+0^{\ast }10^{\ast }1{)}^{\ast }{0}^{\ast }$ must begin with 0, so it cannot generate $1$. (C) $0^{\ast }1(010^{\ast }1{)}^{\ast }{0}^{\ast }$ cannot generate $111$, which has three 1s and is accepted. After the first 1, every block must start with 0, and the trailing part is only 0s. Also test (A) on $1011$, which has three 1s and is accepted: $1\cdot 0\cdot (10^{\ast }1)$ with $10^{\ast }1=11$ gives $1011$, so (A) generates it.