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

劉 莉

(延安大學 數(shù)學與計算機科學學院，陜西 延安 716000)

?

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

劉 莉

(延安大學 數(shù)學與計算機科學學院，陜西 延安 716000)

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

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

1 預備知識

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

設X是非空有限字母表，X上的有限字符串稱為字，不含任何字母的字稱為空字，用1表示. 所有字的集合用X*表示. 設X+=X*{1}.X*的任一非空子集稱為語言.設L是X*上的語言，對任意的x,y,z∈X*，若存在正整數(shù)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)-語言稱為不可數(shù)語言. 如果一個字不能表示成任何非空字的方冪，則稱這個字是本原字，所有本原字的集合用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.

本文中用到的定義但未出現(xiàn)的可參考文獻[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. 下面假設存在整數(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. 因為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及整數(shù)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+. 則存在整數(shù)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的前l(fā)g(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是指數(shù)為k1的左-(n,2)-語言，L=A(ak)+.對任意的整數(shù)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是指數(shù)為k1+1的左-(n,2)-語言. 對任意的u∈X*，v∈X*,設vk1+1∈L.

1)若vk1+1u=(vk1+1u1)u2，其中vk1+1u1∈A，u2∈(ak)+, 由于A是指數(shù)為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)+是指數(shù)為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