Wort (Theoretische Informatik)
aus Wikipedia, der freien Enzyklopädie
In der theoretischen Informatik, und dort in der Theorie der formalen Sprachen, bezeichnet ein Wort eine endliche Folge von Symbolen aus einem Alphabet. Dies schließt auch das leere Wort mit ein. Die Menge aller Wörter über einem Alphabet Σ wird häufig mit Σ * bezeichnet.
Beispielsweise sind haus und xyzzy Wörter über dem Alphabet der lateinischen Buchstaben und @##$@ ein Wort über dem Alphabet {@, #, $}.
Durch Aneinanderhängen zweier Wörter x und y entsteht ein neues Wort xy (manchmal auch 
), dies wird als Verkettung oder Konkatenation bezeichnet. Durch Verkettung von haus und xyzzy ergibt sich hausxyzzy. Die Verkettung ist nicht kommutativ, sondern assoziativ.
Die Länge | x | eines Worts x ist die Anzahl seiner (nicht notwendigerweise verschiedenen) Buchstaben. Die Länge des leeren Worts ist 0, die Länge von xyzzy ist 5.
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.
Siehe auch: Datenwort
