Consider the following two finite automata \(D_1\) and \(D_2\).
Which of the following statements is/are true?
Show Hint
Since the start state is the only accepting state in both automata, a string is accepted only if it traces a closed walk back to the start; check the length of every such walk and compare the specific bit patterns each machine allows.
\((L(D_1) \cup L(D_2))^{*}\) consists of all strings in \(\{0,1\}^{*}\) whose length is divisible by 3
Show Solution
Verified By Collegedunia
The Correct Option isC, D
Solution and Explanation
Step 1: Understanding the Question.
Both \(D_1\) and \(D_2\) are finite automata over the alphabet \(\{0,1\}\) where, in each diagram, only the start state is marked as accepting, shown with a double circle. We must decide which of the four statements about \(L(D_1)\) and \(L(D_2)\) are true, by reasoning about which strings can bring each automaton back to its own start state.
Step 2: Use the fact that only the start state accepts.
In any automaton where the sole accepting state is also the start state, a string is accepted exactly when it labels a path that begins and ends at the start state, that is, a closed walk through the transition diagram back to the start. The empty string \(\epsilon\) always does this trivially, a walk of zero steps, so
\[ \epsilon \in L(D_1) \text{ and } \epsilon \in L(D_2) \]
Step 3: Check that every closed walk in each machine has a length that is a multiple of 3.
Tracing the transitions in \(D_1\) shows that every path leaving the start state and returning to it again passes through exactly three transitions, whether it goes around the small triangle of states or around the larger loop through the other states, there is no way to return to the start after 1, 2, 4, or 5 steps. The same holds for \(D_2\): tracing its transitions shows every return path to the start also takes exactly three transitions. So both languages only contain strings whose length is a multiple of 3:
\[ L(D_1) \subseteq \{w \in \{0,1\}^{*} : |w| \equiv 0 \pmod 3\},\quad L(D_2) \subseteq \{w \in \{0,1\}^{*} : |w| \equiv 0 \pmod 3\} \]
Step 4: Check option (A), \(L(D_1)=L(D_2)\).
\(D_1\) and \(D_2\) route different specific bit patterns back to their start states, because their transition labels on the loops are wired differently, the outgoing symbols at corresponding states do not match up state for state. So while both languages sit inside "length divisible by 3", the actual strings each one accepts are not the same set. \(L(D_1) \neq L(D_2)\), so (A) is false.
Step 5: Check option (B), \(L(D_1)\) is a proper subset of \(L(D_2)\).
For \(L(D_1)\) to be a proper subset of \(L(D_2)\), every string \(D_1\) accepts would have to also be accepted by \(D_2\), plus \(D_2\) would need to accept something extra. Because the two machines loop on different bit patterns, \(D_1\) accepts some length-3 (or longer) strings that do not drive \(D_2\) back to its start, so \(L(D_1)\) is not contained in \(L(D_2)\). (B) is false.
Step 6: Check option (C), \(L(D_1)\cap L(D_2)=\{\epsilon\}\).
We already know \(\epsilon\) is in both languages. For any non-empty string, it would have to trace a valid closed walk in \(D_1\) and, independently, a valid closed walk in \(D_2\), using the exact same sequence of 0s and 1s in both diagrams. Since the two automata are wired with different transition labels at corresponding points in their cycles, no non-empty string manages to close a loop in both machines at once. So the only string common to both languages is the empty string. (C) is true.
Step 7: Check option (D), \((L(D_1)\cup L(D_2))^{*}\) is all strings of length divisible by 3.
Concatenating strings from \(L(D_1)\) and \(L(D_2)\) is the same as gluing together valid return-to-start blocks, where each block individually has a length that is a multiple of 3. Between the two machines, enough different length-3 bit patterns are accepted, one machine covers some patterns and the other covers the rest, that any length-3 block of 0s and 1s can be matched to at least one of the two automata's accepted strings. Since Kleene star lets us pick any number of such blocks, one after another in any combination, we can build every string whose total length is a multiple of 3, and nothing else, because every piece we place still has to be a multiple of 3 long. So
\[ (L(D_1)\cup L(D_2))^{*} = \{w\in\{0,1\}^{*} : |w|\equiv 0 \pmod 3\} \]
(D) is true.
Step 8: Final conclusion.
The true statements are (C) and (D).
\[ \boxed{L(D_1)\cap L(D_2)=\{\epsilon\} \text{ and } (L(D_1)\cup L(D_2))^{*} \text{ is all strings of length divisible by 3}} \]
