Konkatenation

Die Konkatenation oder Verkettung ist eine Verknüpfung zweier Wörter zu einem neuen Wort, das durch Aneinanderhängen der beiden Symbolfolgen entsteht. Die Konkatenation der beiden Wörter ${\displaystyle x}$ und ${\displaystyle y}$ über einem Alphabet ${\displaystyle \Sigma }$ wird mit ${\displaystyle xy}$ oder ${\displaystyle x\circ y}$ angegeben und ist definiert durch:

${\displaystyle xy=x\circ y:=(x_{1},x_{2},x_{3},\ldots ,x_{n},y_{1},y_{2},y_{3},\ldots ,y_{k})}$

Dabei ist nach der Definition des Wortes ${\displaystyle x=(x_{1},x_{2},x_{3},\ldots ,x_{n})}$ und ${\displaystyle y=(y_{1},y_{2},y_{3},\ldots ,y_{k})}$ mit ${\displaystyle n,k\in \mathbb {N} _{0}}$ und ${\displaystyle x_{i},y_{j}\in \Sigma }$ für alle ${\displaystyle i\in \{1,\ldots ,n\}}$ und ${\displaystyle j\in \{1,\ldots ,k\}}$. Nach der obigen Definition ist ${\displaystyle x}$ ein Präfix und ${\displaystyle y}$ ein Suffix des durch die Konkatenation entstandenen Wortes ${\displaystyle x\circ y}$. Die Länge eines konkatenierten Wortes entspricht dabei der Summe der Längen der einzelnen (Teil-)Wörter. So gilt für jedes Wort ${\displaystyle u}$ und ${\displaystyle v}$:

${\displaystyle |u\circ v|=|u|+|v|}$,

und für die absolute Häufigkeit eines Zeichens ${\displaystyle x}$:

${\displaystyle |u\circ v|_{x}=|u|_{x}+|v|_{x}}$.

Das neutrale Element der Konkatenation ist das leere Wort, da für jedes beliebige Wort ${\displaystyle w}$ gilt, dass:

${\displaystyle w\circ \varepsilon =\varepsilon \circ w=w}$

Da außerdem die Konkatenation assoziativ ist, bildet das Tripel ${\displaystyle (\Sigma ^{*},\circ ,\varepsilon )}$ aus der Menge aller Wörter über einem beliebigen Alphabet ${\displaystyle \Sigma }$, der Verknüpfung der Konkatenation und dem leeren Wort als neutralem Element ein Monoid. Die Assoziativität bedeutet, dass ohne weiteres Klammern weggelassen werden können:

${\displaystyle (haus\circ \heartsuit \clubsuit \clubsuit \heartsuit \spadesuit )\circ xyzzy=haus\circ (\heartsuit \clubsuit \clubsuit \heartsuit \spadesuit \circ xyzzy)=haus\heartsuit \clubsuit \clubsuit \heartsuit \spadesuit xyzzy}$

Demgegenüber ist die Konkatenation nicht kommutativ, d. h. nicht für alle Wörter ${\displaystyle u}$ und ${\displaystyle v}$ gilt, dass ${\displaystyle u\circ v=v\circ u}$ ist. So ist zum Beispiel:

${\displaystyle haus\circ \heartsuit \clubsuit \clubsuit \heartsuit \spadesuit =haus\heartsuit \clubsuit \clubsuit \heartsuit \spadesuit \not =\heartsuit \clubsuit \clubsuit \heartsuit \spadesuit haus=\heartsuit \clubsuit \clubsuit \heartsuit \spadesuit \circ haus}$

Potenz

Die ${\displaystyle n}$-te Potenz ${\displaystyle w^{n}}$ eines Wortes ${\displaystyle w}$ ist definiert als die ${\displaystyle (n-1)}$-fache Konkatenation dieses Wortes mit sich selbst. Die Definition der Potenz wird meist rekursiv angegeben:

${\displaystyle w^{0}:=\varepsilon }$

${\displaystyle w^{n+1}:=w^{n}\circ w}$   (für ${\displaystyle n\in \mathbb {N} _{0}}$)

So sind zum Beispiel:

${\displaystyle (xyzzy)^{0}=\varepsilon }$

${\displaystyle (\heartsuit \clubsuit \clubsuit \heartsuit \spadesuit )^{1}=(\heartsuit \clubsuit \clubsuit \heartsuit \spadesuit )^{0}\,\circ \,\heartsuit \clubsuit \clubsuit \heartsuit \spadesuit =\varepsilon \,\circ \,\heartsuit \clubsuit \clubsuit \heartsuit \spadesuit =\heartsuit \clubsuit \clubsuit \heartsuit \spadesuit }$

