Leeres Wort
Das leere Wort ist ein Begriff aus der theoretischen Informatik, speziell dem Bereich der formalen Sprachen.
Das leere Wort ist dort jenes Wort über einem Alphabet Σ, bei dem die Folge von Symbolen aus Σ die Länge 0 besitzt, also aus keinem einzigen Symbol des Alphabets besteht. Das leere Wort wird meist durch ε dargestellt, in englisch-sprachiger Literatur/Software oft auch mit λ (dabei sei ε bzw. λ ∉ Σ).
Das leere Wort bildet bei der Verkettung von Wörtern zu neuen Wörtern das neutrale Element: Die Verkettung eines Wortes w mit dem leeren Wort und auch die Verkettung des leeren Worts mit einem Wort w ergeben wieder das Wort w: wε = εw = w.
Beispiele
- Sei Σ1 = {a, b}. Dann sind a, aa, aaa, b, bb, bbb und so weiter, aber auch alle Kombinationen der beiden Symbole wie zum Beispiel abaaabb oder bbba Wörter über Σ. Das Wort bei dem kein einziges Symbol aus Σ vorkommt (also weder ein a noch ein b), ist das leere Wort und wird (um es irgendwie kenntlich zu machen) durch ε dargestellt.
- Wollte man beispielsweise alle Wörter über dem Alphabet Σ2 = {a} aufzählen, so liegt es nahe wie folgt zu beginnen: ε, a, aa, aaa, aaaa und so weiter.
- Betrachten wir zwei Wörter aus Σ1: Es seien w1 = aaa und w2 = bb. Dann gilt für die Verkettung der beiden Wörter w1 und w2 (geschrieben einfach w1w2): w1w2 = aaabb. Entsprechend ist zum Beispiel w1ε = aaa, εw2 = bb und w1εw2 = w1w2 = aaabb.