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.


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.

  • $\begingroup$ 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$. $\endgroup$ – userhello1298 Oct 30 '20 at 20:19
  • $\begingroup$ This is a Cartesian product. You can look it up on Wikipedia. $\endgroup$ – Yuval Filmus Oct 30 '20 at 20:24
  • $\begingroup$ No, I understand that. But how is $(q, \sigma)$ a \emph{state} for any $q \in Q$, $\sigma \in \Sigma$? $\endgroup$ – userhello1298 Oct 31 '20 at 1:12
  • $\begingroup$ It is a state of the new automaton by definition. $\endgroup$ – 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 !!!)


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.