${\displaystyle (haus)^{3}=(haus)^{2}\,\circ \,haus=((haus)^{1}\,\circ \,haus)\,\circ \,haus=((\varepsilon \,\circ \,haus)\,\circ \,haus)\,\circ \,haus=haushaushaus}$

Nach der Definition der Konkatenation ist die Länge der ${\displaystyle n}$-ten Potenz eines beliebigen Wortes ${\displaystyle w}$ gleich dem Produkt aus ${\displaystyle n}$ und der Länge von ${\displaystyle w}$:

${\displaystyle |w^{n}|=n\cdot |w|}$,

und für die absolute Häufigkeit eines jeden Zeichens ${\displaystyle x}$:

${\displaystyle |w^{n}|_{x}=n\cdot |w|_{x}}$

Spiegelung

Die Spiegelung oder das Reverse ${\displaystyle w^{R}}$ eines Wortes ${\displaystyle w}$ ergibt sich, wenn man ${\displaystyle w}$ rückwärts schreibt. Wenn also ${\displaystyle w=(x_{1},x_{2},x_{3},\ldots ,x_{n})}$ ist, so ist ${\displaystyle w^{R}}$ die endliche Folge ${\displaystyle (y_{1},y_{2},y_{3},\ldots ,y_{k})}$ mit ${\displaystyle k=n}$ und ${\displaystyle y_{i}=x_{n+1-i}}$ für alle ${\displaystyle i\in \{1,\ldots ,k\}}$. Die Länge eines Wortes ist also gleich der Länge seiner Spiegelung:

${\displaystyle |w^{R}|=|w|}$

So gilt zum Beispiel für die folgenden Wörter:

${\displaystyle \varepsilon ^{R}=\varepsilon }$

${\displaystyle (abb)^{R}=bba}$

${\displaystyle (\heartsuit \clubsuit \spadesuit \heartsuit )^{R}=\heartsuit \spadesuit \clubsuit \heartsuit }$

Das Reverse eines Wortes lässt sich außerdem mit Hilfe der strukturellen Induktion über dem Aufbau des betreffenden Wortes definieren. Dazu definiert man im Induktionsanfang das Reverse des leeren Wortes als das leere Wort. Im Induktionsschritt definiert man das Reverse eines aus einem Teilwort und einem Symbol zusammengesetzten Wortes als die Konkatenation des Symbols mit dem Reversen des Teilwortes:

Induktionsanfang: ${\displaystyle w=\varepsilon \Rightarrow w^{R}=\varepsilon ^{R}:=\varepsilon }$

Induktionsschritt: ${\displaystyle (w=v\circ a)\land (v\in \Sigma ^{*},a\in \Sigma )\Rightarrow w^{R}=(v\circ a)^{R}:=a\circ (v^{R})}$

So lässt sich schrittweise das Reverse eines Wortes herleiten:

${\displaystyle \varepsilon ^{R}=\varepsilon }$

${\displaystyle (abb)^{R}=b\circ (ab)^{R}=b\circ b\circ (a)^{R}=b\circ b\circ a\circ (\varepsilon )^{R}=b\circ b\circ a\circ \varepsilon =bba}$

${\displaystyle (\heartsuit \clubsuit \spadesuit \heartsuit )^{R}=\heartsuit \circ (\heartsuit \clubsuit \spadesuit )^{R}=\heartsuit \circ \spadesuit \circ (\heartsuit \clubsuit )^{R}=\heartsuit \circ \spadesuit \circ \clubsuit \circ (\heartsuit )^{R}=\heartsuit \spadesuit \clubsuit \heartsuit }$

Ein Wort wie ${\displaystyle abaaba}$, das identisch mit seiner Spiegelung ist, wird Palindrom genannt. Mathematisch werden diese spiegelsymmetrischen Worte als die Fixpunkte der Spiegelung ^R angesehen.

Infix

Ein Infix ist eine Hinzufügung innerhalb eines Wortes. Jede endliche Teilfolge von aufeinander folgenden Symbolen eines Wortes ${\displaystyle w}$ wird Infix, Teilwort oder Faktor des Wortes ${\displaystyle w}$ genannt. Ein Infix eines gegebenen Wortes ${\displaystyle w=(x_{1},x_{2},x_{3},\ldots ,x_{n})}$ ist demnach jedes Wort ${\displaystyle {\hat {w}}=(y_{1},y_{2},y_{3},\ldots ,y_{k})}$, für das es (mindestens) ein ${\displaystyle i\in \mathbb {N} _{0}}$ gibt, für das gilt, dass zum einen ${\displaystyle k+i\leq n}$ und zum anderen ${\displaystyle x_{j+i}=y_{j}}$ für jedes ${\displaystyle j\in \{1,\ldots ,k\}}$ ist. Demnach ist ein Wort ${\displaystyle u}$ genau dann Infix eines Wortes ${\displaystyle w}$, wenn gilt, dass es mindestens ein Wort ${\displaystyle p}$ und ein Wort ${\displaystyle s}$ aus der Kleeneschen Hülle über dem Alphabet von ${\displaystyle w}$ gibt, so dass ${\displaystyle p\circ u\circ s=w}$ ist:

