GATE 2026 CS2 Q.47: solution and answer

Official answer: C, DSource: Official answer key, GATE 2026 CS2 (IIT Guwahati)

1. In each automaton the start state is the only accepting state, and every walk that leaves it returns to it after exactly 3 transitions (the other states have no edges among themselves except along these 3-step loops). So $L(D_i)=S_i^{\ast }$, where $S_i$ is the set of labels of the length-3 loops through the start state.

2. $D_1$ loops: $q_0\stackrel{0}{\to }b\stackrel{0}{\to }a\stackrel{0}{\to }{q}_0$ gives $000$; the same path ending with the edge $a\stackrel{1}{\to }{q}_0$ gives $001$; $q_0\stackrel{0}{\to }b\stackrel{1}{\to }c\stackrel{0}{\to }{q}_0$ gives $010$; $q_0\stackrel{1}{\to }d\stackrel{0}{\to }e\stackrel{1}{\to }{q}_0$ gives $101$. So $S_1=\{000,001,010,101\}$.

3. $D_2$ loops: $p_0\stackrel{0}{\to }f\stackrel{1}{\to }g\stackrel{1}{\to }{p}_0$ gives $011$; $p_0\stackrel{1}{\to }h\stackrel{1}{\to }g\stackrel{1}{\to }{p}_0$ gives $111$; $p_0\stackrel{1}{\to }h\stackrel{0}{\to }i\stackrel{0}{\to }{p}_0$ gives $100$; $p_0\stackrel{1}{\to }h\stackrel{1}{\to }i\stackrel{0}{\to }{p}_0$ gives $110$. So $S_2=\{011,111,100,110\}$.

4. $S_1\cap S_2=\varnothing$ and $|S_1|+|S_2|=8$, so $S_1\cup S_2=\{0,1{\}}^3$.

5. (A) and (B) are false: $000\in L(D_1)$ but $000\notin L(D_2)$, and $011\in L(D_2)$ but $011\notin L(D_1)$. The languages are incomparable, so neither equality nor proper inclusion holds.

6. (C) is true: a nonempty string in both languages has length $3k$ with $k\ge 1$. Its first 3 symbols form a loop label, so they lie in $S_1$ and also in $S_2$, which is impossible because $S_1\cap S_2=\varnothing$. Only $\epsilon$ is common to both.

7. (D) is true: $(L(D_1)\cup L(D_2){)}^{\ast }=(S_1^{\ast }\cup S_2^{\ast }{)}^{\ast }=(S_1\cup S_2{)}^{\ast }=(\{0,1{\}}^3{)}^{\ast }$, which is exactly the set of strings over $\{0,1\}$ whose length is divisible by 3.