跳转到内容

自由么半群

本页使用了标题或全文手工转换
维基百科,自由的百科全书

抽象代數裡,於一集合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}

另見

[编辑]