Das leere Wort ist im Fachbereich Formale Sprachen der Theoretischen Informatik dasjenige Wort, das aus keinem einzigen Zeichen besteht.

Definition

---

Das leere Wort über dem Alphabet Σ ist eine Folge von Elementen aus Σ der Länge 0.

Schreibweise

---

Das leere Wort wird meist mit dem griechischen Buchstaben ε (Epsilon) dargestellt, in englischsprachiger Fachliteratur findet sich dafür aber auch der griechische Buchstabe λ (Lambda).

Merkmale

---

• |ε| = 0. Die Länge des leeren Wortes ist stets 0. Diese Eigenschaft folgt direkt aus der Definition („... eine Folge ^* der Länge 0.“).
• wε = εw = w. Das leere Wort bildet bei der Konkatenation von Wörtern das neutrale Element, sprich, die Verknüpfung eines beliebigen Wortes w mit ε ergibt stets wieder w.
• ε ∉ Σ. Das leere Wort ε ist niemals Element eines Alphabets Σ. Das würde der Definition widersprechen, die ε gerade als das Fehlen jeglicher Symbole aus Σ definiert.
• ε ∈ Σ*. Das leere Wort ε ist immer Element der Menge aller Wörter über einem Alphabet Σ. Ist Σ ein Alphabet, so bezeichnet Σ* die Menge aller Folgen von Symbolen aus Σ mit beliebiger Länge. Insbesondere ist also auch die Zeichenfolge der Länge 0, eben ε, enthalten.

Beispiele

---

1. Sei Σ₁ := {a, b} ein Alphabet. Dann sind beliebige Kombinationen der beiden Buchstaben – beispielsweise a, b, ab, aabbbaba – Wörter über Σ. Das Wort, das aus keinem einzigen Symbol besteht, ist das leere Wort und wird, um es sichtbar zu machen, durch ε dargestellt.
2. Wollte man alle Wörter über dem Alphabet Σ₂ := {a} aufzählen, so liegt es nahe, wie folgt zu beginnen: Σ* = {ε, a, aa, aaa, aaaa, ...}
3. w₁ := aaa und w₂ := bb seien zwei Wörter über dem Alphabet Σ₁ aus Beispiel 1.Dann gilt für die Verkettung w₁w₂ der beiden Wörter: w₁w₂ = aaabb = εw₁w₂ = w₁εw₂ = w₁w₂ε.

Spezielle Merkmale bei speziellen Anwendungen

---

• ^* = L. Betrachtet man die Äquivalenzklassen einer formalen Sprache L bezüglich der Nerode-Relation ~, so bildet ε stets eine Äquivalenzklasse, die exakt L entspricht. Demnach beträgt der Index von L bezüglich ~ stets mindestens 1, in Zeichen ind(L) ≥ 1. Daraus wiederum lässt sich folgern, dass ein Deterministischer endlicher Automat, der L akzeptiert, aus mindestens einem Zustand bestehen muss.
• ε-Übergänge in Nichtdeterministischen endlichen Automaten sind Argumentpaare (q, a) der Übergangsfunktion δ mit q ∈ Σ, a = ε. Ein solcher Übergang δ(q₁, ε) = q₂ bedeutet, dass der Automat seinen Zustand von q₁ nach q₂ ändern kann, ohne dass ein Zeichen eingegeben wird. ε-Übergänge sind damit die Grundlage des Nichtdeterminismus. Sie werden im Graphen als Kanten kenntlich gemacht, die mit einem ε beschriftet sind.

Formale Sprachen | Compilerbau