Given some regular language $L$, I need to prove that the language of all the substrings of words in $L$ is also regular:
$$ Substring(L)=\{y\in \Sigma^* \mid \exists x, z \in \Sigma^* \text{ such that } xyz \in L \} $$
I need to construct a finite automaton $A$ such that $L(A)=Substring(L)$.
I know that there exists a finite automaton $A_L$ such that $L(A_L)=L$ (since $L$ is regular), but I don't know how to use its components in order to construct $A$.
HINT: Start with a DFA $M$ for $L$; we’ll modify $M$ to get an NFA $M'$ for $\operatorname{Substring}(L)$. The first step is to find all of the states of $M$ from which an acceptor state can be reached and and make them the acceptor states of $M'$. The second and final step is to add $\epsilon$-transitions from the initial state of $M$ to every other state of $M$. I’ll leave the formal details to you, along with the task of explaining why $M'$ does in fact recognize $\operatorname{Substring}(L)$.