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

computation-theory, regular-language

Solution

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.

Problem

Original source