Leeres Wort

aus Wikipedia, der freien Enzyklopädie

Du hast neue Nachrichten auf deiner Diskussionsseite.

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

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.
Wollte man alle Wörter über dem Alphabet Σ₂ := {a} aufzählen, so liegt es nahe, wie folgt zu beginnen: Σ* = {ε, a, aa, aaa, aaaa, ...}
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.