形式陈述

若 $u=u_1\cdots u_m$$u=u_1\cdots u_m$、$v=v_1\cdots v_n$$v=v_1\cdots v_n$ 是 $\Sigma$$\mathrm{\Sigma }$ 上的字，其连接为

$$ uv=u_1\cdots u_m v_1\cdots v_n. $$$$uv=u_1\cdots u_m{v}_1\cdots v_n.$$

形式上，$uv:\{1,\ldots,m+n\}\to\Sigma$$uv:\{1,\dots ,m+n\}\to \mathrm{\Sigma }$ 在前 $m$$m$ 个位置取 $u$$u$，其余位置按平移后的索引取 $v$$v$。连接满足

$$ (uv)w=u(vw), \qquad \varepsilon u=u\varepsilon=u, \qquad |uv|=|u|+|v|. $$$$(uv)w=u(vw),\epsilon u=u\epsilon =u,|uv|=|u|+|v|.$$

因此 $(\Sigma^*,\cdot,\varepsilon)$$({\mathrm{\Sigma }}^{\ast },\cdot ,\epsilon )$ 是自由幺半群。字符串还满足左右消去律：$uw=vw\Rightarrow u=v$$uw=vw\Rightarrow u=v$，$wu=wv\Rightarrow u=v$$wu=wv\Rightarrow u=v$。

直觉

连接就是把第二段原样接到第一段末尾；不需要插入分隔符，所以切分位置来自已知长度，而不是结果字符串本身自动标注。

例子与边界

若 $u=01$$u=01$、$v=10$$v=10$，则 $uv=0110$$uv=0110$ 而 $vu=1001$$vu=1001$，说明连接一般不交换；若字母表只含一个符号，则所有字形如 $a^n$$a^n$，此时连接恰好交换。$\varepsilon$$\epsilon$ 是单位元而非“空格字符”。连接后的字可能有多种分解，例如 $abc=(a)(bc)=(ab)(c)$$abc=(a)(bc)=(ab)(c)$；自由幺半群的“自由”并不表示分解成任意字唯一，而表示从字母上的任意映射可唯一延拓为幺半群同态。

推论与应用

连接生成语言乘积、Kleene 星、语法推导和流式解析；自由幺半群的泛性质连接形式语言与代数自动机理论。

参考资料

• Michael Sipser, Introduction to the Theory of Computation, 3rd ed., Cengage, 2013，Ch. 0, concatenation and string operations。
• John E. Hopcroft, Rajeev Motwani, and Jeffrey D. Ullman, Introduction to Automata Theory, Languages, and Computation, 3rd ed., Pearson, 2006，Ch. 1, concatenation and free monoids。