问如果语言L的每个子集都是正则的，那么L也是正则的？

EN

不仅仅是

如果语言L的每个子集都是正则的，那么L也是正则的

但同时也

如果语言L的每个真子集都是正则的，则L是有限的

证明：

这等同于以下语句

如果一种语言的L是无限的，那么它包含一个不是常规语言的子集。

正则语言的pumping引理指出：“存在一个长度l，使得如果该语言中的一个单词w比l长，则存在三个单词x,y,z，使得y是非空的，xyz == w并且每个xy^nz都在该语言中”。

如果一种语言是无限和规则的，那么它包含的单词长度超过任何给定的长度。因此，必须存在三个单词x,y,z，使得每个xy^nz都在该语言中。

现在，{xy^nz; n in N}的每个真子集都是L的真子集。现在，肯定存在非正则的xy^nz的真子集。因此，每个正则无限语言都有一个非正则的真子集。

如果一种语言是无限的，并且不是正则的，那么考虑它的任意一个真正的无限子集。如果子集不是规则的，则该语言不是反例。如果子集是规则的，那么使用前面的段落来找到一个不是规则的适当子集。由于真子集是传递的，所以这个子集是原始语言的真子集，并且该语言不是反例。

因此，每种无限语言都有一个非正则的真子集。

因此，如果一种语言的每个真子集都是正则的，那么该语言是有限的(因此也是正则的)。

QED

*例如，集合{xy^{n^2}z; n in N}是{xy^nz; n in N}的真子集，它不是正则的，如Myhill-Nerode theorem所示。