# Prove that every infinite regular language has an undecidable infinite subset

I am having trouble writing a formal proof for this. I understand that we have an infinite regular language. This means that we have uncountable many subsets of the infinite regular language and due to this we have a subset which is undecidable. However, I don't know if this reasoning completes the proof or not. What's a recommended way to answer this kind of question in exam?

With the particular focus on regular languages, the intended solution might have been something like using the pumping lemma to find $x,y,z$ such that $xy^nz$ is in your language for every $n$, and then consider the subset $\{xy^nz\mid n\in A\}$, where $A$ is your favorite undecidable set of natural numbers.
• The argument with the pumping lemma probably needs a remark for cases like $x=y=z$ or with multiples, where the numbers of the original undecidable set are not as obviously visible; or suffix/prefix combinations from x/z that generate an additional factor y. Of course, a shift of an undecidable set by a fixed number will still be undecidable. – Peter Leupold Apr 26 '18 at 8:28
• @PeterLeupold: I'm imagining choosing and fixing $x,y,z$ first. Once their values are known (and $y$ is nonempty), then for each word there is only on $n$ such that it can be $xy^nz$. – Henning Makholm Apr 26 '18 at 10:26