Das Kefk Network Wiki befindet sich im Testbetrieb.

---

Aus Kefk.

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 die Länge 0 besitzt (aus keinem Symbol besteht) und meist mit dem griechischen Buchstaben ε dargestellt wird.

Formal lässt sich die Menge der Wörter über einem Alphabet Σ als das freie Monoid mit Basis Σ definieren. Die Verknüpfung des Monoids ist die Verkettung und das leere Wort ist das neutrale Element. Die Länge eines Worts ist ein Monoidmorphismus in die additive Gruppe der ganzen Zahlen, der mit Hilfe der universellen Eigenschaft des freien Monoids durch definiert werden kann.

Die Menge aller Wörter, welche man aus einem Alphabet Σ bilden kann, wird die Kleenesche Hülle über dieses Alphabet genannt und mit Parser-Fehler (Unbekannter Fehler\ast): \Sigma^\ast

bezeichnet. Wörter bilden außerdem die Elemente einer formalen Sprache, welche als die Teilmenge der Kleeneschen Hülle über ein gegebenes Alphabet definiert ist.

Inhaltsverzeichnis 1 Formale Definition 2 Beispiele 3 Rechenoperationen 3.1 Konkatenation 3.2 Potenz 4 Literatur

Formale Definition

Es sei Σ ein gegebenes Alphabet und n eine natürliche Zahl mit , wobei die Menge der natürlichen Zahlen einschließlich der Null bezeichnet . Ein Wort w ist eine endliche Folge mit für alle . Bei der Definition eines Wortes, wird diese Folge von Symbolen oft vereinfacht angegeben, indem die Schreibweise benutzt wird. Wie bereits erwähnt ist die natürliche Zahl n die Länge des Wortes w.

Beispiele

Es seien mit Σ₁ und Σ₁ zwei Alphabete gegeben, wobei Σ₁ das Alphabet der lateinischen Buchstaben und ist. Dann sind zum Beispiel w₁ = haus und w₂ = xyzzy Wörter über Σ₁ und ist ein Wort über Σ₂. Man erkennt, dass | w₁ | = 4 und | w₂ | = | w₃ | = 5 ist.

Rechenoperationen

Konkatenation

Die Konkatenation oder Verkettung ist eine Verknüpfung zweier Wörter zu einen neuem Wort, welche sich aus dem Aneinanderhängen der beiden Symbolfolgen ergibt. Die Konkatenation der beiden Wörter x und y über ein Alphabet Σ (Parser-Fehler (Unbekannter Fehler\ast): x,y \in \Sigma^\ast ) wird mit xy oder angegeben und ist definiert durch:

Dabei ist nach der Definition des Wortes und mit und für alle und .

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

Die Konkatenation ist assoziativ, aber nicht kommutativ. So ist zum Beispiel:

aber:

Potenz

Die Potenz eines Wortes wⁿ ist definiert als eine n-fache Konkatenation dieses Wortes mit sich selber. Die Definition der Potenz wird meist rekursiv angegeben:

w⁰: = ε

So sind zum Beispiel:

xyzzy⁰ = ε

Literatur

• U. Hedtstück: Einführung in die Theoretische Informatik - Formale Sprachen und Automatentheorie. Oldenbourg Verlag, München 2000, ISBN 3-486-25515-0

Dieses Dokument entstammt in seiner ersten oder einer späteren Version der deutschsprachigen Wikipedia. Es ist dort zu finden unter dem Stichwort Wort_%28Theoretische_Informatik%29, die Liste der bisherigen Autoren befindet sich in der Versionsliste; die Originalfassung kann dort auch bearbeitet werden. Alle Texte der Wikipedia und ihre Derivate stehen unter der GNU-Lizenz für freie Dokumentation.