If $L$ is regular, prove that $\sqrt{L}=\left\{ w : ww\in L\right\}$ is regular

Question

Let $L$ be a regular language. Prove that $\sqrt{L}:=\left\{ w : ww\in L\right\}$ is also a regular language.

I suppose I need to modify state machine for $L$ to accept $\sqrt{L}$, but I've been thinking how to do that for a few hours and still don't know. I would be very grateful for help.

Answer 1

Let $\mathcal{A} = (Q, \Sigma, \delta, q_0, F)$ be a DFA that recognizes $L$. Define $\mathcal{A'} = (Q', \Sigma, \delta', q_0', F')$ as follows:

• $Q'$: The set of all functions $f : Q \to Q$.
• $\delta'(f, a) = g$ where $g(q) = f(\delta(q, a))$.
• $q_0'$ is the identity function.
• $F'$ is the set of all functions $f$ so that $f^2(q_0) = f(f(q_0)) \in F$ .

Let $w \in \sqrt{L}$. This means that $w^2 = ww \in L$. We want to show that $\delta'(q_0', w) \in L'$.

Define $h(q) = \delta(q, w)$. Since $w^2 \in L$, it follows that $h^2(q_0) \in F$. Hence $h \in F'$.

What's left is to show that $\delta'(q_0', w) = h$, which can be done via induction on the length of $w$.

Finally, we should show that $F'$ only accepts elements from $\sqrt{L}$ (and not more). I'll let you work this one out. It follows from the definition of $\mathcal{A'}$.

Answer 2

Let $D=(Q,\Sigma,\delta,q_0,F)$ be the DFA which recognizes $L$.

We need to construct an automaton which can simultaneously start from the initial ($q_0$) as well as "middle" state ($q_m$) of $D$, and parallelly parse two occurrences of $w$, one from $q_0$ to $q_m$ and another from $q_m$ to some accepting state.

When the first half is parsed, we also need to remember what this "middle" state $q$ was. Thus the machine will work on $Q\times Q\times Q$ state space, two to parse both halves of string, and third to remember the middle state.

The NFA which accepts $\sqrt{L}$ is: $N=(Q\times Q\times Q, \Sigma, \Delta, Q_0, F')$, where

$Q_0=\{(q_0,q_m,q_m)|q_m\in Q\}$

$F'=\{(q_m,q_f,q_m)|q_f\in F, q_m\in Q\}$

$\Delta=\{((q_1,q_2,q_m),a,(q_1',q_2',q_m))|\delta(q_1,a)=q_1', \delta(q_2,a)=q_2'\}$

Using this, it can easily be shown: $x\in \sqrt{L}\iff\exists$ an accepting run of $N$