Let $M = (Q, Σ, δ, q_0, F)$ be a DFA. Let $M_1 = (Q, Σ, δ, q_0, F_1)$ be an AFD identical to $M$ except for the set of final states, where $F_1$ is defined as the set of states $q ∈ Q$ for which $\hat{δ} (q, z) ∈ F$ for some $z$. What is the relationship between the language accepted by $M_1$ and the language accepted by $M$? Justify your answer.
(Hint: Use the fact that $\hat{δ} (q, xy) = \hat{δ} (\hat{δ}(q, x), y))$
Hi I'm answering this question, and by drawing some DFA, I think the realtionship between the language accepted by $M_1$ and the language accepted by $M$, is that the language acceptes by $M_1$ contains all the prefix from all the strings in $M$.
But I can't seem a way to justify using the hint.
Can someone help?
You are correct.
Consider some arbitrary $s$, and let $q = \hat{\delta}(Q, s)$.
We see that $s \in L(M_1)$ iff $q \in F_1$ iff $\exists z (\hat{\delta}(q, z) \in F)$. Now, let's note that for every $z$, we have $\hat{\delta}(q, z) = \hat{\delta}(\hat{\delta}(Q, s), z) = \hat{\delta}(Q, sz)$, using the hint.
Then we have $\exists z (\hat{\delta}(q, z) \in F)$ iff $\exists z (\hat{\delta}(Q, sz) \in F)$ iff $\exists z (sz \in L(M))$.
Then $s \in L(M_1)$ iff there exists $z$ such that $sz \in L(M)$.
Then $L(M_1)$ is indeed the set of all prefixes of elements of $L(M)$.