关于正则语言的子集的研究

Research on the Subset of Regular Languages

基于泵引理和正则语言的代数判定定理,本文证明了正则语言的子集未必是正则语言。以L={x|x∈{0,1}^*,且x中(10)和(10)作为子串出现次数相等}为例,文中通过构造等价语言L’={x|x∈{0,1}^*,且x的首尾字符相同}证明了L的正则性,其子集L2={01)^n(10)^n|n≥0}易通过泵引理证明不是正则语言。最后将结论推广到上下文无关语言中。

Based on the pump lemma and the algebraic decision theorem of regular language,this paper proves that the subset of regular language is not necessarily regular language.Taking L={x|x∈{0,1}^*,(10)and(10)appear equally as substrings in x}as an example,this paper proves the regularity of L by constructing equivalent language,L’={x|x∈{0,1}^*,the first and last characters in x are the same},and its subset,L2={(01)^n(10)^n|n≥0}is easy to prove that it is not a regular language through pumping lemma.Finally,the conclusion is generalized to context-free language.