suffix regular language Can someone give me an idea how to prove this:
suffix(L) = {y | xy $\in $ L for some x $\in$ $\Sigma$ *}. Or suffix is the set of all suffixes of its strings. Prove that if L is regular, then so is suffix(L)
 A: A simple way of doing it is to take a DFA without states that aren't reachable for $L$, and create an NFA for $\mathrm{tail}(L)$ by adding a new start state with $\epsilon$-transitions to all existing states. The NFA is essentially "jumping on board" at any point of a possible computation of the DFA, accepting just tails.
A: *

*It may be easier to see that $\operatorname{prefix}({\mathcal L}) = \{y : yx \in  {\mathcal L} \text{ for some }x \in \Sigma^\ast\}$ is regular whenever $\mathcal L$ is regular, and easier to show it. One way to do it is to take the machine for $\mathcal L$ and mark any state as an accepting state if there is any possible transition to an accepting state.  Another way is to take the machine for $\mathcal L$ and add an $\epsilon$-transition between states $x$ and $y$ whenever there is a non-$\epsilon$-transition between those states. 

*If you do go that way, it's easy to show that $\operatorname{reverse}({\mathcal L})$ is regular if and only if ${\mathcal L}$ is.  Here $\operatorname{reverse}({\mathcal L}) = \{ w : w^R\in \mathcal L\}$.  Here the easy proof is to take a left-regular grammar for $\mathcal L$ and turn it into a right-regular grammar for $\operatorname{reverse}({\mathcal L})$.

*Then since $\operatorname{suffix}({\mathcal L}) = \operatorname{reverse}(\operatorname{prefix}(\operatorname{reverse}({\mathcal L})))$, you win.
