如果语言L的每个子集都是常规的,那么L是常规的吗？

Question

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

Answer 1

不只

如果语言L的每个子集都是规则的,则L是规则的

但是也

如果语言L的每个适当的子集是规则的,那么L是有限的

证明:

这相当于声明

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

该泵引理的正规语言指出:"存在的长度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定理所示.