13
$\begingroup$

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.

$\endgroup$
7
  • 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$ Commented Apr 12, 2015 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
    Commented Apr 12, 2015 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
    Commented Apr 12, 2015 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
    Commented Apr 12, 2015 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
    Commented Apr 12, 2015 at 21:50

1 Answer 1

7
$\begingroup$

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(f(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)$.

$\endgroup$
3
  • 1
    $\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$ Commented Jul 5, 2018 at 9:53
  • $\begingroup$ There should be a $f$ in a definition of $\delta'$ somewhere. $\endgroup$
    – sas
    Commented Sep 27, 2023 at 9:57
  • $\begingroup$ @sas Thanks, corrected. $\endgroup$ Commented Oct 29, 2023 at 13:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.