GATE 2024 CS2 Q.41: solution and answer

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

1. From the start state 1, the $\epsilon$-moves lead to state 2 or state 4, so $L(M)$ is the union of the strings accepted from 2 and from 4.

2. Branch through 2: the states 2 and 3 form a loop on $0$ ($2\to 3\to 2$). The strings that bring $M$ back to state 2 are $(00{)}^{\ast }$. State 2 is accepting, so $(00{)}^{\ast }$ is accepted.

3. The strings that reach state 3 from 2 are $(00{)}^{\ast }0=0(00{)}^{\ast }$. From 3 the $\epsilon$-move goes to state 5, which is accepting. At 5 the loop $5\to 4\to 5$ reads $11$, so $M$ can read any $(11{)}^{\ast }$ and still be in 5. This branch adds $0(00{)}^{\ast }(11{)}^{\ast }$.

4. Branch through 4: reading $1$ takes 4 to 5, and then $(11{)}^{\ast }$ keeps $M$ in 5. This gives $1(11{)}^{\ast }$. State 4 is not accepting, so a string that ends in 4 is rejected; in particular this branch does not accept $\epsilon$.

5. Combine: $L=(00{)}^{\ast }+0(00{)}^{\ast }(11{)}^{\ast }+1(11{)}^{\ast }=(00{)}^{\ast }+(1+0(00{)}^{\ast })(11{)}^{\ast }$.

6. Rewrite using $0^{\ast }=(00{)}^{\ast }+0(00{)}^{\ast }$. Taking zero repetitions of $11$ gives $0(00{)}^{\ast }\subseteq 0(00{)}^{\ast }(11{)}^{\ast }$, which is already in $L$. So adding $0(00{)}^{\ast }$ to $L$ changes nothing, and $L=0^{\ast }+(1+0(00{)}^{\ast })(11{)}^{\ast }$. This is option B.

7. Check the other options with test strings. A rejects $011$, but $M$ accepts it ($1\to 2\to 3\to 5$ on $0$, then $11$ goes $5\to 4\to 5$). C accepts $11$ (take $(00{)}^{\ast }$ as $\epsilon$, then $11$), but $M$ does not accept it ($1\to 4\to 5\to 4$ ends in the non-accepting state 4). D rejects $\epsilon$, but $M$ accepts $\epsilon$ because $1\to 2$ on an $\epsilon$-move.