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.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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|cite|improve this question
up vote 7 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|cite|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|cite|improve this answer

It is often simpler to construct a nondeterministic automaton than a deterministic one -- but having a deterministic automaton gives us more to work with. If we already know that the existence of an NFA or DFA are both equivalent to being regular, we can get the best of both worlds by assuming that we have a DFA $A_L$ for $L$, but just wanting to construct an NFA for $\sqrt L$.

The first thing our new automaton will do when it starts to read a string $w$ is to guess which state $A_L$ will be in after having read $w$ once. We can do this by having multiple parallel $\epsilon$ transitions out of an initial state, each leading to its own independent sub-automaton that recognizes "strings $w$ such that $w$ can move $A_L$ from the initial state to the guessed intermediate state, and $w$ can also move $A_L$ from the intermediate state to an accepting state.

The language each of these sub-automata must recognize is the intersection of two regular languages, so it has an automation we can use.

More concretely, the sub-automaton can have a state for each pair of states $(p,q)$ from $A_L$, simultaneously simulating two copies of $A_L$ recognizing the input string from different starting states. There are transitions $(p_1,q_1) \overset{a}\to (p_2,q_2)$ whenever $A_L$ has transtions $p_1\overset a\to p_2$ and $q_1\overset a\to q_2$, and $(p,q)$ accepts if $p$ is the guessed intermediate state and $q$ is accepting in $A_L$.

share|cite|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.