How to prove the language of suffixes of a regular language is still regular?

Question

Prove that if $ L \subseteq \Sigma^\star$ is regular, $L'$ is also regular where

$$ L' = \{w\mid{uw \in L \mbox{ for some string }u \in \Sigma^\star}\}$$

I'm new learning formal language and haven't proved stuff like this. But I'm sharing my thoughts here to make sure I'm on the right track. The first idea came to my mind is using close properties. Since $u$$w$ $\in$ L and $u$ $\in$ $\Sigma^\star$ so we know L is also regular. $L'$ is the concatenation of two regular languages. The regular languages are closed under concatenation thus $L'$ is also regular.

Any feedback or suggestions?

Answer 1

Given a DFA for $L$, let $\mathcal{Q}$ be the set of states that are reachable from the start state. Construct an NFA-$\epsilon$ by adding a new start state $S$ and adding an $\epsilon$-transition from $S$ to each state in $\mathcal{Q}$. You can see the new NFA-$\epsilon$ recognizes $L'$.

Answer 2

Your conclusion that $L’$ is a concatenation of two regular languages is wrong.

$L’$ is basically the set of suffixes of all the strings in $L$. Try to prove it for the prefixes and use the “closed under reverse operation” property of regular languages.

Hint for prefix language: make some special states as final state in the DFA of a regular language.