P－n－右析取語言的相關性質

劉 莉

（延安大學數學與計算機科學學院，陜西延安716000）

P－n－右析取語言的相關性質

劉 莉

（延安大學數學與計算機科學學院，陜西延安716000）

主要研究了P－n－右析取語言的一些相關性質，給出了P－n－析取轄的定義，得出了P－n－析取轄是稠密語言等結論。

P－n－右析取語言；稠密語言；P－n－稠密

1 基本概念

設X是非空的字符集（有限或無限），我們稱X是字母表，X上的元素稱為字母，X上的有限字符串稱為X上的字，我們定義空字是不包含任何字母的字，用1表示空字，記X上的所有字的集合為X*，即

其中X0＝1，

令S是一個非空集合，S×S的子集ρ稱為S上的二元關系。若ρ滿足下面的條件：

（1）xρx，（?x∈S）

（2）xρy?yρx，（?x，y∈S）

（3）xρy，yρz?xρz，（?x，y，z∈S）

則稱ρ是S上的等價關系。

等價關系ρ稱為右同余（左同余），若滿足aρb?acρbc（aρb?caρcb），?c∈S。

若ρ既是右同余又是左同余，稱ρ是同余關系。

設X是一個有限字母表，定義X*上的全序如下：?x，y∈X*，若lg（x）＜lg（y）。則x＜y；若lg（x）＝lg（y）＝n，?n≥1，則定義＜是Xn上的字典序，例如，設X＝｛a，b，c｝，則X*＝｛1＜a＜b＜c＜aa＜ab＜ac＜ba＜bb＜…｝。

定義1［1］設L?X*，定義X*上的等價關系Pn，L：

其中u，v∈X*，uy≠1，vy≠1。則Pn，L是X*上的右同余關系。

定義2［2］設L?X*，稱L是P－n－右析取語言：如果Pn，L是X*上的恒等關系。

定義3［3］稱L是P－n－稠密的，如果滿足：?u∈X*，?x，y∈X*，?n，s.t.x（uy）n∈L。

定義4［3］稱L是P－n－離散的，如果滿足

引理1［4］若um＝vn，m，n≥1，則u，v是同一字的方冪。

引理2［5］令L?X＋，則下列條件等價：

（1）L是P－n－稠密語言；

（2）L（k）是P－n－稠密語言；

引理3［5］一個語言是P－n－稠密的當且僅當它包含有一個P－n－右析取語言。

2 主要結論

定義語言D?X*稱為P－n－析取轄。如果D滿足對任意L?X*，若Pn，L在D上是恒等關系，則L是P－n－右析取語言。

命題1設X是有限字母表，D?X*，若D是P－n－析取轄，則D是稠密語言。

證明：令X*＝｛u1＜u2＜u3…＜un＜…｝，我們利用P－n－右析取轄D作語言。

L＝｛x′｜x∈D/｛1｝｝，

這里＃x就是x在全序X*中的位置。顯然，x與x′是一一對應的。由于lg（x）＜＃x，所以x′是本原字。即L?Q。

令L（k）＝｛uk｜u∈L，k∈N｝，

用染色序列對P進行著色,實際上是對m(2n+1)+2n-1條邊進行著色,而圖4中色集合的個數有個,根據上述染色算法,當k是奇數時,有當k是偶數時,有因此恒成立,此時求得最小的整數k滿足?。

下證Pn，L（k）是D上的恒等關系。

首先，令x，y∈D/｛1｝，x≠y，不妨設＃x＞＃y，＃x＝n。

（1）若x?X*a，則存在空字1和an使得

1（xan）k＝（xan）k∈L（k）

假設 1（yan）k＝（yan）k∈L（k），

由L（k）的定義知?z∈D/｛1｝，＃z＝m使得（yan）k＝（z′）k。

①若z?X*a，則（yan）k＝（zam）k。

令lg（yan）＝p，lg（zam）＝q，則（yan）q＝（zam）p。

由引理1知yan和zam是同一字的方冪。又yan，zam∈L?Q，故yan＝zam。

