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

Step 1: Start in the accepting initial state of each depicted automaton. Consequently both accept the zero-length string \(\epsilon\).
Step 2: Trace each possible three-symbol input. The three-bit strings that return automaton \(D_1\) to its accepting initial state form a set \(B_1\); the return strings for \(D_2\) form \(B_2\). Inspection of the labelled edges shows that every binary three-bit string is in exactly one set.
Step 3: Returning to the initial state allows the same transition analysis to start again. Thus a nonempty string accepted by \(D_i\) decomposes into three-bit blocks entirely from \(B_i\), so \(L(D_i)=B_i^*\).
Step 4: Since \(B_1\cap B_2=\varnothing\), a nonempty accepted word cannot have a first block accepted by both automata. Hence the languages intersect only in \(\epsilon\): \(L(D_1)\cap L(D_2)=\{\epsilon\}\).
Step 5: The star outside the union allows blocks chosen independently from either machine. Because \(B_1\cup B_2=\{0,1\}^3\), its language is \((\{0,1\}^3)^*\), exactly the binary words of lengths \(0,3,6,\ldots\). Therefore (C) and (D) are correct; (A) and (B) are not.
Final answer: \(\boxed{\text{(C), (D)}}\).