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?


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)

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.