Problem Detail: 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 ?
Asked By : user3714205
Answered By : babou
Take the language $L= {a^{2^p}mid pgeq 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.
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/42804 Ask a Question Download Related Notes/Documents
