HiveBrain v1.2.0
Get Started
← Back to all entries
snippetMinor

How to prove "if every subset of a set is a CFL, then the set must be regular."

Submitted by: @import:stackexchange-cs··
0
Viewed 0 times
cflthemustregulareveryprovethenhowsubsetset

Problem

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

Solution

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

Context

StackExchange Computer Science Q#51595, answer score: 3

Revisions (0)

No revisions yet.