Proving an operation is closed under regular languages

Question

Following operation is defined over languages where $n \in \mathbb{N} :$

$L \ominus n = \lbrace s \in \sum^* | \exists s^{'} \in \sum^* (length(s^{'})=n,ss^{'} \in L) \rbrace$

Meaning that $L \ominus n$ is obtained by removing the last $n$ symbols from the strings of the language $L$. Prove that regular languages are closed under $\ominus$ operation.

$Hint:$ First prove that if $L$ is regular, then $L \ominus 1$ is as well defining a DFA for $L \ominus 1$ from a DFA to $L$. Then use induction on $n$.

Although I've got the hint, I can't find the solution. Can you help me?

Answer 1

Consider that, if you have a DFA which accepts words in $L$, then it can be in one of finitely many states after it reads the first letter - so, to test if a word is in $L\ominus 1$, we just start the DFA at each of the states it could be in after one letter and if it accepts when started in any of these, the word is in $L\ominus 1$ - and, if you know how to express a language $L_1\cup L_2$ in terms of a DFA, given one for $L_1$ and one for $L_2$, this should be relatively easy.

Personally, though, I think a much easier route is to ignore the hint and prove the statement via structural induction; since regular languages are generated by the empty language and languages accepting a single string under unions, concatenations, and the Kleene star, we merely need to notice:

1. That $L\ominus 1$ is regular if $L$ is the empty language or a language accepting only a single string.
2. That if $A$ and $B$ are regular, as are $A\ominus 1$ and $B\ominus 1$, then so are $AB\ominus 1$, $(A\cup B)\ominus 1$ and $A^*\ominus 1$. (Each of which can be written out fairly explicitly in terms of the given languages)