左-(n,2)语言的一些例子

刘 莉

(延安大学 数学与计算机科学学院，陕西 延安 716000)



左-(n,2)语言的一些例子

刘 莉

(延安大学 数学与计算机科学学院，陕西 延安 716000)

每个(n,k)-语言都是左-(n,k)-语言，给出了uv+以及A(ak)+是左-(n,2)-语言但不是(n,2)-语言的条件.

左-(n,2)语言；本原字；左不可数语言

1 预备知识

关于不可数语言即(n,1)-语言的性质，人们已经做了大量的研究并得到了十分有价值的结论(见文献[1-9])，而不可数语言无需考虑它的指数.石辉然在文献[3]中证明了(n,k)语言的一些性质，本文在此基础上做了进一步研究，构造了一些左-(n,2)-语言.

设X是非空有限字母表，X上的有限字符串称为字，不含任何字母的字称为空字，用1表示. 所有字的集合用X*表示. 设X+=X*{1}.X*的任一非空子集称为语言.设L是X*上的语言，对任意的x,y,z∈X*，若存在正整数n，k≥1使得xynz∈L当且仅当xyn+kz∈L，则称L是(n,k)语言.若存在n≥0,k≥1,使得ynz∈L当且仅当yn+kz∈L，则称L是左-(n,k)-语言.[3].由定义易知，每个(n,k)-语言都是左-(n,k)-语言.若k=1，则(n,k)-语言称为不可数语言. 如果一个字不能表示成任何非空字的方幂，则称这个字是本原字，所有本原字的集合用Q表示. 以下引理将在本文中用到.

引理1[3]设u∈X*,v∈X+，则uv+是(n,2)- 语言当且仅当对任意的f∈Q，f∈Q，k≥3都有v≠fk.

引理2[7]若um,vn的前 lg(u)+lg(v)长度的子字相同，这里m,n≥1，则u和v可以表示成同一个本原字的方幂.

引理3[1]设uv=fi，其中u,v∈X+，f∈Q,i≥1.则存在g∈Q使得vu=gi.

本文中用到的定义但未出现的可参考文献[1，10-12].

2 主要结论

命题 2.1 设u,v∈X+，则uv+是左-(n,2)-语言但不是(n,2)-语言的充分必要条件是存在本原字w及k≥3使得v=wk且对任意的m≥1，都不是wm的后缀.

证明. (⟹)设uv+是左-(n,2)-语言但不是(n,2)-语言. 假设对任意的w∈Q，k≥3都有v≠wk，则由引理1.1 知uv+是(n,2)-语言. 矛盾. 故存在本原字w及k≥3使得v=wk. 下面假设存在整数m≥1 使得u≤swm.

1)若u=wm, 则uv+=wm(wk)+. 取y=w,z=wm+(t+1)(k-1)+1. 其中t≥0 .则ytz=wmw(t+1)k∈wm(wk)+.即有yt+2z=wm+(t+1)k+2. 因为m≥1,k≥3, 所以m+(t+1)k

2)若u=w1wh，其中0≤h≤m，w=w2w1，w1,w2∈X+.因为w2w1=w∈Q，所以w1w2∈Q.对任意的s≥0, 取y=w1w2，z=(w1w2)h+(s+1)(k-1)+1w1.则ysz=(w1w2)h+skw1=w1wh+(s+1)=(w1wh)(wk)s+1∈uv+. 故有ys+2z=(w1w2)h+(s+1)k+2w1=w1wh+(s+1)k+2=(w1wh)w(s+1)k+2=uw(s+1)k+2. 因为k≥3, 所以 (s+1)k<(s+1)k+2<(s+2)k. 故w(s+1)k+2∉(wk)+. 因此ys+2z∉u(wk)+=uv+.即uv+不是左-(n,2)-语言. 矛盾.综上，若uv+是左-(n,2)-语言但不是(n,2)-语言,则存在本原字w及k≥3使得v=wk且对任意的m≥1，u都不是wm的后缀.

(⟸)假设存在本原字w及整数k≥3使得v=wk且对任意的m≥1，u都不是wm的后缀.

由引理1知wv+不是(n,2)-语言.下面证明uv+是左-(n,2)-语言. 设r=lg(u)+lg(w) ，i>3r.假设存在y∈X*， 使得yiz∈uv+. 则存在整数j≥1 使得yiz=uvj=uwkj.设yr=uwi1w3，其中i1≥1，w=w3w4，w3,w4∈X*且yi-rz=w4wkj-i1-1. 即有yi-rz=w4wkj-i1-1w4. 因为i-r>2r且 lg(yi-r)>lg(y2r)，所以ylg(w)yi-r-lg(w)z=yi-rz=(w4w3)kj-i1-1w4=(w4w3)lg(y)(w4w3)kj-i1-1lg(y)w4. 因此yi-r和(w4w3)kj-i1-1的前lg(y)+lg(w3w4)长度的部分相同，由引理1.2知y和w4w3是同一本原字的方幂. 因为w3w4=w∈Q, 则由引理1.3知w4w3∈Q. 即有y=(w4w3)t′ ，其t′≥1.因此(w4w3)t′r=yr=uwt′rw3.故w4wt′r=w4(w3w4)t′r=(w4w3)t′rw4=yrw4=uwi1+1. 若t′r-i1-1≥0, 则u=w4wt′r-i1-1，即w3u=wt′r-i1.这与对任意的m≥1，u都不是wm的后缀矛盾. 若t′r-i1-1≤-1, 即i1+1-t′r≥1，且w4=uwi1+1-t′r，w=w3w4.矛盾. 因此对任意的y∈X+,z∈X*,i>3r，都有yizuv+. 故uv+是左-(n,2)-语言.

