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 .
source to share