Regularity of a language constructed from a know regular language

Question

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.

Answer 1

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<j\le m$ 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.