subsets of non regular language

Question

I know that there are many languages that are context free but not regular like $\{a^n b^n :n>0\}.$ But I want to know if every context free but non-regular language has infinitely many non-regular subsets?

Thank you.

Answer 1

Yes.

If $L$ is context free but non-regular, then for every positive integer n, let $L_n\subseteq L$ be a language such that $|L-L_n|=n$. If $L_n$ were regular, then $L$ would be regular, since an automaton which decides $L_n$ could be (non-deterministically for simplicity) expanded to decide $L_n$ and exactly all the finite strings removed from $L$, and thus the automaton also decides $L$. Thus we conclude that none of $L_n$ may be regular.

Answer 2

If $L$ is context-free but not regular, $L$ must be infinite. For each $w\in L$ let $L_w=L\setminus\{w\}$. The finite language $\{w\}$ is certainly regular, and the union of two regular languages is regular, so if $L_w$ were regular, $L=L_w\cup\{w\}$ would also be regular. Thus, $L_w$ cannot be regular, and each of the infinitely many languages $L_w$ is a distinct non-regular subset of $L$.