Prove that the shift operation on regular languages preserves regularity

Question

I have the following question: I have seen the statement that for the Shift operation, defined as: Shift($L$) = { $yx$ | $xy \in L$}

Where the following is mentioned: "For any regular language $L$, Shift($L$) is regular as well."

---

Shift defined as: Shift($L$) = { $yx$ | $xy \in L$}

I tried approaching this by forming a proof from the fact that a Shifted language is pulling from the same set of words / symbols as it's non shifted counterpart, but couldn't reach anything conclusive.

How would one prove that the shift operation preserves regularity?

Answer 1

Here's a sketch proof, using pictures. Let's say we start with some kind of automaton which accepts the language:

I will sketch how to construct a larger non-deterministic finite-state automaton, with $\varepsilon$ transitions (i.e. transitions between states that do not add to the word in progress), that accepts $\operatorname{Shift}(L)$.

Now, create a copy of this FSA for each state, and add a new initial state. Create $\varepsilon$ transitions from this initial state to each copy, each entering at a different state:

Let's focus one such copy, e.g.

We need a little modification here. Create a new copy of this original automaton, and add $\varepsilon$ transitions from the terminal state(s) to the initial state of the new copy. Change the terminal state(s) to not be terminal. Whichever state you arrived in, make it terminal in the copy. So, in this case:

The given non-deterministic FSA should accept $\operatorname{Shift}(L)$.

Answer 2

Note. The term Shift is not really appropriate and conjugate would possibly be better.

Let ${\cal A} = (Q, A, \cdot, i, F)$ be the minimal automaton of $L$. For each state $p, q \in Q$, let $L_{p, q}$ be the language accepted by $\cal A$ with $p$ as initial state and $q$ as the unique final state. I claim that \begin{equation} \text{Shift}(L) = \bigcup_{q \in Q, f \in F}L_{q,f} L_{i,q} \quad (*) \end{equation} Let $R$ be the right hand side of $(*)$. Let $w \in \text{Shift}(L)$. Then $w = vu$ for some words $u$ and $v$ such that $uv \in L$. Let $q = i \cdot u$ and $f = q\cdot v$. Then $i \cdot uv = q \cdot v = f$, and since $uv \in L$, one has $f \in F$. Now since $v \in L_{q,f}$ and $u \in L_{i,q}$, one gets $vu \in R$, which shows that $\text{Shift}(L) \subseteq R$.

Let now $w \in R$. By definition, there exists $q \in Q$ and $f \in F$ such that $w \in L_{q,f} L_{i,q}$, that is, $w = vu$ with $v \in L_{q,f}$ and $u \in L_{i,q}$. It follows that $i \cdot uv = q \cdot v$ and hence $uv \in L$. Thus $R \subseteq \text{Shift}(L)$, which proves (*). It follows immediately that $L$ is regular.