(n,k)-語言及左-(n,k)-語言的一些性質

劉 莉

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

石輝然先生于1975年開始對不可數語言(即(n,1)-語言)和左不可數語言(即左-(n,1)-語言)進行了大量研究，取得了許多重大成果[1-3]，并且提出了(n,k)-語言的定義，對其做了簡單的研究[4]。在前人研究的基礎上，本文對(n,k)-語言和左-(n,k)-語言進行了初步研究，并得到了一些相關性質[5]。

1 預備知識

設X是非空的字母集合，稱為字母表，X上的字符串稱為字，不含任何字母的字稱為空字，用1表示。所有字的集合用X*表示，設X+=X*/{1}。對任意字w∈X+，lg(w)表示w中所含字母的個數，稱為w的長度，并且規定lg(1)=0。設S是半群(幺半群)，A和B是S的子集，定義A和B的連接運算AB={xy|x∈A,y∈B}。設A?X+是一非空語言，若A∩AX+=?(A∩X+A=?)，則稱A是前綴碼(后綴碼)。以下符號將在文中用到，

l(A)={g∈A|gx?A,?x∈X+,g=yz?y?A,?z∈X+}；

r(A)={g∈A|xg?A,?x∈X+,g=zy?y?A,?z∈X+}；b(A)=l(A)∩r(A)。

