GATE CS 2026 Set 2 Q37 — Regular Expressions and Finite Automata

Based on the transition diagrams for $D_1$ and $D_2$:

• $D_1$ accepts the empty string $\epsilon$ and all binary strings of length divisible by $3$ that start with the symbol $0$. That is, $L(D_1) = \{\epsilon\} \cup \{0w \mid w \in \{0,1\}^* \text{ and } |0w| \equiv 0 \pmod 3\}$.
• $D_2$ accepts the empty string $\epsilon$ and all binary strings of length divisible by $3$ that start with the symbol $1$. That is, $L(D_2) = \{\epsilon\} \cup \{1w \mid w \in \{0,1\}^* \text{ and } |1w| \equiv 0 \pmod 3\}$.

Let's evaluate the given options:

• Option A & B: Since $000 \in L(D_1)$ but $000 \notin L(D_2)$, and $111 \in L(D_2)$ but $111 \notin L(D_1)$, the languages are not equal, nor is one a proper subset of the other. Thus, A and B are false.
• Option C: Any non-empty string in $L(D_1)$ starts with $0$, while any non-empty string in $L(D_2)$ starts with $1$. The only common string between them is the empty string $\epsilon$. Thus, $L(D_1) \cap L(D_2) = \{\epsilon\}$, which is true.
• Option D: The union $L(D_1) \cup L(D_2)$ contains $\epsilon$ and all strings of length $3k$ ($k \ge 1$) starting with either $0$ or $1$. This is exactly the set of all binary strings whose length is a multiple of $3$. Applying the Kleene star, $(L(D_1) \cup L(D_2))^*$ also consists of all strings in $\{0,1\}^*$ whose length is divisible by $3$. Thus, D is true.