"If every subset of a set is a CFL, then the set must be regular."
I want to prove it, could anyone please give me some hints?
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.Sign up to join this community
Suppose that $L$ is a language such that each subset of $L$ is context-free. I claim that $L$ must be finite, and so regular. Indeed, otherwise $L$ would have uncountably many subsets, and so not all of them could be context-free (since there are only countably many context-free languages).
Lemma 1: any language over a finite alphabet has either a finite or countably infinite number of elements. Option one, your language is finite. Option two, your language is infinite, but you can still sort all the strings in "lexicographic order" (i.e. alphabetical order). This means they can be enumerated, so there are only countably many.
Lemma 2: a countably infinite set has uncountably many subsets. This is called Cantor's Theorem, and for the sake of time I'm not going to prove it here, but the proof is very elegant and can be found online.
Lemma 3: the set of context-free languages is countable. You can write down the grammar of any context-free language as a string of finite length (a CFG), and these strings can be sorted lexicographically.
Lemma 4: if a language is infinite, it must have a non-context-free subset. If a language is infinite, it has countably many elements, which means uncountably many subsets. This means there are more distinct subsets than context-free languages. So some of these subsets must be non-context-free.
Lemma 5: if a language is finite, it is regular. You can make a regular expression for it by just union-ing together a whole lot of singleton strings.
Theorem: if a language has no context-free subset, it must be regular. The contrapositive of Lemma 4 means this language must be finite, and so Lemma 5 means it's regular.