连接
| 连接 | |
|---|---|
| 术语名称 | 连接 |
| 英语名称 | concatenation |
| 别名 | 并置, juxtaposition |
连接(concatenation)指把两个字符或字符串首尾相接构成一个字符串的运算。 也指将两个字符串集（或形式语言）通过元素级连接运算得到新的集合（或形式语言）的运算。
定义
| 连接 | |
|---|---|
| 运算名称 | 连接 |
| 运算符号 | （不使用运算符）,[math]\displaystyle{ \cdot }[/math] |
| Latex | （不使用运算符） , \cdot
|
| 运算对象 | 字符, 字符串 |
| 运算元数 | 2 |
| 运算结果 | 字符串 |
| 结构 | 幺半群 |
| 定义域 | [math]\displaystyle{ \Sigma^*\times\Sigma^* }[/math] |
| 陪域 | [math]\displaystyle{ \Sigma^* }[/math] |
对集合 [math]\displaystyle{ \Sigma }[/math] 上的字符串 [math]\displaystyle{ a = \mathtt{a}_1 \mathtt{a}_2 \cdots \mathtt{a}_n }[/math] 和字符串 [math]\displaystyle{ b = \mathtt{b}_1 \mathtt{b}_2 \cdots \mathtt{b}_n }[/math] ，称字符串 [math]\displaystyle{ \mathtt{a}_1 \mathtt{a}_2 \cdots \mathtt{a}_n \mathtt{b}_1 \mathtt{b}_2 \cdots \mathtt{b}_n }[/math] 为两个字符串的连接(concatenation)，记作 [math]\displaystyle{ ab }[/math] 或 [math]\displaystyle{ a\cdot b }[/math]。类似地，也定义在字符和字符、字符和字符串、字符串和字符之间。
| 连接 | |
|---|---|
| 运算名称 | 连接 |
| 运算符号 | （不使用运算符）,[math]\displaystyle{ \cdot }[/math] |
| Latex | （不使用运算符） , \cdot
|
| 运算对象 | 语言 |
| 运算元数 | 2 |
| 运算结果 | 语言 |
| 结构 | 幺半群 |
| 定义域 | [math]\displaystyle{ \mathcal{P}(\Sigma^*)\times\mathcal{P}(\Sigma^*) }[/math] |
| 陪域 | [math]\displaystyle{ \mathcal{P}(\Sigma^*) }[/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 = \mathtt{a}_1 \mathtt{a}_2 \cdots \mathtt{a}_n }[/math] ，存在左右逆元 [math]\displaystyle{ a^{-1} = \mathtt{a}_n^{-1} \mathtt{a}_{n-1}^{-1} \cdots \mathtt{a}_1^{-1} }[/math] 满足 [math]\displaystyle{ a a^{-1} = a^{-1} a = \varepsilon }[/math]。
- 自由幺半群上的字符串连接后的长度总是两个字符串之和，即 [math]\displaystyle{ |ab|=|a|+|b| }[/math] 。