Question 47

In both $D_1$ and $D_2$, only the start state is accepting, and every simple cycle from the start state back to itself has length $3$:

• In $D_1$, the simple 3-step paths from the start state back to itself are labeled $000, 001, 010,$ and $101$. Hence $L(D_1) = \{000, 001, 010, 101\}^*$.
• In $D_2$, the simple 3-step paths from the start state back to itself are labeled $011, 100, 110,$ and $111$. Hence $L(D_2) = \{011, 100, 110, 111\}^*$.

Notice that $S_1 = \{000, 001, 010, 101\}$ and $S_2 = \{011, 100, 110, 111\}$ form a partition of all $2^3 = 8$ binary strings of length $3$ ($S_1 \cap S_2 = \emptyset$ and $S_1 \cup S_2 = \{0, 1\}^3$):

• Any non-empty string in $L(D_1)$ is a concatenation of blocks from $S_1$, and any non-empty string in $L(D_2)$ is a concatenation of blocks from $S_2$. Since $S_1 \cap S_2 = \emptyset$, no non-empty string belongs to both, so $L(D_1) \cap L(D_2) = \{\epsilon\}$ (C is true, while A and B are false).
• Moreover, $(L(D_1) \cup L(D_2))^* = (S_1^* \cup S_2^*)^* = (S_1 \cup S_2)^* = (\{0,1\}^3)^*$, which is the set of all binary strings whose length is a multiple of 3 (D is true).