Reverse

In der theoretischen Informatik ist ein Wort eine endliche Folge von Symbolen (Zeichenkette) aus einem Alphabet. Die Anzahl der Symbole eines Wortes w ist ihre Länge und wird mit | w | bezeichnet. Ein besonderes Wort ist das leere Wort, welches aus keinem Symbol besteht (die Länge 0 besitzt) und meist mit dem griechischen Buchstaben ε (Epsilon) dargestellt wird. Die Menge aller Wörter, welche man aus einem Alphabet Σ bilden kann, wird die Kleenesche Hülle über dieses Alphabet genannt und mit Σ ^* bezeichnet. Wörter bilden die Elemente einer formalen Sprache, welche als eine Teilmenge der Kleeneschen Hülle über ein gegebenes Alphabet definiert ist.

Definition

Es sei Σ ein gegebenes Alphabet und n eine natürliche Zahl mit $n\in\mathbb{N}_{0}$, wobei $\mathbb{N}_{0}$ die Menge der natürlichen Zahlen einschließlich der Null bezeichnet $(\mathbb{N}_{0} = \lbrace 0, 1, 2, ... \rbrace)$. Ein Wort w ist eine endliche Folge $(x_{1},\, x_{2},\, x_{3}, ...\, x_{n})$ mit $x_{i} \in \Sigma$ für alle $i \in \lbrack 1, n \rbrack$. Wie bereits erwähnt, ist die Zahl n die Länge des Wortes w.

Dabei wird zur Definition eines Wortes oft die vereinfachte Schreibweise $w=x_{1} x_{2} x_{3} ...\, x_{n}$ benutzt, was jedoch nur möglich ist, wenn das verwendete Alphabet eine eindeutige Zuordnung der benutzten Symbole zulässt. So kann diese Kurzschreibweise beim Alphabet $\Sigma = \lbrace a ,\, aa \rbrace$ nicht angewendet werden, da hier zum Beispiel aus der Schreibweise w = aaa nicht eindeutig hervorgeht, ob das Wort $(a ,\, aa)$, $(aa ,\, a)$ oder $(a ,\, a ,\, a)$ gemeint ist.

Beispiele

Es seien mit Σ₁ und Σ₂ zwei Alphabete gegeben, wobei Σ₁ das Alphabet der lateinischen Buchstaben und $\Sigma_{2} = \lbrace \diamondsuit,\, \heartsuit,\, \spadesuit,\, \clubsuit \rbrace$ ist. Dann sind die Wörter w₁ = haus und w₂ = xyzzy Beispiele für Wörter über Σ₁ und $w_{3} = \heartsuit \clubsuit \clubsuit \heartsuit \spadesuit$ ist ein Wort über Σ₂. Man erkennt, dass | w₁ | = 4 und | w₂ | = | w₃ | = 5 ist.

Operationen auf Wörtern

Konkatenation

Die Konkatenation oder Verkettung ist eine Verknüpfung zweier Wörter zu einem neuen Wort, welche sich aus dem Aneinanderhängen der beiden Symbolfolgen ergibt. Die Konkatenation der beiden Wörter x und y über ein Alphabet Σ wird mit xy oder $x \circ y$ angegeben und ist definiert durch:

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

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

$|u \circ v| = |u| + |v|$

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

$w \circ \epsilon = \epsilon \circ w = w$

Somit bildet das Tripel der Menge aller Wörter über ein beliebiges Alphabet Σ, die Verknüpfung der Konkatenation und das leere Wort als neutrales Element einen Monoiden. Damit ist die Konkatenation assoziativ und es gilt zum Beispiel:

