(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)-语言)。