epsilonÜbergänge

Epsilon-Übergänge, auch ε-Übergänge genannt, sind Übergänge in Automaten, die mit dem Symbol ε beschriftet sind. Sie verbrauchen kein Eingabezeichen, das heißt, der Automat kann durch eine solche Kante wechseln, ohne ein Symbol aus dem Eingabealphabet zu lesen. Epsilon-Übergänge treten vor allem in nichtdeterministischen endlichen Automaten (NFA) auf, wo sie die Modellierung von optionalen oder zusammengefassten Teilmustern erleichtern, und in ε-NFAs, in denen sie die Grundbausteine der Sprachenmodellierung darstellen.

Formal lässt sich ein ε-NFA durch eine Zustandmenge Q, ein Eingabealphabet Σ, eine Übergangsfunktion δ, einen Startzustand q0 und eine Menge von Akzeptanzzuständen F definieren, wobei δ(q, a) eine Teilmenge von Q für jedes q ∈ Q und jedes Symbol a ∈ Σ ∪ {ε} ist. Ein Wort w wird akzeptiert, wenn es eine Folge von Zustandswechseln gibt, beginnend bei q0, die die gelesenen Symbole von w in der richtigen Reihenfolge verwendet und am Ende in einem Zustand aus F endet. ε-Übergänge können mehrfach auftreten und mit vielen unterschiedlichen Symbolen verbunden sein, was die NFA-Denormalisierung beeinflusst.

Die epsilon-Hülle (ε-Closure) eines Zustands oder einer Zustandsmenge beinhaltet alle Zustände, die ausschließlich über ε-Übergänge erreichbar sind. Damit lassen sich ε-Übergänge in einer Berechnung simulieren, ohne sie explizit zu verwenden. Ein gängiges Verfahren zur Elimination von ε-Übergängen besteht darin, für jeden Zustand die ε-Closure zu bestimmen, die Übergänge entsprechend anzupassen und schließlich ε-Übergänge zu entfernen. Das resultierende System ist ein äquivalentes NFA ohne ε-Übergänge; es kann weiter in einen DFA überführt werden, wobei die Potenzmengenbildung eine Rolle spielt.

Epsilon-Übergänge sind zentral in vielen Konstruktionsmethoden der formalen Sprachen, etwa bei der Thompson-Konstruktion für reguläre Ausdrücke, da sie eine kompakte Modellierung von Konstrukten mit optionalen Teilen ermöglichen. Sie erfordern jedoch Vorsicht bei der Effizienz, da sie zu einer Zustandsvergrößerung und erhöhter Nichtdeterministik führen können.