资源描述：
《一族由前缀码生成的极大自由幺子半群》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、第24卷第2期四川理工学院学报(自然科学版)Vol24No22011年4月JournalofSichuanUniversityofScience&Engineering(NaturalScienceEdition)Apr2011文章编号:16731549(2011)02014803一族由前缀码生成的极大自由幺子半群雷宇,汪莉萍,胡华碧(贵阳医学院基础医学院,贵阳550004)**+摘要:设X是由字母表X生成的自由幺半群且A是X的非空子集,如果AAX=,则称iiA是前缀码。设{B1,B2}是X的任意2划分,令A=B2B1(XB1)E
2、,i=1,2,其中E=i+102M-1M*B1(B1B1B2B1B2B1B2B1B2X),M0。文章证明了A是前缀码且幺半群A是自*由幺半群X的极大自由幺子半群。关键词:语言图;极大码;极大自由幺子半群中图分类号:O15627文献标识码:A*字的连接运算,则X是由X生成的自由幺半群,我们称1基本概念+**X=X{1}是由X生成的自由半群。令L是X的非*+空子集,称L是X的一个语言。如果LLX=,则极大自由幺子半群作为一类特殊的自由幺子半群*称L是前缀码。如果语言L是X的基,则称L是码。如论,引起人们广泛研究兴趣。文献[1]中赵平、李志敏给+
3、果码L满足:对任意XL,有L{}不是码,则出了自由幺半群A*的两类极大自由幺子半群;文献称L是极大码。[2]中赵平、徐波对自由幺半群A*的两类极大自由幺*定义2令S是X的任意自由子半群,若S满足:子半群进行了推广;文献[3-4]中赵平、徐波分别给出*对X的任意自由子半群T,ST,那么S=T或T=了自由幺半群X*的一族极大自由幺子半群;文献[5]**X,则称S是X的极大自由子半群。中胡华碧得到了自由幺半群的一族新的极大自由幺子*0约定对任意xX,x=1,lg(x)表示x所含X半群。本文构造了自由幺半群的一族新的极大自由幺子+中字母的个数,称为x的长度
4、。对任意AX,令lg(A)半群。***=max{lg(x):xA},TA={xX:yX,使xy令A是幺半群S的任意非空子集,且A={1}AC*2n**A},TA=XTA,则显然ATA且1TA。AA,显然A是半群S的子半群,称A本文未定义的术语及记法参见文献[5]。是由A生成的幺半群S的子半群。定义1设M是幺半群S的任意非空子集,若M满2结果及证明足:u1u2un=v1v2vm,u1,u2,un,v1,v2,,vmMm=n,ui=vi,i=1,2,,n,则称M是幺半群S的引理1若A是前缀码,则A是码。基,显然M*是S
5、的幺子半群且1M。如果存在S的一证明见文献[5]。个基B,使得S=B*,则称S是自由幺半群。引理2设X,B1,B2,C同上,则C是一个前缀码且**令X是一个字母表,称X上的任意有限字母的排列X=CTC。*+是一个字,特别地,用1表示不含字母的空字.令X是X证明由C的定义易验证CCX=,即C是前***+*上所有的字的集合,定义X上的二元运算为任意两个缀码。要证明X=CTC。只需证明:XCTC。任意收稿日期:20101208基金项目:贵州省科学技术基金项目(20103174)作者简介:雷宇(1973),女,贵州贵阳人,讲师,主要从事信息及编码理论方面的研
6、究。第24卷第2期雷宇等:一族由前缀码生成的极大自由幺子半群149+**取xX,我们对x的长度lg(x)进行归纳证明。是码,若AD,那么A=D或D=X。现设DX,(1)当lg(x)=1,由C及T的定义易知XT,从**CC因AAD,有B2D,而由X=B1B2知,B1D*而xXTCCTC。。下面证明AD,分以下步骤进行讨论:+*(2)假设对任意xX,lg(x)k,有xCTC。pqq(1)若xD,xX,则xD,pq。事实上,x*当lg(x)=k+1,若xTC,则显然有xTCCTC;D,令=xqxp个q
7、=xpxpq个,这说明字在D中的表C若xTC,由C、TC和Wx的定义知WxC,即存法不唯一,与已知D是码矛盾。+在yC,zX,使x=yz,从而lg(z)k。由归纳假(2)B1D=。若存在xB1D,则任意取b1****i+1i+2*设得zCTC,于是x=yzCCTCCTC。综上,XB1D,b2B2D,因(x)b1B1AD,*iii*=CTC。b1(b2)B1(XB1)AD,由引理4可推出b1引理3{HT设X,B1,B2,C同上,则C是一个极大D,与b1B1D矛盾。码。(3)对b1B1,有b1D,i=
8、1,2。事实上,若存i+
