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&gt;k$, then there exist $0\le i&lt;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.