Concatenation

catenation

For words over some alphabet, the word obtained by taking the symbols of each word in order: if $x = (x_1,\ldots,x_m)$ and $y = (y_1,\ldots,y_n)$ then the concatenation $xy$ is the word $(x_1,\ldots,x_m,y_1,\ldots,y_n)$: the notations $x|y$, $x \cdot y$ are also used. Denoting the empty word by $\lambda$, we have $x \lambda = \lambda x = x$.

For languages (sets of words), the concatenation language is the set of concatenations $$ L_1 L_2 = \\{ x y : x \in L_1,\, y \in L_2 \\} \ . $$

Concatenation is associative, and defines a semi-group structure on the set of words over an alphabet.