"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?

  • 4
    $\begingroup$ Hint: show that every infinite set has a non-CFL subset. Another hint: use the pumping lemma. $\endgroup$ – Shaull Jan 7 '16 at 18:32
  • 3
    $\begingroup$ There is no need to use the pumping lemma. You can use the fact that there are only countably many context-free languages. $\endgroup$ – Yuval Filmus Jan 7 '16 at 18:51
  • $\begingroup$ Cardinality really helps here. $\endgroup$ – chi Jan 7 '16 at 18:52
  • 1
    $\begingroup$ Once you figure out the answer, feel free to answer your own question. $\endgroup$ – Yuval Filmus Jan 7 '16 at 22:56
  • $\begingroup$ N.B. If we want to enforce using the pumping lemma, we can ask what happens if (say) all computable subsets of a set are context-free. $\endgroup$ – Yuval Filmus Jan 7 '16 at 22:57

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

| cite | improve this answer | |

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.

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.