自连接
| 自连接 | |
|---|---|
| 术语名称 | 自连接 |
| 英语名称 | self-concatenation |
| 别名 | 重复, repetition, 幂, exponentiation |
自连接(concatenation)指把一个字符或字符串自身连接指定次数构成一个字符串的运算。 也指将一个字符串集（或形式语言）通过元素级自连接运算得到新的集合（或形式语言）的运算。
定义
| 自连接 | |
|---|---|
| 运算名称 | 自连接 |
| 运算符号 | [math]\displaystyle{ \bullet^\bullet }[/math] |
| Latex | ^
|
| 运算对象 | 字符, 字符串 |
| 运算元数 | 2 |
| 运算结果 | 字符串 |
| 结构 | 幺半群 |
| 定义域 | [math]\displaystyle{ \Sigma^*\times\mathbb{N} }[/math] |
| 陪域 | [math]\displaystyle{ \Sigma^* }[/math] |
对字符串 [math]\displaystyle{ a = \mathtt{a}_1 \mathtt{a}_2 \cdots \mathtt{a}_m }[/math] 和自然数 [math]\displaystyle{ n }[/math] ，称字符串 [math]\displaystyle{ \underbrace{\mathtt{a}_1 \mathtt{a}_2 \cdots \mathtt{a}_m \mathtt{a}_1 \mathtt{a}_2 \cdots \mathtt{a}_m \cdots \mathtt{a}_1 \mathtt{a}_2 \cdots \mathtt{a}_m}_{n 个 \mathtt{a}_1 \mathtt{a}_2 \cdots \mathtt{a}_m} }[/math] 为字符串 [math]\displaystyle{ a }[/math] 的 [math]\displaystyle{ n }[/math] 次自连接(concatenation)，记作 [math]\displaystyle{ a^n }[/math] 。也有人称为 [math]\displaystyle{ n }[/math] 次幂或 [math]\displaystyle{ n }[/math] 次重复。类似地，也定义在字符和字符、字符和字符串、字符串和字符之间。
| 自连接 | |
|---|---|
| 运算名称 | 自连接 |
| 运算符号 | [math]\displaystyle{ \bullet^\bullet }[/math] |
| Latex | ^
|
| 运算对象 | 语言 |
| 运算元数 | 2 |
| 运算结果 | 语言 |
| 结构 | 幺半群 |
| 定义域 | [math]\displaystyle{ \mathcal{P}(\Sigma^*)\times\mathbb{N} }[/math] |
| 陪域 | [math]\displaystyle{ \mathcal{P}(\Sigma^*) }[/math] |
对语言 [math]\displaystyle{ L }[/math] 和自然数 [math]\displaystyle{ n }[/math] ，称语言 [math]\displaystyle{ \{w_1w_2\cdots w_n \mid (\forall i)(w_i \in L) \} }[/math] 为语言 [math]\displaystyle{ L }[/math] 的 [math]\displaystyle{ n }[/math] 次自连接(self-concatenation)，记作 [math]\displaystyle{ L^n }[/math] 。
注：是其中 [math]\displaystyle{ n }[/math] 个可以相同也可以不同元素的连接，不要求是同一个元素的自连接。
性质
字符串上的连接同构于构造在一般的自由半群上的运算，而自连接对应的就是群运算的幂记号，因此满足以下性质：
- 幺半群运算导出性质
- [math]\displaystyle{ (a^m)^n = a^{mn} }[/math] 。
- [math]\displaystyle{ a^m a^n = a^{m+n} }[/math] 。
- 零次自连接为幺元 [math]\displaystyle{ a^0 = \varepsilon }[/math] 。
- 自由半群上存在两种平凡的自连接： [math]\displaystyle{ a^n = a \leftrightarrow n=1 \lor a=\varepsilon }[/math]
- 自由半群上的字符串连接后的长度是原字符串的对应倍数，即 [math]\displaystyle{ |a^n|=n\cdot |a| }[/math] 。