# Regular language is closed given transposition of rightmost character to leftmost

It would appear straightforward to show that a regular language is closed given the transposition of the rightmost character to the front. However after drawing a few sample DFA for the phenomenon, I've been unable to come up with a generalized 'concept' or 'proof' that shows it's true for all regular languages. Could anyone help me out? It's on occasions like these that I see the value of formal definitions for DFA (instead of just drawings), however it's been a while since I've studied those.

## 2 Answers

This answer assumes that the transposed language never contains the empty string.

Let $$L$$ be a regular language, say accepted by a DFA with states $$Q$$, initial state $$q_0$$, accepting states $$F$$, and transition function $$\delta$$.

We construct a new DFA with states $$Q' = q'_0 \cup (Q \times \Sigma)$$. The initial state of the new DFA is $$q'_0$$. The transition function is defined as follows: $$\delta'(q'_0,\sigma) = (q_0,\sigma)$$, and $$\delta'((q,\sigma),\tau) = (\delta(q,\tau),\sigma)$$. Finally, the set of accepting states $$F'$$ contains all states $$(q,\sigma)$$ such that $$\delta(q,\sigma) \in F$$.

The new DFA reads the first symbol $$\sigma$$ and remembers it. It then simulates the original DFA, accepting a word if adding $$\sigma$$ would result in the original DFA accepting it.

• Hi Yuval, sorry I'm only just getting back to you. I don't understand what new states you are denoting by $Q \times \Sigma$. – userhello1298 Oct 30 '20 at 20:19
• This is a Cartesian product. You can look it up on Wikipedia. – Yuval Filmus Oct 30 '20 at 20:24
• No, I understand that. But how is $(q, \sigma)$ a \emph{state} for any $q \in Q$, $\sigma \in \Sigma$? – userhello1298 Oct 31 '20 at 1:12
• It is a state of the new automaton by definition. – Yuval Filmus Oct 31 '20 at 5:32

Lets try solving this question ,

The basic idea is that we need to remember the first symbol we read $$\alpha$$ , then we begin our computation from the start state and the second symbol , once we finish we arrive at a state q , if there is a transition from q to an accept state on $$\alpha$$ we accept

So , we have a DFA M that accepts a language L , we want to construct M' to accept the transposed language L'

In M' we begin in a new start state $$q_0'$$

Now for each $$\alpha \in \Sigma$$ we make a copy of M , name it $$M_\alpha$$ , so when we are in $$q_0'$$ and we read a symbol $$\alpha$$ we go to the start state of $$M_\alpha$$

Formally , $$\delta(q_0',\alpha) = q_{0_{\alpha}}$$

Now how is each $$M_\alpha$$ different from the original M ?

$$M_\alpha$$ is the same as M , all we have to change is the set of accept states , the new accept states are the states who have a transition on $$\alpha$$ to accept state ,

So let $$F_\alpha$$ be the set of accept states for $$M_\alpha$$ , if in M a rule exist $$\delta(q,\alpha) = q_{accept}$$ , then $$q_\alpha \in F_\alpha$$ (here q in M corresponds to $$q_\alpha$$ in $$M_\alpha$$ )

The other answer provided earlier is the same idea expressed more formally (sorry to provide another answer when it is the same idea , could not fit all this into a comment !!!)