h－1保持各种独立语言的条件

刘 莉

（延安大学数学与计算机科学学院，陕西延安716000）

DOI：10.3969／J.ISSN.1004－602X.2014.02.016

h－1保持各种独立语言的条件

刘 莉

（延安大学数学与计算机科学学院，陕西延安716000）

设h：X*→X*是同态映射，主要研究了h－1保持各种独立语言的条件。得到了h－1保持ρc－独立语言，ρd－独立语言以及ρb－独立语言的充分必要条件都是h－1（1）＝｛1｝。此外，证明了若h：X*→X*是同态映射，则h－1保持ρe－独立语言。

同态映射；ρc－独立语言；ρe－独立语言；ρd－独立语言；ρb－独立语言

1 基本概念

令X是至少含有两个元素的有限字母表。X上有限字符串称为字，不含有任何字母的字称为空字，记作1。所有有限字和空字1的集合记为X*。记X＋＝X*＼｛1｝。

设S是一个非空集合，S×S的子集ρ称为S上的二元关系，若ρ满足下面的条件：

（1）（∀x∈S）xρx

（2）（∀x，y∈S）xρy⇒yρx

（3）（∀x，y，z∈S）xρy，yρz⇒xρz

则称ρ是S上的等价关系，等价关系ρ称为右同余（左同余），若满足aρb⇒acρbc（aρb⇒caρcb）（∀c∈S）。若ρ既是左同余又是右同余，则称ρ是同余关系。

设w，v∈X*我们定义以下关系：

（1）w≤cv当且仅当存在x∈X*使得v＝xw＝wx；

（2）w≤ev当且仅当存在n≥1使得v＝wn；

（3）w≤bv当且仅当存在x，y∈X*使得v＝xwy；

（4）w≤dv当且仅当存在x，y∈X*使得v＝wx＝yw。

设H⊆X*，对任意的u，v∈H，若u≤xv⇒u＝v则称H是关于≤x的独立语言，有时记作ρx－独立语言。

设h是X*到X*的映射，若对任意的x，y∈X*都有h（xy）＝h（x）h（y）成立，则称h是X*上的同态映射，h－1表示由h（X*）到X*的一个对应关系。h－1（a）表示由a的原像组成的集合。设是一个语言集合，若任意的L∈，h－1（L）∈，则称h－1保持L语言。

2 主要结论

命题1设h：X*→X*是同态映射，则h－1保持ρc－独立语言的充分必要条件是h－1（1）＝｛1｝。

证明：（⇒）假设h－1（1）≠｛1｝，则存在x∈X＋，使得x∈h－1（1），则有｛1，x｝⊆h－1（1）。而x＝1x＝x1，即1≤cx。因此h－1（1）不是ρc－独立语言，而｛1｝是ρc－独立语言，这与h－1保持ρc-独立语言矛盾，故h－1（1）＝｛1｝。

（⇐）设L⊆X*是ρc－独立语言，若h－1（L）不是ρc－独立语言，则存在w，v∈h－1（L），w≠v，使得w≤cv。即存在x∈X＋，使得v＝xw＝wx。则h（v）＝h（x）h（w）＝h（w）h（x）。由w，v∈h－1（L），知存在z，y∈L，使得h（x）＝z，h（w）＝y，即有z＝h（x）y＝yh（x），又因为L是ρc－独立语言，故h（x）＝1。又h－1＝｛1｝，所以x＝1。这与x∈X＋矛盾。即有h－1（L）是ρc－独立语言。

命题2设h：X*→X*是同态映射，则h－1保持ρe－独立语言。

证明：设L⊆X*是ρe－独立语言，若h－1（L）不是ρe－独立语言，则存在w，v∈h－1（L），n≥2，使得w＝vn，即有h（w）＝h（vn）＝［h（v）］n，即存在x，y∈L，使得h（w）＝x，h（v）＝y，故x＝yn。这与L是ρe－独立语言矛盾。因此h－1（L）是ρe－独立语言。

