If every subset of L is regular, then L is regular?

Not only

if every subset of L is regular, then L is regular

but also

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

Evidence:

This is equivalent to saying

if the language is L

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

The pumping lemma for regular languages ​​says that "there is a length L

such that if a word w

in the language is greater than L

, then there are three words x,y,z

that are y

not empty, xyz == w

and each 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 are necessarily three words x,y,z

such that each xy^nz

is in the language.

Now each proper subset {xy^nz; n in N}

is a proper subset in L

. Now there are definitely valid subsets xy^nz

that are not regular *. Thus, every regular infinite language has its own subset that is not regular.

If a language is infinite and not regular, consider any of its own infinite set. 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 the correct subset that is not regular. Since the correct 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 its own subset that is not regular.

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

QED

* For example, a set {xy^{n^2}z; n in N}

is a proper subset {xy^nz; n in N}

and is not regular, as shown in the Mihill-Nerod theorem .