Das Kefk Network Wiki befindet sich im Testbetrieb.

---

Aus Kefk.

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

Inhaltsverzeichnis 1 Definition 2 Schreibweise 3 Merkmale 4 Beispiele 5 Spezielle Merkmale bei speziellen Anwendungen

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 Element jeder Kleeneschen Hülle über ein beliebiges Alphabet Σ. Die Kleenesche Hülle Σ* ist definiert als die Menge aller Wörter endlicher Länge, welche sich aus den Symbolen des Alphabets Σ zusammensetzen.

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.

Dieses Dokument entstammt in seiner ersten oder einer späteren Version der deutschsprachigen Wikipedia. Es ist dort zu finden unter dem Stichwort Leeres_Wort, 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.