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 ?

  • 1
    $\begingroup$ 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. $\endgroup$
    – Raphael
    May 20, 2015 at 16:07
  • $\begingroup$ @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. $\endgroup$
    – babou
    May 20, 2015 at 16:31
  • $\begingroup$ 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. $\endgroup$ May 21, 2015 at 14:07

1 Answer 1


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.


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