• 
    

    
    

      99热精品在线国产_美女午夜性视频免费_国产精品国产高清国产av_av欧美777_自拍偷自拍亚洲精品老妇_亚洲熟女精品中文字幕_www日本黄色视频网_国产精品野战在线观看 ?

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

      2020-12-16 21:43:52
      延安大學學報(自然科學版) 2020年1期
      關(guān)鍵詞:易知后綴字母

      劉 莉

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

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

      1 預(yù)備知識

      設(shè)X是非空的字母集合,稱為字母表,X上的字符串稱為字,不含任何字母的字稱為空字,用1表示。所有字的集合用X*表示,設(shè)X+=X*/{1}。對任意字w∈X+,lg(w)表示w中所含字母的個數(shù),稱為w的長度,并且規(guī)定lg(1)=0。設(shè)S是半群(幺半群),A和B是S的子集,定義A和B的連接運算AB={xy|x∈A,y∈B}。設(shè)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是左奇異語言(右奇異語言,雙奇異語言)。設(shè)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)-語言為不可數(shù)語言,關(guān)于不可數(shù)(n,k)-語言和(n,k)-語言的性質(zhì)相關(guān)文獻有初步研究[6-13]。

      2 主要結(jié)論

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

      證明設(shè)A,B分別是階為n1和n2的左-(n,k)-語言,其中n1,n2≥0,k≥1。下證AB是階為n1+n2的左-(n,k)-語言。設(shè)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)-語言在連接運算、并集、交集、補集運算下是封閉的。

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

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

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

      (3)設(shè)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)設(shè)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 設(shè)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)設(shè)AB是(n,k)-語言。若A={1}或B={1},顯然B是(n,k)-語言。若A≠{1}且B≠{1}。因為A是左奇異(n,k)-語言,所以存在g∈l(A)?A。設(shè)xynz∈B,其中x,z∈X*,y∈X+,則gxynz∈AB。又AB是(n,k)-語言,故有g(shù)xyn+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)-語言。設(shè)x=1,則可證AB是左-(n,k)-語言的情況。

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

      推論1 設(shè)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 設(shè)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)-語言)。

      猜你喜歡
      易知后綴字母
      巧解一道代數(shù)求值題
      序列(12+Q)(22+Q)…(n2+Q)中的完全平方數(shù)
      三角形中巧求值
      緩存:從字母B到字母Z
      從《曲律易知》看民國初年曲學理論的轉(zhuǎn)型
      戲曲研究(2017年3期)2018-01-23 02:50:52
      字母派對
      河北霸州方言后綴“乎”的研究
      TalKaholic話癆
      說“迪烈子”——關(guān)于遼金元時期族名后綴問題
      一種基于后綴排序快速實現(xiàn)Burrows-Wheeler變換的方法
      新源县| 望城县| 新余市| 安陆市| 镇赉县| 肥东县| 寻乌县| 梅州市| 柞水县| 平乐县| 南宫市| 屯留县| 扎鲁特旗| 朝阳县| 河津市| 涿州市| 称多县| 尼勒克县| 奇台县| 维西| 刚察县| 元阳县| 东莞市| 嘉定区| 东阿县| 博野县| 阿克陶县| 南康市| 南岸区| 仪陇县| 祁阳县| 庆云县| 嵊州市| 湟源县| 喀喇沁旗| 资阳市| 阿合奇县| 赤峰市| 宁远县| 桂林市| 镇坪县|