Leeres Wort

Das leere Wort ist ein Begriff aus der Informatik, speziell dem Bereich der formalen Sprachen, die vor allem in der Berechenbarkeitstheorie und dem Compilerbau betrachtet werden.

Ein Wort über einem Alphabet ist eine endliche Folge von Symbolen aus diesem Alphabet. Dabei ist ein Alphabet einfach eine endliche Menge von Symbolen und endlich bedeutet hier, dass dieses Alphabet nur endlich viele (und nicht unendliche viele) Symbole enthält. Man kann sich ein Alphabet also wie ein normales Alphabet vorstellen, beispielsweise das der deutschen Sprache.

Das ein Wort eine endliche Folge von Symbolen ist, bedeutet, dass diese Folge abbricht, es also nur endlich viele (und nicht unendliche viele) Glieder in dieser Folge gibt. Anschaulich kann man sich ein Wort also wie ein normales geschriebenes Wort vorstellen.

Es gibt dabei einen Spezialfall, das sogenannte leere Wort, bei dem die Folge der Symbole die Länge 0 besitzt. Dieses wird meist durch $\epsilon$ symbolisiert.

Man kann solche Wörter verketten, d.h. in beliebiger Reihenfolge hinereinander schreiben und so neue Wörter bilden. Das leere Wort ist dabei das neutrale Element bezüglich der Verkettung, d.h. die Verkettung eines Wortes mit dem leeren Wort ist das Wort selbst.

Beispiele

Wir betrachten das Alphabet $\{a,b,c\}$. Dann sind $abcab$ und $aaabbb$ zum Beispiel Wörter über diesem Alphabet. $abcdef$ ist kein Wort über diesem Alphabet, da $d$, $e$ und $f$ nicht im Alphabet vorkommen.

Die Verkettung der Wörter $aaa$ und $bbbcc$ (in dieser Reihenfolge) ergibt dann das Wort $aaabbbcc$. Die Verkettung von $aaabb$ mit $\epsilon$ ergibt $aaabb$.