Theoretische Informatik
Nichtdeterministischer endlicher Automat mit Epsilon-Übergängen
Viele Zusammenhänge im Bereich der endlichen Automaten lassen sich leichter darstellen, wenn Zustandsübergänge auch ohne Einlesen eines Zeichens möglich sind. Wir erweitern daher die Übergangsrelation des nichtdeterministischen endlichen Automaten um solche Zustandsübergänge, sogenannte Epsilon-Übergänge.
Epsilon-Übergänge
Die Übergangsrelation eines nichtdeterministischen endlichen Automaten besteht aus Tupeln der Form (s, a, s') mit der Bedeutung, dass der Automat im Zustand s bei gelesenem Zeichen a den Folgezustand s' annehmen kann.
Wir erlauben nun zusätzlich Tupel der Form (s, ε, s'), d.h. der Automat kann vom Zustand s in den Zustand s' übergehen, ohne ein Zeichen zu lesen. Ein solcher Zustandsübergang wird als Epsilon-Übergang bezeichnet. Es zeigt sich, dass es zu jedem nichtdeterministischen endlichen Automaten mit Epsilon-Übergängen einen normalen nichtdeterministischen endlichen Automaten ohne Epsilon-Übergänge gibt, der dieselbe Sprache erkennt, und umgekehrt. Die beiden Maschinenmodelle sind also äquivalent. Wir werden im Folgenden bei nichtdeterministischen endlichen Automaten Epsilon-Übergänge zulassen.
Formal ist die Übergangsrelation d eines nichtdeterministischen endlichen Automaten mit Epsilon-Übergängen definiert als
d ⊆ Z × A? × Z
mit A? = A ∪ {ε}.
Genau wie der normale nichtdeterministische endliche Automat erkennt ein nichtdeterministischer endlicher Automat mit Epsilon-Übergängen ein Wort w, wenn es in seinem Zustandsgraphen einen Pfad vom Startzustand zu einem Endzustand gibt, dessen Beschriftung das Wort w enthält.
Beispiel: In Bild 1 ist ein nichtdeterministischer endlicher Automat mit Epsilon-Übergängen dargestellt. Die Beschriftung des rot dargestellten Pfades enthält das Wort aba, somit erkennt der Automat dieses Wort.
Bild 1: Zustandsgraph eines nichtdeterministischen endlichen Automaten mit Epsilon-Übergängen
Epsilon-Hülle von Zuständen
Definition: Sei N = (Z, A, d, q, F) ein nichtdeterministischer endlicher Automat. Die Menge aller Zustände, die von einem Zustand s durch Epsilon-Übergänge erreichbar sind, einschließlich des Zustands s selbst, wird als Epsilon-Hülle von s bezeichnet, d.h. es ist
ε-hülle(s) = { t ∈ Z | (s, ε, t) ∈ d* }
wobei d* die auf Wörter erweiterte Übergangsrelation des Automaten ist.
Beispiel: In dem Automaten aus Bild 1 (bzw. in dem Automaten aus der Visualisierung der Simulation) gilt beispielsweise
- ε-hülle(2) = {2, 0}
- ε-hülle(0) = {0}
- ε-hülle(7) = {7, 4, 5, 6}
Definition: Die Epsilon-Hülle einer Menge von Zuständen ist die Vereinigung aller Epsilon-Hüllen der einzelnen Zustände der Menge, d.h. für M ⊆ Z ist
ε-hülle(M) = 
s ∈ M ε-hülle(s)
Simulation eines nichtdeterministischen endlichen Automaten mit Epsilon-Übergängen
Die Simulation eines nichtdeterministischen endlichen Automaten mit Epsilon-Übergängen kann man sich wiederum als eine Art "Mensch-ärgere-dich-nicht"-Spiel vorstellen. Der Zustandsgraph des Automaten ist das Spielbrett. Zustände werden markiert, indem nach bestimmten Regeln Spielsteine auf die Felder gesetzt werden. Es gibt nur einen Spieler; dieser liest die Zeichen des zu untersuchenden Wortes w.
Zu Beginn der Simulation wird ein Spielstein auf den Startzustand gesetzt. Es folgen dann abwechselnd zwei Arten von Zügen:
- Spielsteine, die einen Epsilon-Übergang machen können, werden geklont. D.h. wenn ein Feld, auf dem ein Spielstein steht, durch einen Epsilon-Übergang mit einem freien Feld verbunden ist, so wird auch auf das freie Feld ein Spielstein gesetzt (Bild 2). Dieser Schritt wird so lange wiederholt, wie er anwendbar ist. Es wird also die gesamte Epsilon-Hülle des ursprünglichen Feldes mit Spielsteinen besetzt.
- Wird das Zeichen a gelesen, so rücken alle Spielsteine, die einen Übergang mit dem Zeichen a machen können, auf das entsprechende Feld vor. Spielsteine, die auf mehrere Felder vorrücken können, werden geklont (Bild 3). Alle Spielsteine, die keinen Übergang mit dem Zeichen a machen können, werden entfernt (Bild 4).
Das Spiel ist "gewonnen", wenn nach Zug a) ein Spielstein auf einem Endzustand steht. Der Automat hat dann das Wort w, das aus der Folge der bis hierhin gelesenen Zeichen besteht, erkannt.
Bild 2: Epsilon-Übergang
Bild 3: Zustandsübergang bei gelesenem Zeichen a
Bild 4: Zustandsübergang bei gelesenem Zeichen a
Es folgt die formale Beschreibung des Verfahrens zur Simulation eines nichtdeterministischen endlichen Automaten.
- Initialisierung:
- Markiere den Startzustand;
- markiere alle Zustände, die mit Epsilon-Übergängen erreichbar sind (also die Epsilon-Hülle des Startzustands).
- Für jedes gelesene Eingabezeichen:
- Markiere alle Folgezustände unter dem Eingabezeichen;
- markiere alle Zustände, die mit Epsilon-Übergängen erreichbar sind (also die Epsilon-Hülle dieser Folgezustände).
Ist am Ende ein Endzustand markiert, so hat der Automat das Eingabewort erkannt.
Visualisierung der Simulation
Dieses Verfahren kann im Folgenden durchgespielt werden. In dem angegebenen Zustandsgraphen des Automaten sind Epsilon-Übergänge als Kanten ohne Beschriftung dargestellt.
(Java-Applet zur Simulation eines nichtdeterministischen endlichen Automaten)
Übergangsrelation
Derselbe Automat ist hier durch seine Übergangsrelation dargestellt. Er kann in dieser Form hier ebenfalls simuliert werden. Bei nichtdeterministischer Wahlmöglichkeit ist dasjenige Tupel der Übergangsrelation anzuklicken, das den Zustandsübergang bewirken soll.
Weiter mit: [Äquivalenz von nichtdet. endl. Automaten ohne und mit Epsilon-Übergängen] oder [up]
H.W. Lang mail@hwlang.de Impressum Datenschutz
Created: 26.01.2008 Updated: 16.02.2023
Diese Webseiten sind während meiner Lehrtätigkeit an der Hochschule Flensburg entstanden