$(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 u und v gilt, dass $u \circ v = v \circ u$ ist. Dies ist nämlich nur der Fall, wenn u und v übereinstimmen und/oder mindestens eines der beiden Wörter das leere Wort ist. So ist zum Beispiel:

$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 Potenz eines Wortes wⁿ ist definiert als die n-fache Konkatenation dieses Wortes mit sich selbst. Die Definition der Potenz wird meist rekursiv angegeben:

w⁰: = ε

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

So sind zum Beispiel:

xyzzy⁰ = ε

$\heartsuit \clubsuit \clubsuit \heartsuit \spadesuit^1 = \heartsuit \clubsuit \clubsuit \heartsuit \spadesuit^0 \,\circ\, \heartsuit \clubsuit \clubsuit \heartsuit \spadesuit = \epsilon \,\circ\, \heartsuit \clubsuit \clubsuit \heartsuit \spadesuit = \heartsuit \clubsuit \clubsuit \heartsuit \spadesuit$

$haus^3=haus^2 \,\circ\, haus = (haus^1 \,\circ\, haus) \,\circ\, haus = ((\epsilon \,\circ\, haus) \,\circ\, haus) \,\circ\, haus = haushaushaus$

Nach der Definition der Konkatenation ist die Länge der n-fachen Potenz eines beliebigen Wortes w gleich dem Produkt aus n und der Länge von w:

$|w^n| = n \cdot |w|$

Spiegelung

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

| w^R | = | w |

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

ε^R = ε

abb^R = bba

$\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, dass das Reverse des leeren Wortes gleich dem leeren Wort ist. Als Induktionsschritt definiert man, dass das Reverse eines aus einem Wort und einem Symbol zusammengesetzten Wortes gleich der Konkatenation des Symbols mit dem Reversen des Teilwortes ist:

Induktionsanfang: $w=\epsilon \Rightarrow w^{R} = \epsilon^{R} := \epsilon$

Induktionsschritt: $(w=v \circ a) \and (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:

ε^R = ε

$(abb)^R = b \circ (ab)^R = b \circ b \circ (a)^R = b \circ b \circ a \circ (\epsilon)^R = b \circ b \circ a \circ \epsilon = bba$

$\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 abaaba, welches identisch mit seiner Spiegelung ist, wird Palindrom genannt.

Infix, Suffix und Präfix

Infix

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

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

So ist das Wort $\hat w = aba$ mit $\hat w \in \lbrace a ,\, b \rbrace^*$ ein Infix der Wörter babaab, abaababb und aba, nicht aber der Wörter abba, babbaabbab beziehungsweise des leeren Wortes ε.

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

Präfix

Ein Präfix eines Wortes ist ein Infix beliebiger Länge von aufeinander folgenden, führenden Symbolen dieses Wortes. Ein Präfix eines Wortes $w = (x_{1},\, x_{2},\, x_{3}, ...\, x_{n})$ ist demnach jenes Infix $\hat w = (y_{1},\, y_{2},\, y_{3}, ...\, y_{k})$, für welches gilt, dass $k \leq n$ und x_j = y_j für jedes $j \in \lbrack 1 , k \rbrack$ ist. Demnach ist u genau dann Präfix des Wortes w, wenn es mindestens ein s aus der Kleeneschen Hülle über dem Alphabet, aus dem w erzeugt wurde, gibt, so dass $u \circ s = w$ ist:

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

So sind die Wörter ε, ab und abaab Präfixe des Wortes abaabb. Auch für Präfixe gilt, dass jedes Wort ein Präfix von sich selbst und das leere Wort stets ein Präfix jedes beliebigen Wortes ist. Echte Präfixe sind Präfixe eines Wortes, welche nicht identisch mit diesem Wort sind.

Suffix

Ein Suffix eines Wortes ist ein Infix beliebiger Länge von aufeinander folgenden Symbolen am Ende dieses Wortes. Ein Suffix eines Wortes $w = (x_{1},\, x_{2},\, x_{3}, ...\, x_{n})$ ist nach der Definition des Infixes jenes Teilwort $\hat w = (y_{1},\, y_{2},\, y_{3}, ...\, y_{k})$, für welches gilt, dass es ein $i \in \mathbb{N}_{0}$ gibt, für das zum einen k + i = n und zum anderen x_{j + i} = y_j für jedes $j \in \lbrack 1, k \rbrack$ ist. Demnach ist ein Wort u genau dann Suffix eines Wortes w mit $w \in \Sigma^\ast$, wenn es mindestens ein $p \in \Sigma^\ast$ gibt, so dass $p \circ u = w$ ist:

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

So sind die Wörter ε, ab und abaab Suffixe des Wortes babaab. Wie für Präfixe und Infixe gilt auch für Suffixe, dass das leere Wort immer 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.

Literatur

• John E. Hopcroft, Jeffry D. Ullman: Einführung in die Automatentheorie, formale Sprachen und Komplexitätstheorie. Bonn 1994, ISBN 3-89319-744-3. 
• Katrin Erk, Lutz Priese: Theoretische Informatik: eine umfassende Einführung. 2., erw. Auflage. Springer-Verlag, 2002, ISBN 3-540-42624-8, S. 27–28. 
• Gottfried Vossen, Kurt-Ulrich Witt: Grundkurs theoretische Informatik. Vieweg, 2006, ISBN 3834801534, S. 15 (online). 

Weblinks

• Grundbegriffe der formalen Sprache – Abschnitt „Wort“