形式陈述

给定集合 $X$$X$，其自由幺半群 $X^*$$X^{\ast }$ 是所有有限字串

$$ x_1x_2\cdots x_n\quad(n\ge0, \ x_i\in X) $$$$x_1{x}_2\cdots x_n(n\ge 0,x_i\in X)$$

的集合，运算为串连接，单位元为空串 $\varepsilon$$\epsilon$。它满足泛性质：对任意幺半群 $M$$M$ 和函数 $f:X\to M$$f:X\to M$，存在唯一幺半群同态 $\widehat f:X^*\to M$$\hat{f}:X^{\ast }\to M$ 使 $\widehat f(x)=f(x)$$\hat{f}(x)=f(x)$；显式地，$\widehat f(x_1\cdots x_n)=f(x_1)\cdots f(x_n)$$\hat{f}(x_1\cdots x_n)=f(x_1)\cdots f(x_n)$。该性质在同构意义下唯一刻画 $X^*$$X^{\ast }$。

直觉

自由对象只加入幺半群公理强迫的等式，不额外规定不同字串相等；因此给字母赋值后，整个串的解释只能按次序相乘延拓。

例子与边界

若 $X=\{a,b\}$$X=\{a,b\}$，则 $ab$$ab$ 与 $ba$$ba$ 是不同元素，说明自由幺半群通常不交换；$\varepsilon a=a\varepsilon=a$$\epsilon a=a\epsilon =a$。若 $X=\varnothing$$X=\varnothing$，则 $X^*=\{\varepsilon\}$$X^{\ast }=\{\epsilon \}$ 是平凡幺半群。自由半群通常只取非空串 $X^+$$X^{+}$，没有空串单位元。自由群还要加入形式逆元并约去 $xx^{-1}$$x{x}^{-1}$，不能与 $X^*$$X^{\ast }$ 混同。一个字母上的自由幺半群与 $(\mathbb N,+)$$(\mathbb{N},+)$ 同构，串长度对应自然数。

推论与应用

自由幺半群是形式语言、自动机和字符串算法的环境；其泛性质也用于从生成元定义同态，并为群呈示中的词与关系提供语法起点。

参考资料

• David S. Dummit and Richard M. Foote, Abstract Algebra, 3rd ed., Wiley, 2004，Ch. 1, free groups and words; monoid precursor。
• Michael Artin, Algebra, 2nd ed., Pearson, 2011，Ch. 2, free constructions and words。