Question

Prove that if a language L is regular, the suffix language of L is also regular.

Answer 1

1. It may be easier to see that prefix(L)={y:yx∈L for some x∈Σ∗}prefix⁡(L)={y:yx∈L for some x∈Σ∗} is regular whenever LL is regular, and easier to show it. One way to do it is to take the machine for LL 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 LL and add an ϵϵ-transition between states xx and yy whenever there is a non-ϵϵ-transition between those states.

2. If you do go that way, it's easy to show that reverse(L)reverse⁡(L) is regular if and only if LL is. Here reverse(L)={w:wR∈L}reverse⁡(L)={w:wR∈L}. Here the easy proof is to take a left-regular grammar for LL and turn it into a right-regular grammar for reverse(L)reverse⁡(L).

3. Then since suffix(L)=reverse(prefix(reverse(L)))suffix⁡(L)=reverse⁡(prefix⁡(reverse⁡(L))), you win.

You can ask doubt in comments