Verkettung

Verkettung (von englisch concatenation) bezeichnet in der Mathematik, Informatik und Sprachwissenschaft das Aneinanderfügen zweier Sequenzen, Wörter oder Listen zu einer längeren Sequenz. Die resultierende Sequenz AB besteht aus den Elementen von A gefolgt von den Elementen von B.

In der formalen Sprachtheorie wird die Verkettung zweier Sprachen L1 und L2 definiert als L1L2 = {xy | x ∈ L1, y ∈ L2}. Die Verkettung ist assoziativ; (L1L2)L3 = L1(L2L3). Das leere Wort ε dient als Identität, sodass εL = Lε = L gilt.

Im Bereich der Informatik bezeichnet Verkettung häufig das Zusammenführen von Zeichenketten oder Listen. In Programmiersprachen existieren Operatorsymbole oder Funktionen zur Verkettung, zum Beispiel zum Verknüpfen von Strings. Bei Listen hängt die Kostenstruktur von der verwendeten Datenstruktur ab: Bei verketteten Listen lässt sich eine Verkettung oft in konstanter Zeit realisieren, während bei Arrays eine Kopie oder spezielle Algorithmen notwendig sein kann.

Beispiele: Die Verkettung der Zeichenketten "Hallo" und "Welt" ergibt "HalloWelt". In der formalen Sprache {a, b} {c, d} ergibt die Verkettung {ac, ad, bc, bd}.

Verkettung wird auch in anderen Zusammenhängen verwendet, etwa beim Zusammenführen von Symbolfolgen in Parsing-Algorithmen oder beim Aufbau von Befehlsketten in Compiler-Backends. Sie ist ein grundlegendes Konzept mit der Eigenschaft der Assoziativität, aber typischerweise nicht der Kommutativität.