近世代数论文(5)

同样的性质在讨论了同构的概念之后,自然就有一个问题:字母表上互不同构的各类语言的基数是什么?

语言同构的概念、语言同构的概念、性质及简单应用举例

∑1是字母表；f是从∑到∑1定义1设L是字母表∑上的语言，

的一个双射函数。将f扩充为从∑到∑1的双射函数，满足：

(1)f(∈)=∈

(2)f(xa)=f(x)f(a)

x∈∑* ，a∈∑，f（x）∈∑1，f(a)∈∑1*这里。令：L1=f(L)=∪f(x)

x∈L则称

f为从语言L到L1的同构映射，成L和L1同构。

定理1设f为从语言L到L1的同构映射，则对任一x∈L;x=f(x)。证明对任一x∈L，设x=a1a2...an，由于f是从L到L1的同构映射，

故f(x)=f(a1)f(a2)...f(an)，应为f(a1),f(a2),...,f(an)的长度都是1，

故x=a1+a2+...+an=f(a1)+f(a2)+...+f(an)=f(x)

从定理1，立即我们可知∑

都是互不同构的。

定理2设语言L1和L2同构，则L2和L1也同构。

**L1和L2同构证明设∑1到∑2是字母表且L1 ∑1,L2 ∑2， a,aa,aaa,...,aa...a} ,...={a}的语言{}{}{ n

由定义1知，有从∑1到∑2的双射函数f，且扩充为从∑1到∑2的**双射函数后满足条件（1）和（2），f(L1)=L2由于f是双射函数，所

以，f 1存在且f 1是从∑2到∑1的双射函数；f 1(∑2)=∑1，同时****满足条件（1），（2）；等式f(L2)= 1

y∈L2∪nf 1(y)=L1成立。故L1和L2同构。