自由幺半群
此条目没有列出任何参考或来源。 (2019年3月13日) |
在抽象代数里,于一集合A上的自由幺半群是指一幺半群,其元素都是由A内零个或多个元素以串接之二元运算形成的有限序列(或字符串)。通常标记为A*。其单位元为空字元串,标记为ε 或 λ。在A上的自由半群则指是A*内的子半群,其包含除了空字串外的所有元素。通常标记为A+。
更一般地,一抽象幺半群(半群)S被称做是自由的,若其与某一集合上的自由幺半群(半群)同构。
如其名称所述,自由幺半群(半群)为满足定义了自由对象的泛性质的对象,在幺半群(半群)的范畴里。它允许每一个幺半群(半群)都会是某一自由幺半群(半群)的同态映像。研究半群为自由半群的映像的学科称做组合半群理论。
自由生成元和秩
集合A的元素称为A*和A+是自由生成元。更一般地讲,若S是一抽象自由幺半群(半群),则有一集合含有映射至与A*(A+)同态的单字母集合的元素,此集合称为S的“自由生成元集合”。
每一自由幺半群(半群)S会有一个且只有一个自由生成元集合,其势则称做S的“秩”。
两个自由幺半群(半群)同构当且仅当它们拥有相同的秩。而事实上,自由幺半群(半群)S的每一生成元集合都会包含其自由生成元。这使得一个自由幺半群(半群)会是有限生成的当且仅当它的秩是有限个的。
例子
自然数(包括零)在加法下的幺半群(N,+)是一有单一产生元(即其秩为一)的自由幺半群。它唯一的自由产生元为数字一。
设Σ是一有限字母表,则Σ*包含于Σ之上的所有文字,于形式语言理论的意思之下。因此,形式语言的抽象研究可以想成是有限产生自由幺半群子集的研究。且幺半群理论和自动机理论是有着很深的关联性的。例如,于Σ以上的正则语言会是有限幺半群子集的Σ*的同态像原。
例如,若A={a, b, c},A*的元素会是下列的形式
- {ε, a, ab, ba, caa, cccbabbc}
若A是一集合,则在A*上的字长函数是由A*至N的唯一幺半群同态,其将A的每一个元素都映射至1。
自由可交换幺半群
给定一集合A,则在A上的自由可交换幺半群是指由A内元素形成之复集所组成的集合。这形成了以复集联合为二元运算的可交换幺半群。
例如,若A = {a, b, c},于A上的自由可交换幺半群元素会是下列的形式
- {ε, a, ab, a2b, ab3c4}
另见
- Kleene星号
- 字符串运算