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

Research on the Subset of Regular Languages

作　　者：饶淑珍 聂佳 过榴晓[1] 朱平[1] RAO Shuzhen;NIE Jia;GUO Liuxiao;ZHU Ping(School of Science,Jiangnan University,Wuxi,Jiangsu 214122)

机构地区：[1]江南大学理学院,江苏无锡214122

出　　处：《科教导刊》2020年第24期36-38,共3页The Guide Of Science & Education

基　　金：江南大学教学教改课题资助;全国大学生创新课题资助。

摘　　要：基于泵引理和正则语言的代数判定定理,本文证明了正则语言的子集未必是正则语言。以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.

关 键 词：正则语言 正则语言的代数判定定理 泵引理 上下文无关语言 

分 类 号：H0-0[语言文字—语言学]