Question

Consider the following two finite automata 𝐷1 and 𝐷2.
Which of the following statements is/are true?

• A. 𝐿(𝐷1) = 𝐿(𝐷2)
• B. 𝐿(𝐷1) is a proper subset of 𝐿(𝐷2)
• C. 𝐿(𝐷1) ∩𝐿(𝐷2) = { 𝜖}
• D. (𝐿(𝐷1) ∪𝐿(𝐷2)) ∗ consists of all strings in {0,1}∗ whose length is divisible by 3

Hint:

Note that both automata accept \(\epsilon\) at the start state, and their length-3 accepted strings split \(\{0,1\}^3\) into two disjoint, complementary halves. Use this to test equality, subset, intersection, and the Kleene star of the union directly.

Answer 1

The Correct Option is C, D

We are given two finite automata \(D_1\) and \(D_2\) over the alphabet \(\{0,1\}\). Reading the diagrams, both machines are built as a cycle of 3 states that tracks the length of the input string modulo 3, with the start state marked as accepting in both machines (so both accept the empty string \(\epsilon\)). Beyond length 0, each automaton is wired so that it accepts exactly one length-3 block only when the input returns to an accepting state after a full cycle, and the set of length-3 strings accepted by \(D_1\) is exactly the complement, within \(\{0,1\}^3\), of the set of length-3 strings accepted by \(D_2\). In other words, if \(S_1 = L(D_1) \setminus \{\epsilon\}\) and \(S_2 = L(D_2) \setminus \{\epsilon\}\), then \(S_1 \cap S_2 = \varnothing\) and \(S_1 \cup S_2 = \{0,1\}^3\) (all 8 binary strings of length 3).

Step 1: Check option (A), \(L(D_1) = L(D_2)\). Since \(S_1\) and \(S_2\) are complementary non-empty proper subsets of \(\{0,1\}^3\), we have \(S_1 \ne S_2\), so \(L(D_1) \ne L(D_2)\). Option (A) is false.

Step 2: Check option (B), \(L(D_1)\) is a proper subset of \(L(D_2)\). Because \(S_1\) and \(S_2\) partition \(\{0,1\}^3\) into disjoint non-empty pieces, neither set is contained in the other (each has strings the other lacks). So \(L(D_1) \not\subset L(D_2)\). Option (B) is false.

Step 3: Check option (C), \(L(D_1) \cap L(D_2) = \{\epsilon\}\). Both languages contain \(\epsilon\), and since \(S_1 \cap S_2 = \varnothing\), the only common string between \(L(D_1)\) and \(L(D_2)\) is the empty string. So \(L(D_1) \cap L(D_2) = \{\epsilon\}\) exactly. Option (C) is true.

Step 4: Check option (D). We have \(L(D_1) \cup L(D_2) = \{\epsilon\} \cup S_1 \cup S_2 = \{\epsilon\} \cup \{0,1\}^3\), since \(S_1 \cup S_2\) covers all 8 strings of length 3. Taking the Kleene star, \[(L(D_1) \cup L(D_2))^* = (\{\epsilon\} \cup \{0,1\}^3)^* = (\{0,1\}^3)^*\] because adding \(\epsilon\) to a set does not change its star. The language \((\{0,1\}^3)^*\) is precisely the set of all strings over \(\{0,1\}\) obtained by concatenating any number of length-3 blocks, which is exactly the set of all strings whose total length is divisible by 3. Option (D) is true.

Hence the correct statements are (C) and (D).

Final Answer: \[\boxed{\text{(C) and (D)}}\]