[Solved]: Does every infinite recursive language contain an infinite regular subset?

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 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.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/42804

 Ask a Question

 Download Related Notes/Documents