For a regular language $L$, $Z(L)=\{x \in \Sigma ^* | \exists w \in \Sigma^*, xww\in L \}$, Is $Z(L)$ regular?

Question

I was able to prove it is regular by induction on the length of the regular expression of $L$.
I was wondering if there is a better way to prove it. Better in the way that it is not "Induction magic". I thaught about trying to find homomorphizm that can map this language to the original $L$ but I couldn't get anywhere.
Is there a way to prove this other than induction?

Answer 1

We can use the Myhill-Nerode theorem. For $x,y\in\Sigma^*$ write $x\sim_Ly$ iff there is no distinguishing extension for $x$ and $y$ with respect to the language $L$, and $x\sim_Zy$ iff there is no distinguishing extension for $x$ and $y$ with respect to the language $Z(L)$. Suppose that $x\not\sim_Zy$. Then without loss of generality there is a $z\in\Sigma^*$ such that $xz\in Z(L)$ and $yz\notin Z(L)$. Since $xz\in Z(L)$, there is a $w\in\Sigma^*$ such that $xzww\in L$. Clearly $yzww\notin L$, so $zww$ is a distinguishing extension for $x$ and $y$ with respect to $L$, and therefore $x\not\sim_Ly$. Thus, each $\sim_Z$-equivalence class is a union of $\sim_L$-classes. $L$ is regular, so by the Myhill-Nerode theorem there are only finitely many $\sim_L$-classes and hence only finitely many $\sim_Z$-classes, and the other direction of the Myhill-Nerode theorem ensures that $Z(L)$ is regular.