代数码

英文

algebra code

简介

近代半群理论中的重要概念.设X是一有限非空集合(称为字母表).X上的自由幺半群X^*的元素(子集)称为X的字(或语言).X上的一个语言C，若对任意x₁，x₂，…，x_n，y₁，y₂，…，y_m∈C，m，n≥1有

x_i＝y_jm=n

且x_i＝y_i (i=1，2，…，n)，则称C为X上的一个(代数)码.在涉及以上诸概念时，X也未必常假定有限.语言的概念最初于20世纪50年代在计算机科学的形式语言中由乔姆斯基(Chomsky，N.)首先引入.码的概念来自20世纪50年代仙农(Shannon，C.E.)的信息论，是应通讯上对译文惟一性的要求建立起来的.语言理论和码论的中心课题是它的代数和组合结构以及二者的联系.它们涉及字的组合，研究方法通常是组合的与代数的并举，它们已构成半群近代理论的一个重要组成部分，与自动机理论和计算机科学有密切联系.艾伦伯格(Eilenberg，S.)的《自动机，语言与机器》(卷A，卷B)，贝斯特尔(Berstel，J.)与佩林(Perrin，D.)的《码论》，劳瑟尔(Lothaire，M.)的《字的组合》以及石辉然的《自由幺半群与语言》等都是这方面的专著.