Theoretische Informatik

Nichtdeterministischer endlicher Automat mit Epsilon-Übergängen

 aufwärts

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 Übergangs­relation des nicht­deterministischen endlichen Automaten um solche Zustands­übergänge, sogenannte Epsilon-Übergänge.

 

Epsilon-Übergänge

Die Übergangs­relation eines nicht­deterministischen 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 nicht­deterministischen endlichen Automaten mit Epsilon-Übergängen einen normalen nicht­deterministischen endlichen Automaten ohne Epsilon-Übergänge gibt, der dieselbe Sprache erkennt, und umgekehrt. Die beiden Maschinen­modelle sind also äquivalent. Wir werden im Folgenden bei nicht­deterministischen endlichen Automaten Epsilon-Übergänge zulassen.

Formal ist die Übergangs­relation d eines nicht­deterministischen endlichen Automaten mit Epsilon-Übergängen definiert als

d  enthalten  ZkreuzA?kreuzZ

mit A? = A vereinigt {ε}.

Genau wie der normale nicht­deterministische endliche Automat erkennt ein nicht­deterministischer endlicher Automat 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 nicht­deterministischer endlicher Automat mit Epsilon-Übergängen dargestellt. Die Beschriftung des rot dargestellten Pfades enthält das Wort aba, somit erkennt der Automat dieses Wort.

Zustandsgraph eines nichtdeterministischen endlichen Automaten mit Epsilon-Übergängen
Bild 1:  Zustandsgraph eines nicht­deterministischen endlichen Automaten mit Epsilon-Übergängen

 

Epsilon-Hülle von Zuständen

Definition:  Sei N = (Z, A, d, q, F) ein nicht­deterministischer 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 Element Z  |  (s, ε, tElement d* }

wobei d* die auf Wörter erweiterte Übergangs­relation 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 enthalten Z ist

ε-hülle(M)   =   Vereinigung s Element M  ε-hülle(s)

 

Simulation eines nicht­deterministischen endlichen Automaten mit Epsilon-Übergängen

Die Simulation eines nicht­determistischen 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:

  1. 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.
  2. 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.

 

Epsilon-Übergang
Bild 2:  Epsilon-Übergang
Zustandsübergang bei gelesenem Zeichen a
Bild 3:  Zustands­übergang bei gelesenem Zeichen a
Zustandsübergang bei gelesenem Zeichen a
Bild 4:  Zustands­übergang bei gelesenem Zeichen a

 

Es folgt die formale Beschreibung des Verfahrens zur Simulation eines nicht­deterministischen endlichen Automaten.

  1. Initialisierung:
    1. Markiere den Startzustand;
    2. markiere alle Zustände, die mit Epsilon-Übergängen erreichbar sind (also die Epsilon-Hülle des Startzustands).
  2. Für jedes gelesene Eingabezeichen:
    1. Markiere alle Folgezustände unter dem Eingabezeichen;
    2. 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 nicht­deterministischen endlichen Automaten)

 

Übergangs­relation

Derselbe Automat ist hier durch seine Übergangs­relation dargestellt. Er kann in dieser Form hier ebenfalls simuliert werden. Bei nicht­deterministischer Wahlmöglichkeit ist dasjenige Tupel der Übergangs­relation anzuklicken, das den Zustands­übergang bewirken soll.

 

Eingabeband

 
 
 
 
 
 
 
 
 
 
 
 
 
Pfeil

Eingabewort

   

 

sas'
 2 a4
 2 ε0
 0 a1
 1 a1
 1 ε3*
 4 ε6
 4 ε5
 6 a7
 6 b7
 7 ε5
 7 ε4
 5 a3*

 

 

Weiter: [Äquivalenz von nichtdet. endl. Automaten ohne und mit Epsilon-Übergängen] oder  up del.icio.us digg.com Google Ma.gnolia Mister Wong StumbleUpon YahooMyWeb LinkARENA

 

homeH.W. Lang   FH Flensburg   lang@fh-flensburg.de   Impressum   ©   Created: 26.01.2008   Updated: 11.12.2012
Valid HTML 4.01 Transitional


Campus Flensburg

Informatik in Flensburg studieren...

 

Neues Studienangebot

Web- und Softwaretechnologie

 

Wir bieten Ihnen ein praxis­orientiertes Informatik-Studium mit Schwerpunkt auf modernsten Webtechnologien.

Sehen Sie sich einmal den Studienplan an.

 

Ihr Abschluss
nach 7 Semestern:
Bachelor of Science

 

Weitere Informatik-Studienangebote an der Fachhochschule Flensburg:

Medieninformatik Medieninformatik

Informations- und Kommunikationstechnik

Wirtschaftsinformatik