Konkatenationsverknüpfung

Konkatenationen (German for concatenation; in English often simply concatenation) refers to the operation of joining two sequences to form a new sequence. In the context of strings over an alphabet, the concatenation of strings x and y is the string xy obtained by appending y after x. For two languages L and M (sets of strings over the same alphabet), their concatenation is LM = { xy | x ∈ L, y ∈ M } and the concatenation operation extends to finite sequences of strings.

Key properties include associativity, since (xy)z = x(yz). The empty string ε acts as an identity element, so εx = xε = x. In general, concatenation is not commutative; xy does not necessarily equal yx. Concatenation is closed under the construction of regular languages and context-free languages, and it is central to forming longer strings and more complex languages. The Kleene star L* denotes the set of all finite concatenations of zero or more strings from L.

In computer science, concatenation is a fundamental primitive in string processing, compilers, and data serialization. Performance considerations arise with repeated concatenation in some languages, where naive approaches can incur quadratic time; practical implementations often use optimized builders or join operations.

Variants of the concept extend to sequences in programming, and to the monoid structure of strings with ε as the identity element. Concatenation also underpins constructs in formal grammars, automata, and regular expressions, and it has applications in natural language processing for word formation and pattern assembly.

See also: monoid, regular language, context-free language, Kleene star, join operation.