半群

半群刻画“可以连续组合，而且组合次序中的括号不重要”的对象。结合律保证 $a_1\ast \cdots \ast a_n$ 无须指定括号，但不会允许任意交换元素次序。

半群只要求一种运算可结合，因此能无歧义地组合任意有限非空序列。它不保证空组合、逆操作或交换性，恰好适合描述不可撤销的过程与连续状态变换。结合律的价值在于允许改变求值括号，而不是允许交换次序。

正整数在加法下构成半群，却没有加法单位元；非空字符串在连接运算下也构成半群。整数减法不满足结合律，因为 $(5-3)-1\ne 5-(3-1)$。一个封闭运算即使满足交换律，也未必满足结合律。

正偶数在乘法下构成半群：乘积仍为正偶数且乘法结合，但单位元 $1$ 不在其中，所以它不是幺半群。另取任意非空集合 $X$，定义左零运算 $x\ast y=x$，则

故结合律成立；只要 $X$ 至少有两个元素，该运算便不交换。它说明结合律是一条独立条件，不能由封闭性、交换性或熟悉的算术外观自动推出。

加入双侧单位元得到幺半群，再要求每个元素可逆得到群。半群还用于描述自动机的状态变换、程序操作的顺序合成和代数化的字符串处理。

加入单位元得到 幺半群公理库幺半群Monoid具有双侧单位元的半群。，进一步加入逆元得到群。有限半群与自动机转换幺半群联系正则语言公理库正则语言Regular language存在有限状态识别器的有限字语言，也就是只需固定有限种前缀摘要即可判断的语言。，结合运算还支撑并行扫描、区间查询和动态规划公理库动态规划Dynamic programming在有限或良基的状态依赖上复用已计算结果的算法设计范式。中的状态合并。