# Prove the language $\{x \in \Sigma^* : \exists w \in \Sigma^* \ xww \in L \}$ for regular language $L$ is regular

Let $$\Sigma=\{0,1\}$$ and $$L$$ be a regular language. Prove that $$Z(L) = \{x \in \Sigma^* : \exists w \in \Sigma^* \ xww \in L \}$$ is a regular language.

I tried to build a NFA based on the DFA that accepts $$L$$ but failed to do so. I don't know how to ensure the $$\, ww \,$$ part. Please advise.

• Related: the language $\{ w \mid ww\in L\}$ is sometimes called the root of $L$. The root of a regular language is again regular. See If L is a regular language then so is √L={w:ww∈L} May 21, 2021 at 12:35
• @HendrikJan I don't see how this helps (though it looks close). Any hint? May 21, 2021 at 12:41
• My aim was to indicate that the $ww$ suffixes can be recognized using a finite state construction. Nathaniel made that explicit in his answer. In the $\sqrt L$ construction you keep $w$, in Nathaniels construction it is omitted from the string. May 21, 2021 at 18:41

Let $$A = (Q, \delta, q_0, F)$$ a DFA that accepts $$L$$. For $$q, q' \in Q$$, define:

• $$L_{q,q'} = \{u\in \Sigma^*, \delta^*(q, u) = q'\}$$;
• $$L_{q',F} = \{u\in \Sigma^*, \delta^*(q', u) \in F\}$$.

It is quite easy (can you prove it?) to see that those languages are regular.

Now the language $$\{x\in \Sigma^*\mid \exists w\in\Sigma^*, xww\in L\}$$ can be written as: $$\bigcup\limits_{q\in Q}L_{q_0,q}\cdot M(q)$$ Where $$M(q) = \left\{\begin{array}{rl}\emptyset&\text{if }\bigcup\limits_{q'\in Q}L_{q,q'}\cap L_{q',F}=\emptyset\\\{\varepsilon\}&\text{otherwise}\end{array}\right.$$

$$M(q)$$ is regular since it is either $$\emptyset$$ or $$\{\varepsilon\}$$, so that means that $$Z(L)$$ is regular.

• Thank you @Nathaniel, can you please explain the intuition behind $M(q)$? I'm trying to understand what it means. I can't see why the original language can be expressed in that way. May 21, 2021 at 12:45
• We want to find the states $q$ such that there is a "double" path to a final state of $A$, that is states $q$ such that $\exists w\in \Sigma^*, \delta^*(q, ww)\in F$. Those $w$ are expressed by $\bigcup\limits_{q'\in Q}L_{q,q'}\cap L_{q',F}$, so we just need to now if this set is empty or not, and that is what is expressed by $M(q)$. May 21, 2021 at 12:50
• Thank you. If this set is empty, shouldn't we accept only $x \in L$? In this case the union would accept any path from $q_0$ to $q$, wouldn't it? May 21, 2021 at 12:56
• If $M(q) = \emptyset$, that means that $q$ is not a good state to end with when reading $x$. In this case, $L_{q_0,q}\cdot M(q) = \emptyset$ (because the concatenation with the empty set is the empty set), so those paths are not considered. May 21, 2021 at 12:58
• Oh, I didn't know that the concatenation with the empty set if the empty set. Now it's clear, thank you! May 21, 2021 at 13:00

The operator $$Z(L) = \{ x \mid xww\in L \text{ for some } w\}$$ takes strings from the original language $$L$$ but keeps only prefixes $$x$$ that are obtained by chopping a suffix of the form $$ww$$.

This is a special application of the right quotient operation: $$L/K = \{ x \mid xy\in L \text{ for some } y\in K\}$$.

It is known that the family of regular languages is closed under right quotient of arbitrary languages, see Show L1 /L2 is regular. For your problem take $$K = \{ww\mid w\in \Sigma^*\}$$.

• Thank you, that's a neat solution :) May 22, 2021 at 5:40