Regular Language Operation

Question

I need to show that the given regular language is closed under the following operation.

For example: AllSuffixes(L) = {v : uv in L for some u in (0+1)* }

I do not have any idea about this question. I only know that regular languages are closed under + , . and * operations.

Do you have any idea(a solution way or a clue)?

Answer 1

One approach is to start with a DFA that recognizes $L$ and has no inaccessible states. Now add empty transitions from the initial state to each other state and show that the resulting NFA does what you want.

You can also approach it via regular grammars. Start with a regular grammar for $L$. If $S$ is the initial symbol, add a production $S\to X$ for each accessible non-terminal symbol $X$ other than $S$. This is basically exactly the same idea. In both cases the idea is to let the machine/grammar start at any point that the original machine/grammar could have reached from the initial state/symbol.

Answer 2

Another approach is to first prove a slightly easier exercise, namely that the language
$$ \text{AllPrefixes}(L) = \{v \mid vu \in L \text{ for some $u \in \{0,1\}^*$} \} $$ is regular. If you succeed to do so, then you could use the fact that regular languages are closed under reversal. If $u = a_1 \dotsm a_n$ is a word, its reversal is the word $\tilde{u} = a_n \dotsm a_1$, and the reversal of a language $L$ is the language $\tilde{L} = \{\tilde{u} \mid u \in L \}$. The next step would be to verify that the language AllSuffixes(L) is the reversal of $\text{AllPrefixes}(\tilde{L})$.