Show that the language is regular modifying the DFA

Question

Let L be a regular language. How can I show that the language $\text{Suffix}(L)=\{w \in \Sigma^* \mid \text{ there is a $x \in \Sigma^*$ so that }xw \in L\}$ is also regular? How can I modify the DFA of $L$ so that it accepts $\text{Suffix}(L)$.

Answer 1

The "easy" way to do this is to use the equivalence of NFAs and DFAs. Let the DFA that accepts $L$ be $M$. First, make an NFA $M_s$ whose start state has $\varepsilon$-transitions to every state of $M$ that is accessible from $M$'s start state. (And otherwise $M_s$ has the same states as $M$.) It is not hard to check that $M_s$ accepts Suffix$(L)$. Then one can convert the NFA $M_s$ into a DFA accepting the same language in a canonical way by using the powerset construction.

I'm not sure that there is a simpler direct construction.