Namespaces
Variants
Actions

Concatenation

From Encyclopedia of Mathematics
Jump to: navigation, search

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.

How to Cite This Entry:
Concatenation. Encyclopedia of Mathematics. URL: http://www.encyclopediaofmath.org/index.php?title=Concatenation&oldid=37514