命题3设h：X*→X*是同态映射，则h－1保持ρd－独立语言的充分必要条件是h－1（1）＝｛1｝。

证明：（⇒）假设h－1（1）≠｛1｝，则存在x∈X＋，使得x∈h－1（1），则x＝1x＝x1，即x≤d1。因此h－1（1）不是ρd－独立语言，而｛1｝是ρd－独立语言，这与h－1保持ρd－独立语言矛盾。故h－1（1）＝｛1｝。

（⇐）设L⊆X*是ρd－独立语言，若h－1（L）不是ρd－独立语言，则存在u，v∈h－1（L），u≠v，使得u≤dv。即存在x，y∈X*，使得u＝vx＝yv。则h（u）＝h（v）h（x）＝h（y）h（v）。由u，v∈h－1（L），知存在u1，v1∈L，使得h（u）＝u1，h（v）＝v1，即有u1＝v1h（x）＝h（y）v1，又因为L是ρd－独立语言，故h（x）＝h（y）＝1。又h－1（1）＝｛1｝，所以x＝y＝1。这与u≠v矛盾。即有h－1（L）是ρd－独立语言。

命题4设h：X*→X*是同态映射，则h－1保持ρb－独立语言的充分必要条件是h－1（1）＝｛1｝。

证明：（⇒）假设h－1（1）≠｛1｝，则存在x∈X＋，使得x∈h－1（1），故x＝1x＝x1，即1≤bx。因此h－1（1）不是ρb－独立语言，而｛1｝是ρb－独立语言，这与h－1保持ρb－独立语言矛盾。故h－1（1）＝｛1｝。

（⇐）设L⊆X*是ρb－独立语言，设v，w∈h－1（L），v＝xwy，x，y∈X*，则h（v）＝h（x）h（w）h（y），即存在v′，w′∈L，使得h（v）＝v′，h（w）＝w′，故v′＝h（x）w′h（y），因为L是ρb－独立语言，故h（x）＝h（y）＝1。又h－1（1）＝｛1｝。故x＝y＝1，即v＝w。所以h－1（L）是ρb－独立语言。

［1］Shyr H J.Free Monoids and Language［M］.Taiwan：Hon Min Book Company，2001.

［2］Chunhua Cao，Di Yang.Noted on Homomorphisms Which Preserve Certain Families of Language［J］.Southeast Asian Bulletin of Mathematics，2005（29）：415－422.

［3］Ito M，Shyr H J.ρ－Languages and p－Representations［J］. Cybern.EIK，1990，（4）213－228.

［4］Yeh Y T，Yu SS.The disjunctivities ofω－languages［J］. Discrete Applied Mathematics，2003，（127）627－641.

［5］Shyr H J.Disjunctive languages on a freemonoid［J］.Information and Control，1977（34）：123－129.

［6］Shyr H J，Thierrin G.Disjunctive languages and codes［J］. Fundamentals of Computation Theory，1977（56）：171－176.

［7］Guo Y Q，Shyr H J，Thierrin G.F－disjunctive languages［J］.International Journal of Computer Mathematics，1986（18）：219－237.

［责任编辑 贺小林］

Conditions of h－1Preserver Some Independent Languages

LIU LI
（College of Mathematics and Computer Science，Yanan University，Yanan 716000，China）

Let h：X*→X*be a homomorphism.This paper deals with the conditions of h－1preserver some independent languages.We show that h－1preserversρc－independent languages，ρd－independent languages andρdindependent languages if and only if h－1（1）＝｛1｝.Furthermore，we proof that if h：X*→X*is a homomorphism，then h－1preserversρe－independent languages.

homomorphism；ρc－independent languages；ρe－independent languages；ρd－independent languages；ρb－independent languages

O159

A

1004－602X（2014）02－0016－02

2013 12 06

刘 莉（1985—），女，陕西延安人，延安大学助教。