regular-language - 如果语言 L 的每个子集都是正则的，那么 L 是正则的吗？

Question

我知道上述定理的逆是不正确的，即如果 L 是规则的，那么 L 的每个子集都不需要是规则的

Answer 1

不仅

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

但是也

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

证明：

这相当于声明

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

常规语言的抽引引理指出“存在一个长度l，如果w语言中的一个词长于，l则存在三个非空的词，并且每个词都在该语言中”。x,y,zyxyz == wxy^nz

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

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

如果一种语言是无限的且不规则的，那么考虑它的任何适当的无限子集。如果子集不规则，则该语言不是反例。如果子集是正则的，则使用上一段找到不正则的真子集。由于作为真子集是可传递的，因此该子集是原始语言的真子集，并且该语言不是反例。

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

因此，如果语言的每个真子集都是正则的，那么该语言是有限的（因此是正则的）。

量子点

*例如，该集合{xy^{n^2}z; n in N}是 的一个真子集{xy^nz; n in N}并且它不是正则的，如Myhill-Nerode 定理所示。