GATE 2026 CS (CS2) – Question 47
Consider the following two finite automata $D_1$ and $D_2$. Which of the following statements is/are true?

Practise this question in The GATE Grind →
Show answer and explanation
Correct answer: (C) $L(D_1) \cap L(D_2)=\{\epsilon\}$; (D) $(L(D_1) \cup L(D_2))^{*}$ consists of all strings in $\{0,1\}^{*}$ whose length is divisible by 3
Explanation
Trace each three-symbol path from the start/accepting state back to itself. For $D_1$ the possible blocks are $000,001,010,101$; for $D_2$ they are $011,100,110,111$. Repetition of these paths gives arbitrary concatenations of their respective blocks, including the empty string.
The two block sets are disjoint, so a nonempty word cannot belong to both languages when split into consecutive length-3 blocks. Their intersection is exactly $\{\epsilon\}$: C is true. Neither language contains the other, so A and B are false.
Together the two block sets contain all eight binary words of length 3. Consequently the Kleene star of their union contains exactly every binary string whose length is divisible by 3: D is true.
Select **C and D**, the official multiple-select answer.