$L$ is regular. Show that $Root(L) $ is also regular

Question

Let $Root(L)=\{w \mid \exists {n\in \mathbb{N}} \text{ such that } w^n\in L\}$.
How to deal with it ? I tried think about modifications connected with automat for $L$, but it failed. Help me, please.

Answer 1

Let $L$ be a regular language. Then there is a surjective monoid morphism $f:A^* \to M$ and a subset $P$ of $M$ such that $f^{-1}(P) = L$. I claim that $Root(L) = f^{-1}(Q)$ where $$ Q = \{m \in M \mid \exists n \in \mathbb{N} \text{ such that } u^n \in P \} $$ Thus $L'$ is recognized by the finite monoid $M$ and hence is regular.

Proof of the claim. \begin{align*} f^{-1}(Q) &= \{u \in A^* \mid f(u) \in Q \} \\ &= \{u \in A^* \mid \exists n \in \mathbb{N} \text{ such that } f(u)^n \in P \} \\ &= \{u \in A^* \mid \exists n \in \mathbb{N} \text{ such that } f(u^n) \in P \} \\ &= \{u \in A^* \mid \exists n \in \mathbb{N} \text{ such that } u^n \in f^{-1}(P) \} \\ &= \{u \in A^* \mid \exists n \in \mathbb{N} \text{ such that } u^n \in L \} \\ &= L' \end{align*}