If every subset of a language L is regular then L is regular?

Question

I know that converse of above theorem is not true i.e if L is regular then every subset of L need not be regular

Answer 1

Not only

if every subset of a language L is regular then L is regular

but also

if every proper subset of a language L is regular, then L is finite

Proof:

This is equivalent to the statement

if a language L is infinite, then it contains a subset that is not a regular language.

The pumping lemma for regular languages states that "there exists a length l such that if a word w in the language is longer than l, then there exist three words x,y,z such that y is non-empty, xyz == w and every xy^nz is in the language".

If a language is infinite and regular, then it contains a word longer than any given length. Thus, there neccessarily exist three words x,y,z such that every xy^nz is in the language.

Now, every proper subset of {xy^nz; n in N} is a proper subset of L. Now, there definitely exist proper subsets of xy^nz that are not regular*. Thus, every regular infinite language has a proper subset that is not regular.

If a language is infinite and not regular, then consider any of its proper infinite subsets. If the subset is not regular, then the language is not a counter-example. If the subset is regular, then use the previous paragraph to find a proper subset that is not regular. Since being a proper subset is transitive, this subset is a proper subset of the original language, and the language is not a counter-example.

Thus, every infinite language has a proper subset that is not regular.

Thus, if every proper subset of a language is regular, then the language is finite (and thus regular).

QED

*For example, the set {xy^{n^2}z; n in N} is a proper subset of {xy^nz; n in N} and it is not regular, as shown by the Myhill-Nerode theorem.