Leere Wort

Einführung

Das "leere Wort" in der Theorie formaler Sprachen und regulärer Grammatiken wird oft mit dem griechischen Buchstaben Epsilon (ε) oder manchmal auch mit dem Buchstaben Lambda (λ) dargestellt. Es bezeichnet eine Zeichenkette ohne Zeichen, also eine Zeichenkette von Länge 0.

Einige wichtige Eigenschaften und Aspekte des leeren Worts:

• Definition: Das leere Wort hat keine Zeichen. Das heißt, seine Länge ist genau 0.

• Konkatenation: Wenn man das leere Wort mit einem anderen Wort konkateniert (egal ob vorne oder hinten), bleibt das andere Wort unverändert. Das bedeutet: für jedes Wort w gilt: ε · w = w · ε = w.

• Potenz: Das leere Wort, hoch irgendeiner positiven Potenz, ist immer noch das leere Wort: ε^n = ε für alle n > 0.

• Nützlich in Definitionen: Das leere Wort wird oft in der Theorie der Automaten und der formellen Grammatiken verwendet. Zum Beispiel kann in einem nichtdeterministischen endlichen Automaten (NFA) ein Übergang existieren, der das leere Wort als Eingabe akzeptiert, was bedeutet, dass der Automat diesen Übergang nehmen kann, ohne ein Eingabesymbol zu lesen.

• Akzeptanz: In der Theorie der Automaten kann ein Automat entscheiden, das leere Wort zu akzeptieren. Wenn ein Automat direkt in einem Endzustand startet (ohne irgendeine Eingabe zu lesen), dann akzeptiert er das leere Wort.

Das Verständnis des leeren Worts ist wesentlich, wenn man sich mit formellen Sprachen, Grammatiken, regulären Ausdrücken und Automaten auseinandersetzt. Es spielt eine fundamentale Rolle in vielen Definitionen und Eigenschaften in diesem Bereich.

Beispiel

Stellen Sie sich einen Automaten mit zwei Zuständen vor: q0 und q1. q0 ist der Startzustand und q1 ist ein Endzustand. Es gibt einen Übergang von q0 zu q1, der das leere Wort akzeptiert. Da es sich um einen NFA handelt, ist ein solcher Übergang zulässig.

Hier ist eine textuelle Beschreibung des Automaten:

• Zustände: {q0, q1}

• Alphabet: {a, b} (wir könnten irgendein Alphabet wählen, aber für dieses Beispiel nehmen wir {a, b})

• Startzustand: q0

• Endzustände: {q1}

• Übergangsfunktion:

  • δ(q0, ε) = q1

  • Andere Übergänge können definiert oder ausgelassen werden, je nachdem, welche anderen Wörter außer ε Sie akzeptieren möchten.

Da es einen ε-Übergang von q0 zu q1 gibt, wird das leere Wort von diesem NFA akzeptiert, da er vom Startzustand direkt zum Endzustand übergehen kann, ohne irgendein Eingabesymbol zu lesen.

In grafischer Form wäre der Automat ein Diagramm mit zwei Kreisen (für die Zustände) und einem Pfeil von q0 zu q1 beschriftet mit ε.

Dies ist nur ein einfacher NFA, der das leere Wort akzeptiert. Es gibt unzählige Möglichkeiten, Automaten zu erstellen, die das leere Wort entweder alleine oder zusammen mit anderen Wörtern akzeptieren.

Leere Worte in einem DEA

Ein deterministischer endlicher Automat (DEA, auf Englisch: DFA - Deterministic Finite Automaton) unterscheidet sich von einem nichtdeterministischen endlichen Automaten (NFA) insofern, als dass er für einen gegebenen Zustand und ein gegebenes Eingabesymbol nur einen einzigen möglichen Übergang haben darf. Das bedeutet, dass im Falle eines DEA Übergänge aufgrund des leeren Wortes (ε-Übergänge) nicht zulässig sind. Somit spielen ε-Übergänge in der Definition und im Verhalten eines DEA keine direkte Rolle.

Allerdings spielt das leere Wort insofern eine Rolle, als dass ein DEA das leere Wort akzeptieren kann. Das geschieht, wenn der Startzustand gleichzeitig ein Endzustand ist. Ohne ein Symbol zu lesen, befindet sich der DEA bereits in einem akzeptierenden Zustand, und somit wird das leere Wort akzeptiert.

Ein Beispiel:

• Zustände: {q0}

• Alphabet: {a, b}

• Startzustand: q0

• Endzustände: {q0}

• Keine Übergangsfunktion definiert (oder sie könnte definiert werden, aber für dieses einfache Beispiel lassen wir sie weg).

Hier akzeptiert der DEA nur das leere Wort, weil er beim Start bereits in einem akzeptierenden Zustand ist und keine weiteren Zustände oder Übergänge definiert sind.

Zusammenfassend kann gesagt werden, dass, obwohl ε-Übergänge in einem DEA nicht vorkommen, das Konzept des leeren Wortes dennoch eine Rolle spielt, nämlich in Bezug darauf, ob der DEA das leere Wort akzeptiert oder nicht.