连接
| 连接 | |
|---|---|
| 术语名称 | 连接 |
| 英语名称 | concatenation |
| 别名 | 并置, juxtaposition |
连接(concatenation)指把两个字符或字符串首尾相接构成一个字符串的运算。 也指将两个字符串集（或形式语言）通过元素级连接运算得到新的集合（或形式语言）的运算。
定义
| 连接 | |
|---|---|
| 运算名称 | 连接 |
| 运算符号 | |
| Latex | |
| 运算对象 | 字符, 字符串, 语言 |
| 运算元数 | 2 |
| 运算结果 | 字符串, 语言 |
| 结构 | 幺半群 |
| 定义域 | [math]\displaystyle{ \Sigma^*\times\Sigma^* }[/math] |
| 陪域 | [math]\displaystyle{ \Sigma^* }[/math] |
对字符串 [math]\displaystyle{ a = a_1 a_2 \cdots a_n }[/math] 和字符串 [math]\displaystyle{ b = b_1 b_2 \cdots b_n }[/math] ，称字符串 [math]\displaystyle{ a_1 a_2 \cdots a_n b_1 b_2 \cdots b_n }[/math] 为两个字符串的连接(concatenation)，记作 [math]\displaystyle{ ab }[/math] 。类似地，也定义在字符和字符、字符和字符串、字符串和字符之间。
对语言 [math]\displaystyle{ L_1 }[/math] 和 [math]\displaystyle{ L_2 }[/math] ，称语言 [math]\displaystyle{ \{w_1 w_2 \mid w_1 \in L_1 \land w_2 \in L_2 \} }[/math] 为两个语言的连接(concatenation)，记作 [math]\displaystyle{ L_1 L_2 }[/math] 。
由于连接运算符合结合律，也会说多个字符串（或字符）的连接以及多个语言的连接。
注：由于这种不加运算符的二元运算表达式也被叫做“并置(juxtaposition)”，也有人会将字符串的连接称为字符串的并置。但“并置”一词本身指的是两个操作数之间不加运算符的运算，也包括各种不写运算符或省略了运算符的二元运算，如乘法。
注：以上定义中只考虑实际意义上的字符串及抽象在自由半群中的字符串，如果字符串是自由群上的则应包含简化操作，见自由群词条。
性质
字符串上的连接同构于构造在一般的自由半群上的运算，因此总是使结构满足幺半群或群，满足以下性质：
- 结合律：[math]\displaystyle{ (ab)c = a(bc) }[/math]，通常直接记作 [math]\displaystyle{ abc }[/math] 。
- 有幺元：存在空串 [math]\displaystyle{ \varepsilon }[/math] ，满足对任意字符串 [math]\displaystyle{ a }[/math] 都有 [math]\displaystyle{ \varepsilon a = a \varepsilon = a }[/math]
- 有逆元（如果是自由群）：对字符串 [math]\displaystyle{ a = a_1 a_2 \cdots a_n }[/math] ，存在左右逆元 [math]\displaystyle{ a^{-1} = a_n^{-1} a_{n-1}^{-1} \cdots a_1 }[/math] 满足 [math]\displaystyle{ a a^{-1} = a^{-1} a = \varepsilon }[/math]。