劉 莉

(延安大學(xué) 數(shù)學(xué)與計(jì)算機(jī)科學(xué)學(xué)院，陜西 延安 716000)

?

左-(n,2)語(yǔ)言的一些例子

劉 莉

(延安大學(xué) 數(shù)學(xué)與計(jì)算機(jī)科學(xué)學(xué)院，陜西 延安 716000)

每個(gè)(n,k)-語(yǔ)言都是左-(n,k)-語(yǔ)言，給出了uv+以及A(ak)+是左-(n,2)-語(yǔ)言但不是(n,2)-語(yǔ)言的條件.

左-(n,2)語(yǔ)言；本原字；左不可數(shù)語(yǔ)言

1 預(yù)備知識(shí)

關(guān)于不可數(shù)語(yǔ)言即(n,1)-語(yǔ)言的性質(zhì)，人們已經(jīng)做了大量的研究并得到了十分有價(jià)值的結(jié)論(見(jiàn)文獻(xiàn)[1-9])，而不可數(shù)語(yǔ)言無(wú)需考慮它的指數(shù).石輝然在文獻(xiàn)[3]中證明了(n,k)語(yǔ)言的一些性質(zhì)，本文在此基礎(chǔ)上做了進(jìn)一步研究，構(gòu)造了一些左-(n,2)-語(yǔ)言.

設(shè)X是非空有限字母表，X上的有限字符串稱(chēng)為字，不含任何字母的字稱(chēng)為空字，用1表示. 所有字的集合用X*表示. 設(shè)X+=X*{1}.X*的任一非空子集稱(chēng)為語(yǔ)言.設(shè)L是X*上的語(yǔ)言，對(duì)任意的x,y,z∈X*，若存在正整數(shù)n，k≥1使得xynz∈L當(dāng)且僅當(dāng)xyn+kz∈L，則稱(chēng)L是(n,k)語(yǔ)言.若存在n≥0,k≥1,使得ynz∈L當(dāng)且僅當(dāng)yn+kz∈L，則稱(chēng)L是左-(n,k)-語(yǔ)言.[3].由定義易知，每個(gè)(n,k)-語(yǔ)言都是左-(n,k)-語(yǔ)言.若k=1，則(n,k)-語(yǔ)言稱(chēng)為不可數(shù)語(yǔ)言. 如果一個(gè)字不能表示成任何非空字的方冪，則稱(chēng)這個(gè)字是本原字，所有本原字的集合用Q表示. 以下引理將在本文中用到.

引理1[3]設(shè)u∈X*,v∈X+，則uv+是(n,2)- 語(yǔ)言當(dāng)且僅當(dāng)對(duì)任意的f∈Q，f∈Q，k≥3都有v≠fk.

引理2[7]若um,vn的前 lg(u)+lg(v)長(zhǎng)度的子字相同，這里m,n≥1，則u和v可以表示成同一個(gè)本原字的方冪.

引理3[1]設(shè)uv=fi，其中u,v∈X+，f∈Q,i≥1.則存在g∈Q使得vu=gi.

本文中用到的定義但未出現(xiàn)的可參考文獻(xiàn)[1，10-12].

2 主要結(jié)論

命題 2.1 設(shè)u,v∈X+，則uv+是左-(n,2)-語(yǔ)言但不是(n,2)-語(yǔ)言的充分必要條件是存在本原字w及k≥3使得v=wk且對(duì)任意的m≥1，都不是wm的后綴.

證明. (?)設(shè)uv+是左-(n,2)-語(yǔ)言但不是(n,2)-語(yǔ)言. 假設(shè)對(duì)任意的w∈Q，k≥3都有v≠wk，則由引理1.1 知uv+是(n,2)-語(yǔ)言. 矛盾. 故存在本原字w及k≥3使得v=wk. 下面假設(shè)存在整數(shù)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. 因?yàn)閙≥1,k≥3, 所以m+(t+1)k

2)若u=w1wh，其中0≤h≤m，w=w2w1，w1,w2∈X+.因?yàn)閣2w1=w∈Q，所以w1w2∈Q.對(duì)任意的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. 因?yàn)閗≥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)-語(yǔ)言. 矛盾.綜上，若uv+是左-(n,2)-語(yǔ)言但不是(n,2)-語(yǔ)言,則存在本原字w及k≥3使得v=wk且對(duì)任意的m≥1，u都不是wm的后綴.

(?)假設(shè)存在本原字w及整數(shù)k≥3使得v=wk且對(duì)任意的m≥1，u都不是wm的后綴.

由引理1知wv+不是(n,2)-語(yǔ)言.下面證明uv+是左-(n,2)-語(yǔ)言. 設(shè)r=lg(u)+lg(w) ，i>3r.假設(shè)存在y∈X*， 使得yiz∈uv+. 則存在整數(shù)j≥1 使得yiz=uvj=uwkj.設(shè)yr=uwi1w3，其中i1≥1，w=w3w4，w3,w4∈X*且yi-rz=w4wkj-i1-1. 即有yi-rz=w4wkj-i1-1w4. 因?yàn)閕-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的前l(fā)g(y)+lg(w3w4)長(zhǎng)度的部分相同，由引理1.2知y和w4w3是同一本原字的方冪. 因?yàn)閣3w4=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.這與對(duì)任意的m≥1，u都不是wm的后綴矛盾. 若t′r-i1-1≤-1, 即i1+1-t′r≥1，且w4=uwi1+1-t′r，w=w3w4.矛盾. 因此對(duì)任意的y∈X+,z∈X*,i>3r，都有yizuv+. 故uv+是左-(n,2)-語(yǔ)言.

推論1 設(shè)u∈X*,v∈X+. 則uv+是左-(n,2)-語(yǔ)言當(dāng)且僅當(dāng)存在本原字w使得以下條件成立：

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

2)v=wi，其中i≥3且對(duì)任意m≥1，u不是wm的后綴.

命題1 設(shè)A是左-(n,2)-語(yǔ)言且A?X*b，其中b∈X，|X|≥2.則對(duì)任意的a∈X，a≠b，k≥3，A(ak)+是左-(n,2)-語(yǔ)言但不是(n,2)-語(yǔ)言.

證明： 設(shè)A是指數(shù)為k1的左-(n,2)-語(yǔ)言，L=A(ak)+.對(duì)任意的整數(shù)m≥0，w∈A，取x=wa(m+1)(k-1)，y=a，z=a.則xymz=wa(m+1)k∈L.因?yàn)?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)-語(yǔ)言. 下面證明L是指數(shù)為k1+1的左-(n,2)-語(yǔ)言. 對(duì)任意的u∈X*，v∈X*,設(shè)vk1+1∈L.

1)若vk1+1u=(vk1+1u1)u2，其中vk1+1u1∈A，u2∈(ak)+, 由于A是指數(shù)為k1的左-(n,2)-語(yǔ)言，故有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, 則因?yàn)関2viu∈(ak)+, 所以v=at，其中t≥1. 故v1和v2是a的方冪. 這與vk1-ivi∈A?X*b矛盾.

同理可證，若vk1+3u∈L 則vk1+1u∈L .因此L=A(ak)+是指數(shù)為k1+1的左-(n,2)-語(yǔ)言但不是(n,2)-語(yǔ)言.

[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.

國(guó)家自然科學(xué)基金(11471007)；陜西省教育廳基金(16JK1860)

劉 莉(1985-)，女，講師，研究方向：字，語(yǔ)言與自動(dòng)機(jī)理論.

O152

A

1672-0946(2017)03-0340-03