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: Both automata have an accepting start state, so the empty string \(\epsilon\) belongs to both languages.
Step 2: Read the labelled transitions in the diagram. Let \(B_1\) and \(B_2\) be the sets of three-bit strings that take the respective automaton from its accepting start state back to that state.
Step 3: The two three-bit return-block sets are disjoint and exhaustive: \(B_1\cap B_2=\varnothing\) and \(B_1\cup B_2=\{0,1\}^3\). Longer accepted strings are concatenations of such blocks, hence \(L(D_1)=B_1^*\) and \(L(D_2)=B_2^*\).
Step 4: A nonempty accepted string has a first three-bit block. Because no block belongs to both \(B_1\) and \(B_2\), no nonempty string can belong to both languages. Therefore \(L(D_1)\cap L(D_2)=\{\epsilon\}\), so option (C) is true.
Step 5: Taking the Kleene closure of the union permits any concatenation of blocks from either automaton. Thus \((L(D_1)\cup L(D_2))^*=(B_1\cup B_2)^*=(\{0,1\}^3)^*\), precisely all binary strings whose lengths are divisible by three. Option (D) is true; neither containment statement (A) or (B) holds.
Final answer: \(\boxed{\text{(C) and (D)}}\).