Why is $S(L)$ regular? Let $L$ be a regular language, and $\Sigma$ be its alphabet. Then, the language $S(L) = \{y \in \Sigma^*~|~xy \in L \text{ for some string }x \in \Sigma^*\}$ is also regular.
I am trying to demonstrate this by constructing a Non-deterministic Finite Automata for $S(L)$. The solution says to construct epsilon transitions from that start state of a DFA $D$ representing $L$ to the final states of $D$, but I don't understand how that works.
Could someone please clarify what that means? By the way, this is practice, not homework.
 A: I didn't really think too hard about your book soliton but it seems
that for $L=\emptyset$ your book gives that $\epsilon$ is accepted,
but $S(L)=\emptyset$.
I will attempt something similar:
Consider a finite deterministic automata that accepts $A$.
When is a word in $S(L)$ ? when there is some word $x$ that brings
us to a states (from $q_{0}$) and from there $w$ brings as a final
state
Where can the word $x$ bring us ? to any reachable state, and note
that for every reachable state there is an $x$ (by definition) that
can bring us to that state.
So lets build a new automata (non-deterministic with epsilon moves),
the automata is the same except we add epsilon moves from $q_{0}$
to any reachable state (formally there will be some difference because
we need to go to a set of states ). 
Can you see why this works ? 
A: This is an instance of a more general result. If $L$ is regular, then for any language $X$ (regular or not), the language
$$
  X^{-1}L = \bigl\{\ y \in A^* \mid \text{there exists $x \in X$ such that $xy \in L$}\ \bigr\}
$$
is regular. This can be proved as follows. First, for each word $x \in A^*$, the language $x^{-1}L$ is regular. Indeed, if $\mathcal{A} = (Q, A, \cdot, i, F)$ is a DFA accepting $L$, then the automaton $(Q, A, \cdot, i.x, F)$ (obtained from $\mathcal{A}$ by changing the initial state $i$ to $i\cdot x$) accepts $x^{-1}L$. It follows that there are only finitely many languages of the form $x^{-1}L$, a (famous) result known as Nerode's lemma.
Now observe that
$$
  X^{-1}L = \bigcup_{x \in X} x^{-1}L
$$
but according to Nerode's lemma, this apparently infinite union is a finite one. Therefore $X^{-1}L$ is a finite union of regular sets and hence is regular.
In your case, you take $X = A^*$.
