h-1保持各种独立语言的条件-论文.pdf

《h-1保持各种独立语言的条件-论文.pdf》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第33卷第2期延安大学学报(自然科学版)Vo1．33No．22014年6月JournalofYananUniversity(NaturalScienceEdition)Jun．2014DOI：10．3969／J．ISSN．1004—602X．2014．02．016h保持各种独立语言的条件刘莉(延安大学数学与计算机科学学院，陕西延安716000)摘要：设h：一是同态映射，主要研究了h保持各种独立语言的条件。得到了h保持P一独立语言，Pd一独立语言以及JD一独立语言的充分必要条件都是h(1)：{1}。此外，证明了若h：一是同态映射，则h-1保持P一独立语言。关键词：同态映射；p一独

2、立语言；一独立语言；一独立语言；p6一独立语言中图分类号：O159文献标识码：A文章编号：1004—602X(2014)02—0016—02则称H是关于≤的独立语言，有时记作P一独立语1基本概念．一日0令是至少含有两个元素的有限字母表。上设h是到的映射，若对任意的，Y∈X’有限字符串称为字，不含有任何字母的字称为空字，都有h(xy)=h()h(Y)成立，则称h是上的同记作1。所有有限字和空字1的集合记为。记态映射，h表示由h(X)到的一个对应关系。X=X＼{1}。h(0)表示由n的原像组成的集合。设莎是一个设s是一个非空集合，SXS的子集P称为．s上语言集合，若任意的L∈莎，h

3、一(L)∈莎，则称h保的二元关系，若P满足下面的条件：持语言。(1)(V∈S)xpx2主要结论(2)(V，Y∈S)xpy~ypx命题1设h：X一是同态映射，则h保持(3)(V，y，∈S)xpy，ypz~xpzP一独立语言的充分必要条件是h(1)={1}。则称P是5上的等价关系，等价关系P称为右同余(左同余)，若满足apbacpbc(apbcapcb)证明：()假设h(1)≠{1}，则存在．Tf∈X，(Vc∈s)。若P既是左同余又是右同余，则称P是使得∈h(1)，则有{1，}h(1)。而=lx=同余关系。1，即1≤。因此h(1)不是P一独立语言，而设W，∈X’我们定义以下关系：{

4、1}是P一独立语言，这与h一保持P一独立语言矛(1)W≤当且仅当存在ft．X使得=X,W=盾，故h(1)={1}。(乍)设是P一独立语言，若h(L)不(2)W≤当且仅当存在n≥1使得口=W；是P。一独立语言，则存在，∈h(L)，W≠，使得(3)≤当且仅当存在，Y∈X使得=xwy；W≤。即存在∈X，使得z)：删=WX。则h(13)=(4)W≤d当且仅当存在，yft．X使得=WX,=h(x)h(W)=h()h()。由1)，∈h(L)，知存在yw。，Y∈L，使得h(x)=。，h(1t))=Y，即有=h(x)Y=设HCX，对任意的11,，∈H，若≤H=()，又因为是P一独立语言，故h(

5、)=1。又h收稿日期：2013—12—06作者简介：刘莉(1985一)，女，陕西延安人，延安大学助教。第2期h保持各种独立语言的条件17={1}，所以：1。这与∈X矛盾。即有h()使得∈h(1)，故=lx=xl，即1≤6。因此h是P一独立语言。(1)不是P一独立语言，而{1}是P一独立语言，这命题2设h：X一是同态映射，则h保持与h保持P一独立语言矛盾。故h(1)={1}。P一独立语言。(仁)设三是一独立语言，设，∈h证明：设LC_X是P～独立语言，若h()不(L)，=xwy，，Y∈X，贝0h()=h()h(w)h(Y)，是P一独立语言，则存在w，∈h(L)，n≥2，使得即存在

6、，w∈L，使得h()=，h(w)=w，故=w=，即有h(w)=h()=[h()]，即存在，Y∈h(x)wh(y)，因为是P一独立语言，故h()=h￡，使得h(w)=，h(v)=Y，故=Y。这与￡是P。(Y)=I。又h(1)={1}。故=Y：I，即=w。一独立语言矛盾。因此h()是P一独立语言。所以h()是P一独立语言。命题3设h：X_÷是同态映射，则h保持参考文献：[1]ShyrHJ．FreeMonoidsandLanguage[M]．Taiwan：HonP一独立语言的充分必要条件是h(1)={1}。MinBookCompany，2001．证明：(j)假设h(1)≠{1}，则存

7、在∈X，[2]ChunhuaCao，DiYang．NotedonHomomorphismsWhich使得∈h一(1)，贝0=lx=xl，最口≤d1。因此h一PreserveCertainFamiliesofLanguage[J]．SoutheastAsian(1)不是P一独立语言，而{1}是P一独立语言，这BulletinofMathematics，2005(29)：415—422．与h保持P。一独立语言矛盾。故h(1)={1}。[3]ItoM，ShyrHJ．P—LanguagesandP—