Prove language is regular

Question

My question is this:

Given a language L, define L' to be the set of all words in L but with the first letter moved to the end of the word.

e.g. if L = {a, ab, abc, abcd, bab} then L' = {a, ba, bca, bcda, abb}

If L is regular, prove that L' is also regular.

I'm really struggling, since I see no easy way to construct a DFA/NFA or regular expression for L'.

Your help is appreciated, thanks!

Christian

Answer 1

Here's one approach. (It is essentially the same approach as @Max's, presented in a different way.) It is based on the notion of quotient of a language $L$ by a word $x$:

$$ x^{-1} L = \{ w \mid xw \in L\} .$$

If $L$ is regular, so is $x^{-1}L$, because it is the language accepted by a DFA $D$ for $L$ modified so that the initial state is the state reached by $D$ after reading $x$.

If $\epsilon \not\in L$, your $L'$ is simply

$$ \bigcup_{a \in \Sigma} a^{-1}L \cdot a \enspace. ~~~~~~~~~~~~~~~~~~~~~~~~~(1)$$

Hence, it is regular because regular languages are closed under concatenation and finite unions. If $\epsilon \in L$, then the definition of $L'$ should be clarified. Suppose it means that $\epsilon$ is also in $L'$. (There is no first letter, hence there's nothing to do to $\epsilon$.) Then it's enough to add $\{\epsilon\}$ to $(1)$. If $\epsilon$ is excluded from $L'$, then $(1)$ is the result.

Answer 2

Let $(Q, F, q_0, \delta)$ be DFA associated with $L$. For $q\in Q$ let $L_q$ denote the rational language consisting of those words $m$ such that $\delta^*(q,m)\in F$ (where $\delta^*$ is the expansion of $\delta$).

Then $L' =\displaystyle\bigcup_{q\in Q} \bigcup_{a\in \Sigma, \delta(q_0,a) = q} L_q \cdot a$ which makes $L'$ a finite union of rational languages, thus rational, and thus regular.