# Does every infinite recursive language contain an infinite regular subset? [duplicate]

My intuition is telling me that this is not the case. But I am having trouble formulating a proof for this.How do I prove it ?

• What have you tried? Where did you get stuck? We do not want to just do your (home-)work for you; we want you to gain understanding. However, as it is we do not know what your underlying problem is, so we can not begin to help. See here for a relevant discussion. If you are uncertain how to improve your question, why not ask around in Computer Science Chat? You may also want to check out our reference questions.
– Raphael
May 20, 2015 at 16:07
• @Raphael Sorry. No memory. I did not remember that it had been answered previously, and what's worse, by myself. Actually I had to think again to get the answer. Well ... so it goes. But this question raises another question for meta. May 20, 2015 at 16:31
• I'm sorry if this was a duplicate but I didn't thought of searching what subsets a language can have. I had thought of giving a counter example and using the pumping lemma but I could't think of a language with the above criteria. All I wanted was a hint. Thanks anyway. May 21, 2015 at 14:07

## 1 Answer

Take the language $L= \{a^{2^p}\mid p\geq 1\}$.

It is easy to show with the pumping lemma that it contains no infinite regular subset.

Try to prove it is a counter-example.

The reason is that the pumping lemma requires, for infinite regular sets, that some infinite sequence of strings in the language grows linearly in size. But the language $L$ contains no such sequence because its strings grow exponentially. Hence it cannot contain an infinite regular subset.