Theoretische Informatik

Nichtdeterministischer endlicher Automat mit Epsilon-Übergängen

 aufwärts

Viele Zusammen­hä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 in  Z × A? × Z

mit A? = A vereinigt {ε}.

Genau wie der normale nicht­deterministische endliche Automat erkennt ein nicht­deterministischer endlicher Automat mit Epsilon-Übergängen ein Wort w, wenn es in seinem Zustands­graphen 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 dar­gestellten Pfades enthält das Wort aba, somit erkennt der Automat dieses Wort.

Bild 1: Zustandsgraph eines nichtdeterministischen endlichen Automaten mit Epsilon-Übergängen
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 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 in Z ist

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

Simulation eines nichtdeterministischen endlichen Automaten mit Epsilon-Übergängen

Die Simulation eines nicht­deterministischen endlichen Automaten mit Epsilon-Übergängen kann man sich wiederum als eine Art "Mensch-ärgere-dich-nicht"-Spiel vorstellen. Der Zustands­graph 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 unter­suchenden 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üng­lichen 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.

 

Bild 2: Epsilon-Übergang
Bild 2: Epsilon-Übergang
Bild 3: Zustandsübergang bei gelesenem Zeichen a
Bild 3: Zustandsübergang bei gelesenem Zeichen a
Bild 4: 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 Start­zustands).
  2. Für jedes gelesene Eingabe­zeichen:
    1. Markiere alle Folge­zustände unter dem Eingabe­zeichen;
    2. markiere alle Zustände, die mit Epsilon-Übergängen erreichbar sind (also die Epsilon-Hülle dieser Folge­zustände).

Ist am Ende ein Endzustand markiert, so hat der Automat das Eingabewort erkannt.

Visualisierung der Simulation

Dieses Verfahren kann im Folgenden durch­gespielt werden. In dem angegebenen Zustands­graphen 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 Übergangs­relation dargestellt. Er kann in dieser Form hier ebenfalls simuliert werden. Bei nicht­deterministischer Wahl­mö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 mit:  [Äquivalenz von nichtdet. endl. Automaten ohne und mit Epsilon-Übergängen]   oder   up

 

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


Campus Flensburg

Informatik in Flensburg studieren...

 

Neues Studienangebot:

Web- und Softwaretechnologie

Ein praxis­orientiertes Informatik-Studium mit Schwerpunkt auf modernsten Webtechnologien...

Ihr Abschluss
nach 7 Semestern:
Bachelor of Science

 

Und ganz neu:

Master-Studiengang
Angewandte Informatik

Ein projektorientiertes Studium auf höchstem Niveau mit den Schwerpunkten IT-Sicherheit, Mobile Computing und Human-Computer Interaction...

Ihr Abschluss
nach 3 Semestern:
Master of Science

 

Weitere Informatik-Studienangebote an der Fachhochschule Flensburg:

Medieninformatik Medieninformatik

Informations- und Kommunikationstechnologie

Wirtschaftsinformatik