I’m working through so textbook questions on regular languages, and came across a problem that amounts to showing the following language is regular, given that $A$ is a regular language:

$$

{x|exists n ge 0 ; exists y in A ; y = x^n}

$$

I’ve attempted to show that this is regular by a contradiction using Myhill-Nerode, by assuming it has infinite index, and showing this means that $A$ must have infinite index. However, I cannot seem to get this proof to work, because taking representatives of each class lets me show an infinite number of pairs of elements in $A$ that are not in the same class, but these elements do not uniquely correspond to my representatives, so I cannot show that an element is not in the same class as infinitely many others.

However, the book seems to indicate that the solution should be construction.

I can also easily see the construction for a NFA if $n$ was fixed, but this doesn’t seem to offer any help, as this makes the states depend on $n$ (by using tuples of states, and simultaneously moving states once).

If anyone could suggest how to go about constructing the required automata, that would be very helpful.