I am interested in proving that $\sqrt{L}=\{w:ww\in L\}$ is regular if $L$ is regular but I don't seem to be getting anywhere. If possible I was hoping for a hint to get me going in the right direction. Thank you for your help.

My idea for demonstrating regularity of the square root language was to try to consider two machines running in tandem. One of them accepts the original language $L$ and the other runs the same machine backwards (I expect that this will be an NFA). I then wanted to accept words that met in the middle (i.e ${(q,q):q∈Q}$ where $Q$ are the states of the DFA accepting $L$ ). However, I do not think this will work.

  • 6
    $\begingroup$ The following has an answer on math.sx: If $L$ is regular, prove that $\sqrt{L}=\left\{ w : ww\in L\right\}$ is regular $\endgroup$
    – Pål GD
    Apr 12 '15 at 6:58
  • 2
    $\begingroup$ The two machine must run forward. It is only that the second one must start where the first will finish. Hence, the second must make a guess for its starting state, and remember that guess. $\endgroup$
    – babou
    Apr 12 '15 at 8:13
  • $\begingroup$ @PålGD Thank you for your response. That's an interesting solution but I can not seem to get the induction to work at the inductive step. What I get is the following: $$\hat{\delta'}(q_{0}',wa)=\delta'(\hat{\delta'}(q_{0}',w),a)=\delta'(f,a)=g$$ where $f(q)=\hat{\delta}(q,w)$ by the inductive hypothesis. So $$g(q)=f(\delta(q,b))=\hat{\delta}(\delta(q,b),w)=\hat{\delta}(q,bw)$$ If you could perhaps tell me where I went wrong I would be grateful. $\endgroup$
    – user99163
    Apr 12 '15 at 16:11
  • $\begingroup$ @babou Thank you for your response. Are you suggesting an NFA in which you can start at any point of the original DFA that accepted $L$? $\endgroup$
    – user99163
    Apr 12 '15 at 16:15
  • $\begingroup$ Yes. This is done with a non-deterministic $\epsilon$-transition at the beginning. The states are triples of the original machine state, one for the first simulation, one for the second simulation, and one to remember where the second simulation started, to make sure the first ends there. $\endgroup$
    – babou
    Apr 12 '15 at 21:50

Here is how to implement your solution. Let $A = \langle Q, q_0, F, \delta \rangle$ be a DFA for $L$. We will construct an NFA $A' = \langle Q', q'_0, F', \delta' \rangle$ as follows:

  • $Q' = \{q'_0\} \cup Q^3$. The state $(q_1,q_2,q_3)$ means that we have guessed that when $A$ finishes reading the first copy of $w$, it will be in state $q_1$; the first copy of $A$, started at $q_0$, is at state $q_2$; and the second copy of $A$, started at $q_1$, is at state $q_3$.
  • $F' = \{(q_1,q_1,q_2) : q_1 \in Q, q_2 \in F\}$. Thus we accept if the first copy of $A$ is in the guessed state, and the second copy of $A$ is at an accepting state.
  • $\delta'(q'_0,\epsilon) = \{(q,q_0,q) : q \in Q\}$. This initializes the simulation of the two copies of $A$.
  • $\delta'((q_1,q_2,q_3),a) = \{(q_1,\delta(q_2,a),\delta(q_3,a))\}$. This simulates both copies of $A$, while keeping the guessed state.

We leave the reader the formal proof that $L(A') = \sqrt{L(A)}$.

Here is another solution, which creates a DFA. We now run $|Q|$ copies of $A$ in parallel, starting at each state of $A$:

  • $Q' = Q^Q$.
  • $q'_0 = q \mapsto q$, the identity function.
  • $\delta'(f,a) = q \mapsto \delta(q,a)$.
  • $F' = \{ f \in Q' : f(f(q_0)) \in F \}$.

What is the meaning of the condition $f(f(q_0)) \in F$? After reading a word $w$, the automaton $A'$ is in a state $f$ given by $f(q) = \delta(q,w)$. Thus $f(f(q_0)) = \delta(\delta(q_0,w),w) = \delta(q_0,w^2)$.

  • $\begingroup$ There can be many types of such functions, like SQRT(L),HALF(L), etc. Is there some general way to combine all of them together? I was thinking on the lines of Myhill Nerode Theorem. This is what is also called half. sqrt is $\exists y$ s.t. $|y|=|x|^2$ and $xy\in L$ $\endgroup$ Jul 5 '18 at 9:53

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.