Präfix (Theoretische Informatik)

Präfix (Theoretische Informatik)

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.

Inhaltsverzeichnis

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 Σ1 und Σ2 zwei Alphabete gegeben, wobei Σ1 das Alphabet der lateinischen Buchstaben und \Sigma_{2} = \lbrace \diamondsuit,\, \heartsuit,\, \spadesuit,\, \clubsuit \rbrace ist. Dann sind die Wörter w1 = haus und w2 = xyzzy Beispiele für Wörter über Σ1 und w_{3} = \heartsuit \clubsuit \clubsuit \heartsuit \spadesuit ist ein Wort über Σ2. Man erkennt, dass | w1 | = 4 und | w2 | = | w3 | = 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 wn ist definiert als die n-fache Konkatenation dieses Wortes mit sich selbst. Die Definition der Potenz wird meist rekursiv angegeben:

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

So sind zum Beispiel:

xyzzy0 = ε
\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 wR 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 wR diejenige endliche Folge (y_{1},\, y_{2},\, y_{3}, ...\, y_{k}) mit n = k und xi = yk − (i + 1) für alle i \in \lbrack 1, k \rbrack. Die Länge eines Wortes ist somit gleich der Länge seiner Spiegelung:

| wR | = | w |

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

εR = ε
abbR = 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 xj + i = yj 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 xj = yj 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 xj + i = yj 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


Wikimedia Foundation.

Schlagen Sie auch in anderen Wörterbüchern nach:

  • Infix (Theoretische Informatik) — 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… …   Deutsch Wikipedia

  • Suffix (Theoretische Informatik) — 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… …   Deutsch Wikipedia

  • Wort (Theoretische Informatik) — In der theoretischen Informatik ist ein Wort eine endliche Folge von Symbolen eines Alphabets. Im Gegensatz zur natürlichsprachlichen Bedeutung von Wörtern, die stets eine eigenständige Bedeutung haben, hat ein Wort in der theoretischen… …   Deutsch Wikipedia

  • Präfix (Begriffsklärung) — Präfix steht für: in der Linguistik ein sprachlicher Baustein, der vor dem Wortstamm angehängt wird, siehe Präfix ein Vorsatz für eine Maßeinheit, siehe Vorsätze für Maßeinheiten in der Theorie formaler Sprachen eine Folge von führenden Symbolen… …   Deutsch Wikipedia

  • PS-Regel — Eine Produktionsregel (auch Regel oder Produktion genannt) ist ein geordnetes Paar (P,Q) der beiden Wörter P und Q, welches besagt, dass bei der Erzeugung einer formalen Sprache aus einer gegebenen formalen Grammatik mit dieser Produktionsregel… …   Deutsch Wikipedia

  • Phrasenstrukturregel — Eine Produktionsregel (auch Regel oder Produktion genannt) ist ein geordnetes Paar (P,Q) der beiden Wörter P und Q, welches besagt, dass bei der Erzeugung einer formalen Sprache aus einer gegebenen formalen Grammatik mit dieser Produktionsregel… …   Deutsch Wikipedia

  • Produktion (Grammatik) — Eine Produktionsregel (auch Regel oder Produktion genannt) ist ein geordnetes Paar (P,Q) der beiden Wörter P und Q, welches besagt, dass bei der Erzeugung einer formalen Sprache aus einer gegebenen formalen Grammatik mit dieser Produktionsregel… …   Deutsch Wikipedia

  • Konkatenation (Wort) — 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… …   Deutsch Wikipedia

  • Potenz (Wort) — 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… …   Deutsch Wikipedia

  • 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… …   Deutsch Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”