複製鏈接
請複製以下鏈接發送給好友

自由幺半羣

鎖定
在抽象代數里,於一集合A上的自由幺半羣是指一幺半羣,其元素都是由A內零個或多個元素以串接之二元運算形成的有限序列(或字符串)。通常標記為A*。其單位元為空字元串,標記為ε 或 λ。在A上的自由半羣則指是A*內的子半羣,其包含除了空字串外的所有元素。通常標記為A
中文名
自由幺半羣
學    科
數學

自由幺半羣定義

更一般地,一抽象幺半羣(半羣)S被稱做是自由的,若其與某一集合上的自由幺半羣(半羣)同構
如其名稱所述,自由幺半羣(半羣)為滿足定義了自由對象泛性質的對象,在幺半羣(半羣)的範疇裏。它允許每一個幺半羣(半羣)都會是某一自由幺半羣(半羣)的同態映像。研究半羣為自由半羣的映像的學科稱做組合半羣理論。

自由幺半羣自由生成元和秩

集合A的元素稱為A*和A是自由生成元。更一般地講,若S是一抽象自由幺半羣(半羣),則有一集合含有映射至與A*(A)同態的單字母集合的元素,此集合稱為S的“自由生成元集合”。
每一自由幺半羣(半羣)S會有一個且只有一個自由生成元集合,其則稱做S的“秩”。
兩個自由幺半羣(半羣)同構當且僅當它們擁有相同的秩。而事實上,自由幺半羣(半羣)S的每一生成元集合都會包含其自由生成元。這使得一個自由幺半羣(半羣)會是有限生成的當且僅當它的秩是有限個的。 [1] 

自由幺半羣例子

自然數(包括零)在加法下的幺半羣(N,+)是一有單一產生元(即其秩為一)的自由幺半羣。它唯一的自由產生元為數字一。
設Σ是一有限字母表,則Σ*包含於Σ之上的所有文字,於形式語言理論的意思之下。因此,形式語言的抽象研究可以想成是有限產生自由幺半羣子集的研究。且幺半羣理論和自動機理論是有着很深的關聯性的。例如,於Σ以上的正則語言會是有限幺半羣子集的Σ*的同態像原。
例如,若A={a,b,c},A*的元素會是下列的形式
  • {ε,a,ab,ba,caa,cccbabbc}
A是一集合,則在A*上的字長函數是由A*至N的唯一幺半羣同態,其將A的每一個元素都映射至1。 [1] 

自由幺半羣自由可交換幺半羣

給定一集合A,則在A上的自由可交換幺半羣是指由A內元素形成之復集所組成的集合。這形成了以復集聯合為二元運算的可交換幺半羣。
例如,若A= {a,b,c},於A上的自由可交換幺半羣元素會是下列的形式
  • {ε,a,ab,ab,abc} [2] 
參考資料
  • 1.    Berstel, J.; Séébold, P. (1994). "A remark on morphic Sturmian words". RAIRO, Inform. Théor. Appl. 2. 8 (3–4): 255–263. ISSN 0988-3754. Zbl 0883.68104.
  • 2.    Aldo de Luca; Stefano Varricchio (1999). Finiteness and Regularity in Semigroups and Formal Languages. Springer Berlin Heidelberg. p. 2. ISBN 978-3-642-64150-3.