查看“︁自连接”︁的源代码

[[分类:形式语言]]
[[分类:字符串]]
{{InfoBox
|name=自连接
|eng_name=self-concatenation
|aliases=重复,repetition,幂,exponentiation
}}
'''自连接'''('''concatenation''')指把一个[[字符]]或[[字符串]]自身[[连接]]指定次数构成一个字符串的运算。
也指将一个字符串集（或[[形式语言]]）通过元素级自连接运算得到新的集合（或形式语言）的运算。

== 定义 ==

{{Operation
|name=自连接
|symbol=<math>\bullet^\bullet</math>
|latex=^
|operand=字符,字符串,自然数
|result=字符串
|prototype=幺半群
|domain=<math>\Sigma^*\times\mathbb{N}</math>
|codomain=<math>\Sigma^*</math>
}}
对字符串 <math>a = \mathtt{a}_1 \mathtt{a}_2 \cdots \mathtt{a}_m</math> 和自然数 <math>n</math> ，称字符串 <math>\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>a</math> 的 <math>n</math> 次'''自连接'''('''concatenation''')，记作 <math>a^n</math> 。也有人称为 <math>n</math> 次幂或 <math>n</math> 次重复。类似地，也定义在字符和字符、字符和字符串、字符串和字符之间。

{{Operation
|name=自连接
|symbol=<math>\bullet^\bullet</math>
|latex=^
|operand=语言,自然数
|result=语言
|prototype=幺半群
|domain=<math>\mathcal{P}(\Sigma^*)\times\mathbb{N}</math>
|codomain=<math>\mathcal{P}(\Sigma^*)</math>
}}
对语言 <math>L</math> 和自然数 <math>n</math> ，称语言 <math>\{w_1w_2\cdots w_n \mid (\forall i)(w_i \in L) \}</math> 为语言 <math>L</math> 的 <math>n</math> 次'''自连接'''('''self-concatenation''')，记作 <math>L^n</math> 。

注：是其中 <math>n</math> 个可以相同也可以不同元素的连接，不要求是同一个元素的自连接。

== 性质 ==

字符串上的连接同构于构造在一般的[[自由幺半群]]上的运算，而自连接对应的就是群运算的幂记号，因此满足以下性质：
* 幺半群运算导出性质
** <math>(a^m)^n = a^{mn}</math> 。
** <math>a^m a^n = a^{m+n}</math> 。
** 零次自连接为[[幺元]] <math>a^0 = \varepsilon</math> 。
* '''自由半群'''上存在两种平凡的自连接： <math>a^n = a \leftrightarrow n=1 \lor a=\varepsilon</math>
* '''自由半群'''上的字符串连接后的长度是原字符串的对应倍数，即 <math>|a^n|=n\cdot |a|</math> 。


{{字符串}}