推论1 设u∈X*,v∈X+. 则uv+是左-(n,2)-语言当且仅当存在本原字w使得以下条件成立：

1)v=wi，其中i≤2 ；

2)v=wi，其中i≥3且对任意m≥1，u不是wm的后缀.

命题1 设A是左-(n,2)-语言且A⊆X*b，其中b∈X，|X|≥2.则对任意的a∈X，a≠b，k≥3，A(ak)+是左-(n,2)-语言但不是(n,2)-语言.

证明： 设A是指数为k1的左-(n,2)-语言，L=A(ak)+.对任意的整数m≥0，w∈A，取x=wa(m+1)(k-1)，y=a，z=a.则xymz=wa(m+1)k∈L.因为(m+1)k<(m+1)k+2<(m+2)k,且wa2∉A，w∈A⊆X*b，所以xym+2z=wa(m+1)k+2L.因此L不是(n,2)-语言. 下面证明L是指数为k1+1的左-(n,2)-语言. 对任意的u∈X*，v∈X*,设vk1+1∈L.

1)若vk1+1u=(vk1+1u1)u2，其中vk1+1u1∈A，u2∈(ak)+, 由于A是指数为k1的左-(n,2)-语言，故有vk1+3u1∈A.即vk1+3u=(vk1+3u1)u2∈A(ak)+=L.

2)若vk1+1u=(vk1-iv1)(v2viu)，其中0≤i≤k1，v=v1v2，v1，v2∈X*，vk1-iv1∈A ,v2viu∈(ak)+.我们考虑下列情形：

1)若i=0, 则vk1+1u=(vk1v1)(v2u) ，其中vk1v1∈A ，v2u∈(ak)+. 即vk1+2v1∈A.因此vk1+3u=(vk1+2v1)(v2u)∈A(ak)+.

2)若1≤i≤k1, 则因为v2viu∈(ak)+, 所以v=at，其中t≥1. 故v1和v2是a的方幂. 这与vk1-ivi∈A⊆X*b矛盾.

同理可证，若vk1+3u∈L 则vk1+1u∈L .因此L=A(ak)+是指数为k1+1的左-(n,2)-语言但不是(n,2)-语言.

[1]SHYRHJ.Freemonoidsandlanguage[M].Taiwan:HonMinBookCompany, 2001. 17-42.

[2]SHYRHJ,THIERRING.Left-noncountinglanguages[J].InternationalJournalofComputerandInformationSciences, 1975, 4(1): 95-102.

[3]SHYRHJ,THIERRING.Somepropertiesofthelanguages[J].TamkangJournalofMathematics, 1975, 6(2): 281-284.

[4]KARIL,THIERRING.Aperiodiclanguagesandgeneralization[J].WorldScientificSeriesofComputerScience, 2010, 43(11): 233-243.

[5]LIZZ.Languagespreservinghomomorphisms[D].Taiwan:Chung-YuanChristsanUniversity, 2001. 57-80.

[6]BRZOZOWSKIJA,CULIK.Classificationofnoncountingevents[J].JournalofComputerandSystemScience, 1971(5): 41-53.

[7]McNaughtonR,PAPERTS.Counter-freeautomata[M].Camberige:MITPress, 1971. 27-49.

[8]RESTIVOA.OnaquestionofMcNaughtonandPapert[J].InformationandControl, 1974, 25(1): 93-101.

[9]SHYRHJ,THIERRING.Power-separatingregularlanguages[J].MathematicalSystemTheory, 1974, 8(1): 90-95.

[10]BOOKRV.Formallanguagetheory:perspectivesandopenproblems[M].NewYork:AcademicPress, 1980. 118-136.

[11]LEUPILDP.Languagesgeneratedbyiteratedidempotencies[D].Tarragona:UniversitatRoviraIVirgili, 2006. 87-98.

[12]LOTHAIREM.Combinatoricsonwords[M].London:CambridgeUniversityPress, 1997. 98-106.

Some examples of left-(n,2) languages

LIU Li

(School of Mathematics and Computer Science, Yan’an University, Yan’an 716000, China)

Every (n,k)language is a le-ft-(n,k)-language. This paper gave some conditions foruv+andA(ak)+being a left-(n,2)-language.

left-(n,2)languages; primitive word; left-non-counting language

2016-08-15.

国家自然科学基金(11471007)；陕西省教育厅基金(16JK1860)

刘 莉(1985-)，女，讲师，研究方向：字，语言与自动机理论.

O152

A

1672-0946(2017)03-0340-03