1
$\begingroup$

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

$\endgroup$

2 Answers 2

1
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ What do you mean by the "expansion" of delta? $\endgroup$
    – user417638
    Feb 18, 2017 at 16:42
  • $\begingroup$ Well the function defined by $\delta^*(q,x\cdot m) = \delta^*(\delta(q,x), m)$ where $x\in \Sigma$, and $\delta^*(q,\epsilon) = q$ $\endgroup$ Feb 18, 2017 at 18:01
0
$\begingroup$

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.

$\endgroup$

You must log in to answer this question.