Construct a DFA based on this language

Question

Let $L \subseteq \Sigma^*$ be a language of any alphabet $\Sigma$. Let $move(L)$ describe the language which contains every string such that it takes the last letter in $x \in L$ and puts it to the front.

How can we construct a DFA $A$ for $move(L)$?

I started off by looking at what the DFA for L would be like:

• Say $s = s_0 s_1 s_2 ... s_n$ where $s_i \in \Sigma$ is a string this DFA accepts
• it will go by some path of states $q_0q_1...q_n$. I made the last state transition to the first in $A$ but something tells me this isn't right so I'm not sure how to move on.

Answer 1

Let $\ A=\big(Q,\Sigma, \delta, q_0, F\big)\ $ be a DFA which accepts $\ L\ $. Let \begin{align} Q'&=\big(\Sigma\times Q\big)\,\cup \big\{q_0'\big\}\\ F'&=\big\{(s,q)\in \Sigma\times Q\,\big|\,\delta(q,s)\in F\big\}\\ \delta'(q',s)&=\cases{(s,q_0)&if $\ q'=q_0'$\\ \big(\sigma,\delta(q,s)\big)&if $\ q'=(\sigma,q)\in\Sigma\times Q\ $.} \end{align} Then $\ S'=\big(Q',\Sigma, \delta', q_0', F'\big)\ $ is a DFA which accepts $\ move(L)\ $.

If $\ \xi\in\Sigma^*\ $, and $\ q_n\ $ is the state of $ A\ $ after it has processed the string $\ \xi\ $, then $\ \big(s_0,q_n\big)\ $ will be the state of $\ A' $ after it has processed the string $\ s_0\xi\ $, and $\ \big(s_0,q_n\big)\in F'\ $ if and only if $\ \delta(q_n,s_0)\in F\ $—that is, $\ A'\ $ accepts the string $\ s_0\xi\ $ if and only if $\ A\ $ accepts the string $\ \xi s_0\ $.

Reply to query from OP in comments

In general, the minimal-state DFA for the language $\ L\ $ will have strictly fewer states than the minimal-state DFA for $\ move(L)\ $, so if you're given a DFA for $\ L\ $ it will not always possible to construct a DFA for $\ move(L)\ $ which has the same set of states. If \begin{align} L=\ &\big\{a^{n_1}b^{n_2}c^{n_3}\,\big|\,n_1\ge0, n_2\ge0, n_3\ge1\,\big\}\\ \cup &\big\{a^{n_1}b^{n_2}d^{n_3}\,\big|\,n_1\ge0, n_2\ge0, n_3\ge1\,\big\}\\ \cup &\big\{a^{n_1}b^{n_2}e^{n_3}\,\big|\,n_1\ge0, n_2\ge0, n_3\ge1\,\big\}\ , \end{align} for instance, it is easy to construct a $5$-state DFA which accepts $\ L\ $. However, \begin{align} move(L)=\ &\big\{ca^{n_1}b^{n_2}c^{n_3}\,\big|\,n_1\ge0, n_2\ge0, n_3\ge0\,\big\}\\ \cup &\big\{da^{n_1}b^{n_2}d^{n_3}\,\big|\,n_1\ge0, n_2\ge0, n_3\ge0\,\big\}\\ \cup &\big\{ea^{n_1}b^{n_2}e^{n_3}\,\big|\,n_1\ge0, n_2\ge0, n_3\ge0\,\big\}\ , \end{align} and it is not difficult to show that any DFA which accepts $\ move(L)\ $ must have at least $7$ states (by using the Myhill-Nerode theorem, for instance).

What if $\ \epsilon\in L\ $?

Dromniscience's answer and LetmeKnow's comment below have alerted me to the fact that the above answer implicitly (and inadvertently on my part) makes an assumption which is not necessarily justified—namely that the move operation will eliminate the empty string $\ \epsilon\ $ if it happens to be in $\ L\ $. Because $\ q_0'\not\in F'\ $ in the above definition of $\ A'\ $ the empty string $\ \epsilon\ $ can't be in the language accepted by $\ A'\ $.

However, since the OP doesn't specify how the move operation will deal with the empty string, it doesn't seem justified to me to assume that $\ \epsilon\not\in move(L)\ $ whenever $\ \epsilon\in L\ $. If, instead, $\ \epsilon\in L\ \implies\epsilon\in move(L)\ $ then the definition of $\ A'\ $ would have to be modified as follows: \begin{align} Q'&=\big(\Sigma\times Q\big)\,\cup \big\{q_0'\big\}\\ F'&=\cases{\big\{(s,q)\in \Sigma\times Q\,\big|\,\delta(q,s)\in F\big\}&if $\ q_0\not\in F$\\ \big\{(s,q)\in \Sigma\times Q\,\big|\,\delta(q,s)\in F\big\}\cup\big\{q_0'\big\}&if $\ q_0\in F$}\\ \delta'(q',s)&=\cases{(s,q_0)&if $\ q'=q_0'$\\ \big(\sigma,\delta(q,s)\big)&if $\ q'=(\sigma,q)\in\Sigma\times Q\ $.} \end{align}

Answer 2

You don't have to actually move the last transition to the front. Instead, why don't you simply remember the first letter and check whether it will lead to a final state in the original DFA?

Please think it over before you continue reading. If we denote the original DFA as $L = \langle Q, \Sigma, \delta, q_0, F\rangle$, we can construct a new DFA for $move(L) = \langle Q', \Sigma, \delta', q_{init}, F'\rangle$, where \begin{align} Q' &= \{q_{init}\} \cup \Sigma \times Q \\ F' &= \{(a, q)\mid \delta(a, q)\in F\} \\ \delta'((a, q), b) &= (a, \delta(q,b)) \\ \delta'(q_{init}, b) &= (b, q_0) \\ \end{align} Since $\epsilon$ is never in $move(L)$, $F'$ suffices.