${\displaystyle u}$ ist Infix von ${\displaystyle w:\;\Longleftrightarrow \exists p,s\in \Sigma ^{\ast }:\;p\circ u\circ s=w}$

So ist das Wort ${\displaystyle {\hat {w}}=aba}$ mit ${\displaystyle {\hat {w}}\in \lbrace a,b\rbrace ^{*}}$ ein Infix der Wörter ${\displaystyle babaab}$, ${\displaystyle abaababb}$ und ${\displaystyle aba}$, nicht aber der Wörter ${\displaystyle abba}$, ${\displaystyle babbaabbab}$ beziehungsweise des leeren Wortes ${\displaystyle \varepsilon }$. In vielen Computersprachen ist für Infix die englische Bezeichnung substring gebräuchlich.

Speziell ist das leere Wort ein Infix jedes beliebigen Wortes, und jedes Wort ist ein Infix von sich selbst. Ein Infix eines beliebigen Wortes, das nicht identisch mit diesem ist, wird echtes Infix genannt.

Präfix

Ein Präfix ist eine Hinzufügung am Anfang eines Wortes. Ein Präfix eines Wortes ${\displaystyle w=(x_{1},x_{2},x_{3},\ldots ,x_{n})}$ ist demnach jedes Infix ${\displaystyle {\hat {w}}=(y_{1},y_{2},y_{3},\ldots ,y_{k})}$, für das gilt, dass ${\displaystyle k\leq n}$ und ${\displaystyle x_{j}=y_{j}}$ für jedes ${\displaystyle j\in \{1,\ldots ,k\}}$ ist. Demnach ist ${\displaystyle u}$ genau dann Präfix des Wortes ${\displaystyle w}$, wenn es mindestens ein ${\displaystyle s}$ aus der Kleeneschen Hülle über dem Alphabet, aus dem ${\displaystyle w}$ erzeugt wurde, gibt, so dass ${\displaystyle u\circ s=w}$ ist:

${\displaystyle u}$ ist Präfix von ${\displaystyle w:\;\Longleftrightarrow \exists s\in \Sigma ^{\ast }:\;u\circ s=w}$

Auch für Präfixe gilt, dass jedes Wort ein Präfix von sich selbst und das leere Wort ein Präfix jedes beliebigen Wortes ist. Ein Präfix eines Wortes, das nicht identisch mit ihm ist, wird echtes Präfix genannt.

Suffix

Ein Suffix, auch Postfix genannt, ist eine Hinzufügung am Ende eines Wortes. Ein Suffix eines Wortes ${\displaystyle w=(x_{1},x_{2},x_{3},\ldots ,x_{n})}$ ist nach der Definition des Infixes jedes Teilwort ${\displaystyle {\hat {w}}=(y_{1},y_{2},y_{3},\ldots ,y_{k})}$, für das gilt, dass es ein ${\displaystyle i\in \mathbb {N} _{0}}$ gibt, für das zum einen ${\displaystyle k+i=n}$ und zum anderen ${\displaystyle x_{j+i}=y_{j}}$ für jedes ${\displaystyle j\in \{1,\ldots ,k\}}$ ist. Demnach ist ein Wort ${\displaystyle u}$ genau dann Suffix eines Wortes ${\displaystyle w}$ mit ${\displaystyle w\in \Sigma ^{\ast }}$, wenn es mindestens ein ${\displaystyle p\in \Sigma ^{\ast }}$ gibt, so dass ${\displaystyle p\circ u=w}$ ist:

${\displaystyle u}$ ist Suffix von ${\displaystyle w:\;\Longleftrightarrow \exists p\in \Sigma ^{\ast }:\;p\circ u=w}$

Wie für Präfixe und Infixe gilt auch für Suffixe, dass das leere Wort ein Suffix jedes beliebigen Wortes und ein beliebiges Wort stets auch ein Suffix von sich selbst ist. Ein Suffix eines Wortes, das nicht identisch mit ihm ist, wird echtes Suffix genannt.