1
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.