suffix regular language

Question

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)

Answer 1

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.

Answer 2

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

2. 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})$.

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