若g∈l(A)，(g∈r(A)，g∈b(A)，則稱g是A的左奇異字(右奇異字，雙奇異字)。若l(A)≠?，(r(A)≠?，b(A)≠?)則稱A是左奇異語言(右奇異語言，雙奇異語言)。設L∈X+，對任意的x,z∈X*，y∈X+，若xynz∈L?yn+kz∈L，其中n≥0,k≥1，則稱L是(n,k)-語言；若ynz∈L?yn+kz∈L，則稱L是左-(n,k)-語言。其中n叫做L的階。若k=1，則稱(n,1)-語言為不可數語言，關于不可數(n,k)-語言和(n,k)-語言的性質相關文獻有初步研究[6-13]。

2 主要結論

命題1 設A,B?X+，若A,B是左-(n,k)-語言，則AB是左-(n,k)-語言。(左-(n,k)-語言在連接運算下是封閉的)。

證明設A,B分別是階為n1和n2的左-(n,k)-語言，其中n1,n2≥0,k≥1。下證AB是階為n1+n2的左-(n,k)-語言。設yn1+n2z∈AB，其中任意的y∈X+，z∈X*。下面我們將證明yn1+n2+kz∈AB。考慮以下幾種情形：

(1)若yn1+n2z=(yn1+n2z1)z2，其中yn1+n2z1∈A，z2∈B，z=z1z2，z1,z2∈X*。因為A是階為n1的左-(n,k)-語言，所以yn1+n2+kz1∈A。故有yn1+n2+kz=(yn1+n2+k)z2∈AB。

(2)若yn1+n2z=(yiy1)(y2yyn1+n2-i-1z)，其中yiy1∈A，y2yn1+n2-i-1z∈B，y=y1y2，y1,y2∈X*。考慮以下兩種情形：

①若i≥n1，因為A是階為n1的左-(n,k)-語言且yiy1∈A，所以yi+ky1∈A。故有

yn1+n2+kz=yk(yiy1)(y2yn1+n2-i-1z)=

(yi+ky1)(y2yyn1+n2-i-1z)∈AB。

②若i

(y2,y1)n1+n2-i-1y2z=y2yn1+n2-i-1z∈B，

所以(y2y1)n1+n2-i-1+ky2z=B。

故有yn1+n2+kz=yi+1yn1+n2-i-1+kz=

yiy1y2(y1y2)n1+n2-i-1+kz=

(yiy1)[(y2y1]n1+n2-i-1+ky2z]∈AB，

因此AB是階為n1+n2的左-(n,k)-語言。

同理可證，若yn1+n2+kz∈AB，則yn1+n2z∈AB。即AB是左-(n,k)-語言。

命題2 左-(n,k)-語言在連接運算、并集、交集、補集運算下是封閉的。

證明設A和B分別是階為n1和n2的左-(n,k)-語言。

(1)由命題1知左-(n,k)-語言在連接運算下是封閉的。

(2)設ynz∈A∪B，其中y∈X+，z∈X*，n=max{n1,n2}。則ynz∈A或ynz∈B。不失一般性，設ynz∈A，因為A是階為n1的左-(n,k)-語言，所以yn+kz∈A?A∪B。同理可證，若yn+kz∈A∪B，則ynz∈A∪B。因此左-(n,k)-語言在并集運算下是封閉的。

(3)設ynz∈A∩B，其中y∈X+，z∈X*，n=max{n1,n2}，則yn+kz∈A∩B。同理可證，若yn+kz∈A∩B，則ynz∈A∩B。因此左-(n,k)-語言在交集運算下是封閉的。

(4)設yn1z∈Ac，其中y∈X+，z∈X*，則yn1z?A。因為A是階為n1的左-(n,k)-語言，所以yn1+kz?A，即yn1+kz∈A。同理可證，若yn1+kz∈Ac，則yn1z∈Ac。因此左-(n,k)-語言在補集運算下是封閉的。

命題3 設A和B是非空(n,k)-語言，則

(1)若AB是(n,k)-語言(左-(n,k)-語言)且A是左奇異(n,k)-語言，則B是(n,k)-語言(左-(n,k)-語言)；

(2)若AB是(n,k)-語言(左-(n,k)-語言)且B是右奇異(n,k)-語言，則A是(n,k)-語言(左-(n,k)-語言)。

證明(1)設AB是(n,k)-語言。若A={1}或B={1}，顯然B是(n,k)-語言。若A≠{1}且B≠{1}。因為A是左奇異(n,k)-語言，所以存在g∈l(A)?A。設xynz∈B，其中x,z∈X*，y∈X+，則gxynz∈AB。又AB是(n,k)-語言，故有gxyn+kz∈AB。即存在u∈A，v∈B使得gxyn+kz=uv。

①若lg(g)=lg(u)，則xyn+kz=v∈B。

②若lg(g)>lg(u)，則存在x1∈X+使得g=ux1。這與g∈l(A)矛盾。

③若lg(g)

因此，xyn+kz∈B，同理可證，若xyn+k∈B，則xynz∈B，即B是(n,k)-語言。設x=1，則可證AB是左-(n,k)-語言的情況。

同(1)可證(2)成立。

推論1 設A和B是非空語言，則

(1)若AB是(n,k)-語言(左-(n,k)-語言)且A是前綴碼，則B是(n,k)-語言(左-(n,k)-語言)。

(2)若AB是(n,k)-語言(左-(n,k)-語言)且B是后綴碼，則A是(n,k)-語言(左-(n,k)-語言)。

證明(1)因為A是前綴碼，所以A左奇異(n,k)-語言，又AB是(n,k)-語言(左-(n,k)-語言)，由命題3易知B是(n,k)-語言(左-(n,k)-語言)。

(2)因為后綴碼是右奇異語言，同理可證若AB是(n,k)-語言(左-(n,k)-語言)且B是后綴碼，則A是(n,k)-語言(左-(n,k)-語言)。

推論2 設A是前綴碼或后綴碼，則A2是(n,k)-語言(左-(n,k)-語言)當且僅當A是(n,k)-語言(左-(n,k)-語言)。

證明(?)若A是前綴碼或后綴碼并且A是(n,k)-語言(左-(n,k)-語言)。則由命題3易知A2是(n,k)-語言(左-(n,k)-語言)。

(?)若A2是(n,k)-語言(左-(n,k)-語言)，A是前綴碼或后綴碼，則由命題3易知A是(n,k)-語言(左-(n,k)-語言)。