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.
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 ?