The GATE Grind

GATE 2026 CS (CS2) – Question 47

Theory of Computation · Regular Expressions and Finite Automata · 2 marks · Multiple choice

Consider the following two finite automata $D_1$ and $D_2$. Which of the following statements is/are true?

  1. $L(D_1)=L(D_2)$
  2. $L(D_1)$ is a proper subset of $L(D_2)$
  3. $L(D_1) \cap L(D_2)=\{\epsilon\}$
  4. $(L(D_1) \cup L(D_2))^{*}$ consists of all strings in $\{0,1\}^{*}$ whose length is divisible by 3

Practise this question in The GATE Grind →

Show answer and explanation

Correct answer: (C) $L(D_1) \cap L(D_2)=\{\epsilon\}$

Explanation

According to the supplied solution, comparing the length-3 strings accepted by the two automata shows that their accepted word sets are disjoint except for the empty string. Hence $L(D_1) \cap L(D_2)=\{\epsilon\}$. Therefore, option (C) is correct. This answer is tentative because the source solution explicitly states that some edge labels in the figure were difficult to read and should be verified against the automata diagram.