若lg（y）＜lg（z），則?z1∈X＋使得z＝yz1，故an＝z1am，但z?X*a，z1是z的后綴，從而z1?X*a，即z1不是以a結尾，這與an＝z1am矛盾。

若lg（y）＞lg（z），則y＝zal其中l＋n＝m，l＞0。由y＝zal知＃y＞＃z，又＃x＞＃y，＃x＝n，＃z＝m故有n＞m，這與l＋n＝m矛盾。

②若z∈X*a，則（yan）k＝（zbm）k從而yan＝zbm，但a≠b 故 yan≠zbm矛盾。

因此，假設不成立。故（yan）k?L（k）。

即x與y沒有（Pn，L（k））關系。

（2）若x∈X*a，則類似可以證明存在空字1和bn使得1（xbn）k＝（xbn）k∈L（k）但1（ybn）k＝（ybn）k?L（k）。從而即x與y沒有（Pn，L（k）關系。

其次，對?x∈D/｛1｝，不妨設x＝x1a，x1∈X*，＃x＝n則存在空字1和bn使得1（xbn）k＝（xbn）k∈L（k），1（1bn）k＝1（1bn）k＝?L（k）。

從而即x與1沒有（Pn，L（k））關系。

綜上?x，y∈D，x≠y，x與y沒有（Pn，L（k））關系。

又D是P－n－右析取轄，故L（k）是P－n－右析取語言。

由引理2知L是P－n－稠密語言。

假設D不是稠密語言。則?w∈X＋，

由于L是P－n－稠密語言，從而?wk∈X＋，其中w與k的末尾字母互異。?u，v∈X*，?n，s.t.u（wkv）n∈L，由L得作法知uwv1∈D，其中v1是kv的前綴，這與X*wX*∩D＝?矛盾。

因此D是稠密語言。

命題2設L?X*，若L是P－n－右析取語言，則L′＝L∩X*/（X＋）（k），其中k∈N，是P－n－右析取語言。也就是說P－n－右析取語言中所有最終周期字所作的集合還是P－n－右析取語言。

證明：對于?u，v∈X*，u≠v，由于L是P－n－右析取語言。所以u和v沒有Pn，L關系。即?x，y∈X*，n≥2，有x（uy）n∈L，x（vy）n?L或x（vy）n∈L，x（uy）n?L。

不妨設x（uy）n∈L，x（vy）n?L，

又 L′＝L∩X*（X＋）（k），故

即u和v沒有Pn，L′關系。

由u，v的任意性知L′是P－n－右析取語言。

命題3設L1?X*是P－n－右析取語言，L2?X*/X*（X＋）（k），則L＝L1∪L2是P－n－右析取語言。

證明：對于?u，v∈X*，u≠v，由于L1是P－n－右析取語言。故u和v沒有Pn，L1關系。即?x，y∈X*，n≥2，有

不妨設x（uy）n∈L1，x（vy）n?L1，

則x（uy）n∈L，x（vy）n∈X*（X＋）（k），故

即x（vy）n?L2，x（vy）n?L。

所以u和v沒有Pn，L關系。

由u，v的任意性知L是P－n－右析取語言。

P－n－右析取語言與任一非最終周期字的并還是P－n－右析取語言，也就是說X*中不存在極大的P－n－右析取語言。

命題4設L?X*是P－n－右析取語言，若L＝L1∪L2且L1∩L2＝?，則下面兩式中至少有一個成立：（1）L1和L2中至少有一個是P－n－右析取語言；

（2）L1和L2都包含P－n－右析取語言。

證明：假設（2）不成立，即L1和L2中至少有一個不包含P－n－右析取語言。不妨設L1不包含P－n－右析取語言。由引理3可知，L1不是P－n－稠密語言。則?w∈X*，?x，y∈X*，?n∈N 有x（wy）n?L1，（*）。

下證?u，v∈X*，若u≡v（Pn，L2），則u＝v。

事實上，由同余關系的性質有

O159

A

1004－602X（2014）03－0024－03

10.13876/J.cnki.ydnse.2014.03.024

2014-06-20

劉 莉（1985—），女，陜西延安人，延安大學助教。