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

[[分类:形式语言]]
[[分类:字符串]]
{{InfoBox
|name=连接
|eng_name=concatenation
|aliases=并置,juxtaposition
}}
'''连接'''('''concatenation''')指把两个[[字符]]或[[字符串]]首尾相接构成一个字符串的运算。
也指将两个字符串集（或形式语言）通过元素级连接运算得到新的集合（或形式语言）的运算。

== 定义 ==

{{Operation
|name=连接
|symbol=（不使用运算符）,<math>\cdot</math>
|latex=（不使用运算符）,\cdot
|operand=字符,字符串
|result=字符串
|prototype=幺半群
|domain=<math>\Sigma^*\times\Sigma^*</math>
|codomain=<math>\Sigma^*</math>
}}
对集合 <math>\Sigma</math> 上的[[字符串]] <math>a = \mathtt{a}_1 \mathtt{a}_2 \cdots \mathtt{a}_n</math> 和字符串 <math>b = \mathtt{b}_1 \mathtt{b}_2 \cdots \mathtt{b}_n</math> ，称字符串 <math>\mathtt{a}_1 \mathtt{a}_2 \cdots \mathtt{a}_n \mathtt{b}_1 \mathtt{b}_2 \cdots \mathtt{b}_n</math> 为两个字符串的'''连接'''('''concatenation''')，记作 <math>ab</math> 或 <math>a\cdot b</math>。类似地，也定义在字符和字符、字符和字符串、字符串和字符之间。

{{Operation
|name=连接
|symbol=（不使用运算符）,<math>\cdot</math>
|latex=（不使用运算符）,\cdot
|operand=语言
|result=语言
|prototype=幺半群
|domain=<math>\mathcal{P}(\Sigma^*)\times\mathcal{P}(\Sigma^*)</math>
|codomain=<math>\mathcal{P}(\Sigma^*)</math>
}}
对语言 <math>L_1</math> 和 <math>L_2</math> ，称语言 <math>\{w_1 w_2 \mid w_1 \in L_1 \land w_2 \in L_2 \}</math> 为两个语言的'''连接'''('''concatenation''')，记作 <math>L_1 L_2</math> 。

由于连接运算符合[[结合律]]，也会说多个字符串（或字符）的连接以及多个语言的连接。

注：由于这种不加运算符的二元运算表达式也被叫做“并置(juxtaposition)”，也有人会将字符串的连接称为字符串的并置。但“并置”一词本身指的是两个操作数之间不加运算符的运算，也包括各种不写运算符或省略了运算符的二元运算，如乘法。

注：以上定义中只考虑实际意义上的字符串及抽象在[[自由幺半群]]中的字符串，如果字符串是[[自由群]]上的则应包含简化操作，见自由群词条。

== 性质 ==

字符串上的连接同构于构造在一般的幺半群上的运算，因此总是使结构满足[[幺半群]]或[[群]]，满足以下性质：
* [[结合律]]：<math>(ab)c = a(bc)</math>，通常直接记作 <math>abc</math> 。
* 有[[幺元]]：存在[[空串]] <math>\varepsilon</math> ，满足对任意字符串 <math>a</math> 都有 <math>\varepsilon a = a \varepsilon = a</math>
* '''自由群'''上的字符串有[[逆元]]：对字符串 <math>a = \mathtt{a}_1 \mathtt{a}_2 \cdots \mathtt{a}_n</math> ，存在左右逆元 <math>a^{-1} = \mathtt{a}_n^{-1} \mathtt{a}_{n-1}^{-1} \cdots \mathtt{a}_1^{-1}</math> 满足 <math>a a^{-1} = a^{-1} a = \varepsilon</math>。
* '''自由幺半群'''上的字符串连接后的长度总是两个字符串之和，即 <math>|ab|=|a|+|b|</math> 。


{{字符串}}