The GATE Grind

GATE 2026 CS (CS2) – Question 47

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

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

Diagram for GATE 2026 CS (CS2) question 47
  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\}$; (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.

More Regular Expressions and Finite Automata questions

All Regular Expressions and Finite Automata questions →