# Infinite prefix-closed context-free languages contain an infinite regular subset

The Problem:

Say that a language is prefix-closed if all prefixes of every string in the language are also in the language. Let C be an infinite, prefix-closed, context-free language. Show that C contains an infinite regular subset.

Can we show this by using Myhill-Nerode Theorem?

Given a normal form grammer $$G$$ for an infinite prefix-closed $$L$$, examine the (almost) regular grammer $$G'$$ obtained by transforming rules of the form $$A\rightarrow BC$$ into $$A\rightarrow B$$. I leave it to you to show that $$L(G')$$ satisfies your requirements.
Another easy solutions uses the pumping-lemma for context-free languages. Let $$L$$ be infinite, prefix closed and context free. Then there is an $$l$$ such that for all $$z\in L$$ with length at least $$l$$ there is a decomposition $$uvwxy=z$$, s.t. $$vx$$ has length $$>0$$, $$vwx$$ hat length $$\leq l$$ and $$\forall i\geq 0: uv^iwx^iy\in L$$ (actually, we don't need $$l$$ and just one $$z$$ and since $$L$$ is infinite, there is one).
Now take such a word $$z$$ and some decomposition. Then $$uv^*$$ and $$uvwx^*$$ are regular expression for subsets of $$L$$ (since $$L$$ is prefixed closed) and at least one of them generates an infinite language, because $$x$$ and $$v$$ cannot both be empty.
Using the Myhill-Nerode Theorem seems rather difficult: Take the language $$L=\{a^nb^m|m\leq n\}$$. While $$A=\{a\}^*=\{a^n| n\geq 0\}$$ is an infinite regular subset of $$L$$, all the $$a^i$$ ($$i\geq 0$$) are pairwise inequivalent w.r.t. the Nerode relation of $$L$$. So we need an additional ingredient to show why we can collapse equivalence classes by not allowing certain suffixes (that is what taking a subset practically means for the Nerode relation).