Theoretische Informatik

Äquivalenz von nichtdeterministischen endlichen Automaten ohne und mit Epsilon-Übergängen

 aufwärts

Es stellt sich die Frage, ob nicht­deterministische endliche Automaten mit Epsilon-Übergängen mehr können als normale nicht­deterministische endliche Automaten. Gibt es also eine Sprache, die von einem nicht­deterministischen endlichen Automaten mit Epsilon-Übergängen erkannt wird, aber nicht von einem normalen nicht­deterministischen endlichen Automaten? Die Antwort ist nein.

Konstruktion

Satz:  Zu jedem nicht­deterministischen endlichen Automaten mit Epsilon-Übergängen gibt es einen nicht­deterministischen endlichen Automaten ohne Epsilon-Übergänge, der dieselbe Sprache erkennt.

Beweis:  Wir formen einen gegebenen nicht­deterministischen endlichen Automaten mit Epsilon-Übergängen in einen normalen nicht­deterministischen endlichen Automaten um, indem wir alle Epsilon-Übergänge beseitigen, ohne dass sich die erkannte Sprache ändert.

Sei N = (Z, A, d, q, F) der gegebene nicht­deterministische endliche Automat mit Epsilon-Übergängen. Wir konstruieren hieraus einen normalen nicht­deterministischen endlichen Automaten N' in folgender Weise.

Zustands­menge Z, Eingabe­alphabet A und Startzustand q werden von N übernommen; neu erzeugt werden die Übergangs­relation d' und die Menge der Endzustände F'.

Die Übergangs­relation d' besteht jeweils aus Zustands­übergängen (r, a, t) mit a Element A, falls es in N Zustände s, s' gibt mit

(r, ε, sElement d*   und   (s, a, s'Element d   und   (s', ε, tElement d*

Die neuen Zustands­übergänge in d' ergeben sich also aus den Nicht-Epsilon-Übergängen aus d mit vor- und nach­geschalteten Ketten von Epsilon-Übergängen.

Diese Ketten von Epsilon-Übergängen dürfen auch die Länge 0 haben, d.h. zu den Zustands­übergängen in d' gehören insbesondere auch die Nicht-Epsilon-Übergänge (r, a, t) von d, denn es gilt mit s = r und s' = t:

(r, ε, rElement d*   und   (r, a, tElement d   und   (t, ε, tElement d*

Anders ausgedrückt enthält die Übergangs­relation d' alle Elemente der auf Wörter erweiterten Übergangs­relation d*, bei denen das jeweilige Wort die Länge 1 hat:

d'  =  { (r, w, tElement d*  |  |w| = 1 }

 

Somit enthält d' keine Epsilon-Übergänge, und wir haben d' gerade so konstruiert, dass wenn wir im Zustands­graphen von N mit dem Zeichen a vom Zustand r zum Zustand t kommen, dasselbe auch in N' gilt. Kommen wir umgekehrt im Zustands­graphen von N' mit dem Zeichen a von r nach t, so auch in N. Für nichtleere Wörter w Element A+ gilt daher: N' erkennt jedes Wort, das N erkennt, und umgekehrt.

Die von N und N' erkannten Sprachen sind also gleich, bis möglicher­weise auf das Wort ε.

In N können wir möglicher­weise vom Startzustand q mit dem Wort ε zu einem Endzustand t ≠ q gelangen, aber in N' natürlich nicht, weil N' keine Epsilon-Übergänge hat. Damit ε auch von N' erkannt wird, muss in diesem Fall der Startzustand q' auch zum Endzustand gemacht werden.

F'  =  geschweifte Klammer
F  vereinigt  {q}       falls   es existiert  t Element F:  (q, ε, tElement d*
F    sonst

Beispiel

Beispiel:  Gegeben sei der folgende nicht­deterministische endliche Automat N mit Epsilon-Übergängen (Bild 1a). Aus N wird ein äquivalenter nicht­deterministischer endlicher Automat N' ohne Epsilon-Übergänge konstruiert (Bild 1b).

Zunächst enthält die Übergangs­relation von N alle Nicht-Epsilon-Übergänge von N':

(1, a, 1) weil   (1, ε, 1) Element d* und (1, a, 1) Element d und (1, ε, 1) Element d*
(2, b, 3) weil   (2, ε, 2) Element d* und (2, b, 3) Element d und (3, ε, 3) Element d*

Hinzu kommen die folgenden weiteren Zustands­übergänge:

(0, a, 1) weil   (0, ε, 1) Element d* und (1, a, 1) Element d und (1, ε, 1) Element d*
(1, a, 2) weil   (1, ε, 1) Element d* und (1, a, 1) Element d und (1, ε, 2) Element d*
(1, b, 3) weil   (1, ε, 2) Element d* und (2, b, 3) Element d und (3, ε, 3) Element d*
(0, a, 2) weil   (0, ε, 1) Element d* und (1, a, 1) Element d und (1, ε, 2) Element d*
(0, b, 3) weil   (0, ε, 2) Element d* und (2, b, 3) Element d und (3, ε, 3) Element d*

Außerdem muss der Startzustand 0 zum Endzustand gemacht werden, weil vom Zustand 0 aus der Endzustand 2 über Epsilon-Übergänge erreicht werden kann.

Automat N mit Epsilon-Übergängen Zusätzlich hinzugekommene Zustandsübergänge
(a) (b)
Bild 1: Nichtdeterministische endliche Automaten N mit Epsilon-Übergängen (a) und N' ohne Epsilon-Übergänge (b)

 

Weiter mit:  [Konstruktion eines nichtdet. endl. Automaten aus einem regulären Ausdruck]   oder   up

 

homeH.W. Lang   Hochschule Flensburg   lang@hs-flensburg.de   Impressum   ©   Created: 16.10.2010   Updated: 13.05.2016
Valid HTML 4.01 Transitional


Campus Flensburg

Informatik in Flensburg studieren...

 

Neu gestaltetes Studienangebot:

Bachelor-Studiengang
Angewandte Informatik

mit Schwerpunkten auf den Themen Software, Web, Mobile, Security und Usability.

Ihr Abschluss
nach 7 Semestern:
Bachelor of Science

 

Ebenfalls ganz neu:

Master-Studiengang
Angewandte Informatik

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

Ihr Abschluss
nach 3 Semestern:
Master of Science

 

Weitere Informatik-Studienangebote an der Hochschule Flensburg:

Medieninformatik

Wirtschaftsinformatik