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
The Correct Option isC, D
Solution and Explanation
Step 1: Notice the shape both machines share.
In $D_1$ and in $D_2$, the double circle marks both the start state and the only accepting state. That means a string gets accepted only if it walks the automaton in a full loop, leaving the start and coming straight back to it.
Step 2: Think of acceptance as returning home.
Trace the arrows in $D_1$: any path that leaves the start state and eventually lands back on it again always takes exactly three arrows, never one, two, four, or five. The same check on $D_2$ gives the same fact, every trip back home takes exactly three arrows. So both machines only ever accept strings whose length is a multiple of $3$, and both accept the empty string $\epsilon$ for free, since standing still already counts as being at home.
Step 3: Test option (A) by asking if the two machines agree on every string.
The two diagrams send $0$s and $1$s along different arrows at corresponding points in their loops, so the actual three-letter (and longer) words that bring each machine home form different lists for $D_1$ and $D_2$. Two different lists mean $L(D_1)\neq L(D_2)$, so (A) fails.
Step 4: Test option (B) with a subset check.
A subset relationship would need every word accepted by $D_1$ to also be accepted by $D_2$. Since $D_1$ has words in its accepted list that are not on $D_2$'s list, because their loop patterns differ, this containment breaks down, so (B) fails too.
Step 5: Test option (C) by hunting for a shared non-empty word.
Suppose some non-empty string worked for both. It would have to close a loop in $D_1$ using its arrows and close a loop in $D_2$ using its arrows, with the very same sequence of bits both times. Because the arrow labels at matching points in the two loops do not line up, no such shared non-empty string exists. Only $\epsilon$ survives in both lists, so
\[ L(D_1)\cap L(D_2)=\{\epsilon\} \]
and (C) holds.
Step 6: Test option (D) by thinking of blocks stacked end to end.
Every accepted word from either machine is a block whose length is some multiple of $3$. Kleene star on $L(D_1)\cup L(D_2)$ means gluing any number of such blocks together in any order. Between the two machines' accepted words, every possible pattern of $0$s and $1$s of length $3$ shows up in at least one of the two lists, so any string whose total length is a multiple of $3$ can always be cut into three-letter chunks that each come from $D_1$ or $D_2$. Nothing of a length not divisible by $3$ can ever appear, since each block forces a multiple of $3$. So
\[ (L(D_1)\cup L(D_2))^{*}=\{w\in\{0,1\}^{*}:|w|\equiv0\pmod3\} \]
and (D) holds too.
Step 7: Conclude.
\[ \boxed{\text{(C) and (D) are true}} \]
