1
$\begingroup$

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.
$\endgroup$
4
  • $\begingroup$ Welcome to MSE. Please read this text about how to ask a good question. $\endgroup$ Oct 31 '20 at 7:33
  • $\begingroup$ Is $L$ a regular language? Because if its not, no DFA can accept it... $\endgroup$
    – Eminem
    Oct 31 '20 at 7:33
  • $\begingroup$ Yes, It is regular. $\endgroup$ Oct 31 '20 at 7:36
  • $\begingroup$ @JoséCarlosSantos Sorry, I added my thought process to the question. $\endgroup$ Oct 31 '20 at 7:39
0
$\begingroup$

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}

$\endgroup$
5
  • $\begingroup$ what does it mean for the transition function to map to a pair? $\endgroup$ Nov 2 '20 at 2:11
  • $\begingroup$ The states of a DFA can be any finite set. In this case, all the states of $\ S'\ $ except the starting state are members of $\ \Sigma\times Q\ $—i.e. pairs comprising one member of $\ \Sigma\ $ and one member of $\ Q\ $. The only pairs which the transition function $\ \delta'\ $ maps to are all of this form—i.e. they are states of the DFA $\ S'\ $. $\endgroup$ Nov 2 '20 at 3:02
  • $\begingroup$ I've spent a while trying to translate this DFA into a DFA where the states are only members of $Q$, but I'm not getting anywhere with it. Could you help me out? $\endgroup$ Nov 2 '20 at 3:13
  • $\begingroup$ Hey, I have a question, is $s \in \Sigma$ or in $\Sigma^*$ and would this handle the empty string $\epsilon$ if $L$ accepted it? $\endgroup$
    – LetmeKnow
    Nov 2 '20 at 6:28
  • $\begingroup$ @LetmeKnow I have now modified my answer in response to your question. $\endgroup$ Nov 2 '20 at 22:35
0
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ what does it mean for the transition function to map to a pair? $\endgroup$ Nov 2 '20 at 2:11
  • $\begingroup$ This pair is a component of $Q'$. Recall that $\delta$ is always a mapping from $Q\times \Sigma$ to $Q$. $\endgroup$ Nov 2 '20 at 3:53
  • $\begingroup$ is b a member of $\Sigma^*$? or of $\Sigma$? $\endgroup$
    – LetmeKnow
    Nov 2 '20 at 15:59

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.