8
$\begingroup$

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.

$\endgroup$

4 Answers 4

15
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ It seems that the definition of transition function should be $\delta'(f,a) = g$ where $g(q)=\delta(f(q),a)$. Otherwise induction proof does not work. $\endgroup$
    – sas
    Sep 27, 2023 at 9:55
9
$\begingroup$

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)

$\endgroup$
1
  • $\begingroup$ Thank you Jean-Éric for the reference. In [1] the result, Prop. 4.5, is an easy application of the main theorem (one could say "an example"). Was the result already known to you back then? And if so do you have an even older reference? This is for historical purposes. Amitiés, -phs $\endgroup$
    – phs
    Mar 25 at 14:45
3
$\begingroup$

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

$\endgroup$
2
$\begingroup$

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$

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .