Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question

2 Answers 2

up vote 3 down vote accepted

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'}$.

share|improve this answer

The shortest way to prove this result is to use the fact that a language is regular iff it is recognized by a finite monoid. A language $L$ of $A^*$ is recognized by a finite monoid $M$ if there is a surjective monoid morphism $f:A^* \to M$ and a subset $P$ of $M$ such that $f^{−1}(P) = L$.

Now let $Q = \{ x \in M \mid x^2 \in P\}$. Then \begin{align} f^{−1}(Q) &= \{ u \in A^* \mid f(u) \in Q \} = \{ u \in A^* \mid f(u)^2 \in P \}\\ &= \{ u \in A^* \mid f(u^2) \in P \} = \{ u \in A^* \mid u^2 \in L \}\\ &= \sqrt{L} \end{align} Thus $\sqrt{L}$ is regular. This method actually shows that if $M$ recognizes $L$, then it also recognizes $\sqrt{L}$. This is useful to prove further properties: for instance if $L$ is star-free, so is $\sqrt{L}$.

References

[1] J.-É. Pin and J. Sakarovitch, Some operations and transductions that preserve rationality, in 6th GI Conference, Berlin, (1983), 277-288, LNCS 145, Springer.

[2] J.-É. Pin and J. Sakarovitch, Une application de la représentation matricielle des transductions, Theoret. Comp. Sci. 35 (1985), 271-293. (in French)

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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