# Regularity of a language constructed from a know regular language

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.

As you mention, if $$n$$ was fixed, then this is not too difficult to prove. So, the idea would be to show that in fact, $$n$$ can be bounded a-priori, depending only on $$A$$, and not on $$x$$.
To this end, consider some word $$x\in \Sigma^*$$, and suppose $$x^m\in A$$ for some $$m$$. Let $$k$$ be the number of states in some DFA $$D$$ for $$A$$ (e.g., minimal DFA). Suppose $$m>k$$, then there exist $$0\le i such that the run of $$D$$ on $$x^i$$ reaches the same state as on $$x^j$$. But this implies that $$x^{m-{j-i}}$$ is also accepted by $$D$$.
Thus, it's enough to consider $$n\le k$$. So you can rewrite your language as $$\{x| \exists n\le k,\ x^n\in A\}$$ And this is regular.