Leeres Wort

aus Wikipedia, der freien Enzyklopädie

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

[Bearbeiten] Definition

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

[Bearbeiten] 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).

[Bearbeiten] 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.

[Bearbeiten] 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₂ε.

[Bearbeiten] 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.