-1
$\begingroup$

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 ?

$\endgroup$
3
  • 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

2
$\begingroup$

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.

$\endgroup$
0

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