Wort (Theoretische Informatik)

aus Wikipedia, der freien Enzyklopädie
(Weitergeleitet von Konkatenation (Wort))
Wechseln zu: Navigation, Suche

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 Informatik keine sprachliche Bedeutung. Es ist lediglich ein anderer Begriff für eine Zeichenkette.

Wörter oder Worte[1] sind die Elemente einer formalen Sprache. Sie sind deshalb wichtig für mathematische Modellierungen, für die Theorie der Programmiersprachen, für die Berechenbarkeitstheorie und andere Gebiete der theoretischen Informatik.

Definition[Bearbeiten | Quelltext bearbeiten]

Es sei ein gegebenes Alphabet und eine natürliche Zahl aus , der Menge der natürlichen Zahlen einschließlich der Null (). Ein Wort der Länge ist eine endliche Folge mit für alle .

Die Länge eines Wortes wird als notiert. Ein besonderes Wort ist das leere Wort, das aus keinem Symbol besteht (die Länge 0 besitzt) und meist mit dem griechischen Buchstaben (Epsilon) dargestellt wird. Die Menge aller Wörter, die man aus einem Alphabet bilden kann, ist die Kleenesche Hülle über diesem Alphabet, kurz .

Zur Angabe eines Wortes wird oft die vereinfachte Schreibweise 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 nicht angewendet werden, da hier zum Beispiel aus der Schreibweise nicht eindeutig hervorgeht, ob das Wort , oder gemeint ist.

Wörter der Länge können wie folgt aufgefasst werden:[2]

  • als -Tupel
  • als Folgen (da Tupel als Folgen aufgefasst werden können)
  • als Elemente des -fachen kartesischen Produktes (da Tupel so aufgefasst werden können)

Beispiele[Bearbeiten | Quelltext bearbeiten]

Es sei das Alphabet der lateinischen Buchstaben und . Dann sind die Wörter und Beispiele für Wörter über und ist ein Wort über . Man erkennt, dass und ist.

Operationen auf Wörtern[Bearbeiten | Quelltext bearbeiten]

Konkatenation[Bearbeiten | Quelltext bearbeiten]

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 und über einem Alphabet wird mit oder angegeben und ist definiert durch:

Dabei ist nach der Definition des Wortes und mit und für alle und . Nach der obigen Definition ist ein Präfix und ein Suffix des durch die Konkatenation entstandenen Wortes . Die Länge eines konkatenierten Wortes entspricht dabei der Summe der Längen der einzelnen (Teil-)Wörter. So gilt für jedes Wort und :

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

Da außerdem die Konkatenation assoziativ ist, bildet das Tripel aus der Menge aller Wörter über einem beliebigen Alphabet , 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:

Demgegenüber ist die Konkatenation nicht kommutativ, d. h. nicht für alle Wörter und gilt, dass ist. So ist zum Beispiel:

Potenz[Bearbeiten | Quelltext bearbeiten]

Die -te Potenz eines Wortes ist definiert als die -fache Konkatenation dieses Wortes mit sich selbst. Die Definition der Potenz wird meist rekursiv angegeben:

   (für )

So sind zum Beispiel:

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

Spiegelung[Bearbeiten | Quelltext bearbeiten]

Die Spiegelung oder das Reverse eines Wortes ergibt sich, wenn man rückwärts schreibt. Wenn also ist, so ist die endliche Folge mit und für alle . Die Länge eines Wortes ist also gleich der Länge seiner Spiegelung:

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

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:

Induktionsschritt:

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

Ein Wort wie , das identisch mit seiner Spiegelung ist, wird Palindrom genannt.

Präfix, Infix und Suffix[Bearbeiten | Quelltext bearbeiten]

Präfix[Bearbeiten | Quelltext bearbeiten]

Ein Präfix ist eine Hinzufügung am Anfang eines Wortes. Ein Präfix eines Wortes ist demnach jedes Infix , für das gilt, dass und für jedes ist. Demnach ist genau dann Präfix des Wortes , wenn es mindestens ein aus der Kleeneschen Hülle über dem Alphabet, aus dem erzeugt wurde, gibt, so dass ist:

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.

Beispiel[Bearbeiten | Quelltext bearbeiten]

Sei , so lauten die echten Präfixe für :

  • .

Infix[Bearbeiten | Quelltext bearbeiten]

Ein Infix ist eine Hinzufügung innerhalb eines Wortes. Jede endliche Teilfolge von aufeinander folgenden Symbolen eines Wortes wird Infix oder Teilwort des Wortes genannt. Ein Infix eines gegebenen Wortes ist demnach jedes Wort , für das es (mindestens) ein gibt, für das gilt, dass zum einen und zum anderen für jedes ist. Demnach ist ein Wort genau dann Infix eines Wortes , wenn gilt, dass es mindestens ein Wort und ein Wort aus der Kleeneschen Hülle über dem Alphabet von gibt, so dass ist:

So ist das Wort mit ein Infix der Wörter , und , nicht aber der Wörter , beziehungsweise des leeren Wortes .

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.

Suffix[Bearbeiten | Quelltext bearbeiten]

Ein Suffix, auch Postfix genannt, ist eine Hinzufügung am Ende eines Wortes. Ein Suffix eines Wortes ist nach der Definition des Infixes jedes Teilwort , für das gilt, dass es ein gibt, für das zum einen und zum anderen für jedes ist. Demnach ist ein Wort genau dann Suffix eines Wortes mit , wenn es mindestens ein gibt, so dass ist:

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.

Beispiel[Bearbeiten | Quelltext bearbeiten]

Sei , so lauten die echten Suffixe für :

  • .

Literatur[Bearbeiten | Quelltext bearbeiten]

  • John E. Hopcroft, Jeffry D. Ullman: Einführung in die Automatentheorie, formale Sprachen und Komplexitätstheorie. 3. korrigierte Auflage. Addison Wesley, Bonn u. a. 1994, ISBN 3-89319-744-3 (Internationale Computer-Bibliothek).
  • Katrin Erk, Lutz Priese: Theoretische Informatik. Eine umfassende Einführung. 2. erweiterte Auflage. Springer-Verlag, Berlin u. a. 2002, ISBN 3-540-42624-8, S. 27–28 (Springer-Lehrbuch).
  • Gottfried Vossen, Kurt-Ulrich Witt: Grundkurs theoretische Informatik. Eine anwendungsbezogene Einführung - für Studierende in allen Informatik-Studiengängen. 4. verbesserte und erweiterte Auflage. Vieweg, Wiesbaden 2006, ISBN 3-8348-0153-4, S. 15 (online).

Anmerkungen und Einzelnachweise[Bearbeiten | Quelltext bearbeiten]

  1. Gebräuchlich sind beide Pluralformen, vgl. z. B. dtv-Atlas zur Mathematik, Bd. I, ISBN 3-423-03007-0, S. 245 versus Bauer, Goos: Informatik. Bd. I, ISBN 3-540-06332-3, S. 28.
  2. Definition von Tupel und seine Synonyme: http://www.encyclopediaofmath.org/index.php/Tuple

Weblinks[Bearbeiten | Quelltext bearbeiten]