## 半群
设 S 是定义了一个运算的非空集合，若该运算是可结合的，则称 S 为半群；若该运算还有一个单位元，则称 S 为幺半群。
设 F = F(A) 表示 A 上所有字符串在连接运算下的集合，显然对于任意串 u，v，w，串(uv)w 和 u(vw)是一样的；它们都是由u，v，w一个接一个地写成的。因此 F 是一个半群，称为 A 上的自由半群；A 的元素，称为 F 的生成元。
空序列记为 \lambda，也看做 A 上的一个串，但我们不能认为\lambda属于 自由半群 F = F(A)。 A 上所有的串包括 \lambda 记为 A *。于是 A * 是连接下的一个幺半群，称为 A 上的自由幺半群。
设 A 是半群 S 的一个非空子集，如果 A 本身对于 S 上的运算是一个半群，则称 A 为 S 的一个子半群。因为 A 中的元素也是 S 的元素，A 中的元素自然满足结合行。
因此 A 是一个子半群当且仅当 其在 S 的运算下封闭。
设 S 是一个半群，~ 是 S 上的一个等价关系。回顾等价关系，可以把集合 S 分成等价类，且用[a]表示含有集合 S 中的元素 a 的等价类，等价类的集合记为：S/~。
假设 S 上的等价关系有下面的性质： $$ a ~ a', b ~ b' \implies ab ~ a'b' $$
那么 ~ 称为 S 上的同余关系。而且可以定义等价类上的一个运算： $$ [a] * [b] = [a * b], [a] [b] = [ab] $$
并且这个 S/~ 上的运算是可结合的，因此，S/~ 是一个半群。
定理 设 ~ 是半群 S 上的一个同余关系，那么 ~ 的等价类 S/~ 关于运算 $$ [a] [b] = [ab] $$ 构成一个半群。这个半群 S/~ 称为由 ~生成的商群。
考虑两个半群(S, *) 和 (S', *')，函数 f: S\to S'，称为半群同态，或简称同态，如果： $$ f(a * b) = f(a) *' f(b) 或 f(ab) = f(a)f(b) $$ 假设 f 是单射的，满射的，则 f 称为 S 与 S' 之间的一个同构，S 和 S' 称为同构半群，记作： $$ S\cong S' $$
定理 设 f: S\to S' 是一个半群同态，如果 f(a) = f(b)，今 a ~ b，则
i. ~ 是S 上的同余关系； ii. S/~ 同构于 f(S)；
设 (S1, *1) 和 (S2, *2) 是两个半群，我们构造一个新半群 S = S1 \otimes S2，称为 S1 和 S2 的直积，如下：
- S 中的元素来自 S1\times S2，即 S 中的元素是有序偶 (a,b), a\in S1, b\in S2；
- S 中的运算 * 定义为分量两两相乘，即： $$ (a, b) * (a', b') = (a *_1 a', b *_2 b') $$ 或简记为： $$ (a, b)(a', b') = (aa', bb') $$ （可证明，上面的运算是可结合的。）