Automat mit Epsilon übergang

mithrawnuruodo
Erstie
Erstie
Beiträge: 22
Registriert: 4. Sep 2009 00:03

Automat mit Epsilon übergang

Beitrag von mithrawnuruodo »

Hallo,

ich bin mir nicht sicher ob diese Frage schon gestellt wurde hab zumindest bei der Suche nichts gefunden. Wie man am Titel vielleicht schon sieht geht es um die Frage ob Epsilon Übergänge im Graphen erlaubt sind. Wobei ich mit Epsilonübergang jetzt einfach einen Übergang mein der ohne Eingabe stattfindet. Zu einigen regulären Ausdrücken kann man so nämlich (finde ich zumindest) einfacher und schneller einen zugehörigen Automaten konstruieren.
Beispiel wäre foglende Sprache.

\(\begin{equation}
L(A)=\left(b+(b+a)^* aa \right)^*
\end{equation}\)


Im Anhang habe ich ein Bild von einem Graphen eingefügt der diese Sprache mit Hilfe von Epsilonübergängen Beschreibt. Ich bin relativ sicher dass es stimmt blos nicht sicher ob man das in der Klausur auch so machen dürfte. Ansonsten es gibt doch bestimmt eine einfache Methode den Automaten mit Epsilonübergänge in einen ohne umzuwandeln? (Die rot markierten Zustände sind übrigens die bei der aktuellen Eingabe aktiven Zustände wobei die aktuelle Eingabe das Wort b war)
eps.png
eps.png (21.03 KiB) 1161 mal betrachtet

Tobias
BASIC-Programmierer
BASIC-Programmierer
Beiträge: 132
Registriert: 20. Okt 2004 14:17
Kontaktdaten:

Re: Automat mit Epsilon übergang

Beitrag von Tobias »

mithrawnuruodo hat geschrieben:ob Epsilon Übergänge im Graphen erlaubt sind.
Das hängt von der verwendeten Definition ab. Prinzipiell kann man natürlich Epsilon-Übergänge in Automaten haben. Die Frage ist nur, ob man das auch will.
mithrawnuruodo hat geschrieben:ob man das in der Klausur auch so machen dürfte.
Wenn es in der Vorlesung oder Übung behandelt wurde, könnte man das vermuten. Frag aber besser direkt beim Assistenten nach.
mithrawnuruodo hat geschrieben:Ansonsten es gibt doch bestimmt eine einfache Methode den Automaten mit Epsilonübergänge in einen ohne umzuwandeln?
Notfalls geht immer Potenzmengenkonstruktion.
Wise people talk, because they have something to say; fools, because they have to say something. (Plato)

mithrawnuruodo
Erstie
Erstie
Beiträge: 22
Registriert: 4. Sep 2009 00:03

Re: Automat mit Epsilon übergang

Beitrag von mithrawnuruodo »

Okay dann werde ich mal den Assistent anschreiben. Potzenmengenkonstruktion ist prinzipiell gut. Ich meine ja klar ist ein NFA und den könnte ich dann in einen DFA umwandeln. Aber mir istn icht so ganz klar wie ich dabei die Epsilon-Übergänge zu behandeln habe. Allgemein ist das ja wieder man geht her und bastelt diese Tabelle in der die Transtionen beschrieben werden. Aber was würde denn dann bitte in der Zeile für den Zustand q0 aus meinem Graphen stehen ?

Tobias
BASIC-Programmierer
BASIC-Programmierer
Beiträge: 132
Registriert: 20. Okt 2004 14:17
Kontaktdaten:

Re: Automat mit Epsilon übergang

Beitrag von Tobias »

mithrawnuruodo hat geschrieben:Aber mir istn icht so ganz klar wie ich dabei die Epsilon-Übergänge zu behandeln habe.
Nehmen wir mal an, dass sich dein Automat gerade im Zustand q5 befindet. Ohne Eingabezeichen zu verbrauchen, können wir nach q0, q1 oder q2 wechseln. Wir folgen also einfach so weit wie möglich den Epsilon-Kanten und merken uns die erreichbaren Knoten. Daraus erhalten wir die Epsilon-Hülle eines Knotens.

Konstruieren wir damit einen DEA:
  • Wir beginnen mit dem Startzustand q0. Erreichbar sind aber alle Knoten aus der Epsilon-Hülle {q0, q1, q2}, also wird das der Startzustand im zu konstruierenden Automaten. q0 ist akzeptierend, also ist auch der neue Zustand akzeptierend.
  • Lesen wir ein b, können wir von q1 nach q3 wechseln oder auf q2 bleiben. Der Folgezustand wäre also normalerweise {q2, q3}. Durch die Epsilon-Kanten können wir aber auch weiter von q3 über q0 zu q1 und q2, die Epsilon-Hülle ist also {q0, q1, q2, q3}. Das wird der Folgezustand bei Eingabe von b. q1 und q3 sind akzeptierend, also auch der neue Zustand.
  • Lesen wir ein a, können wir auf q2 bleiben oder von q2 nach q4 wechseln. Der Folgezustand wäre also normalerweise {q2, q4}. Ausgehende Epsilon-Kanten gibt es diesmal nicht, die Epsilon-Hülle ist also ebenfalls {q2, q4}. Das wird der Folgezustand bei Eingabe von a. Keiner dieser Zustände ist akzeptierend, also auch nicht der neue Zustand.
Und so weiter, bis der Automat fertig ist.

Der wesentliche Unterschied zur "normalen" Potenzmengenkonstruktion ist also nur, dass immer die Epsilon-Hüllen der erreichbaren Zustände betrachtet werden. Etwas ausführlicher findest du das in Einführung in die Automatentheorie, Formale Sprachen und Komplexitätstheorie von Hopcroft, Motwani und Ullman.

Das Problem an der Sache ist nur, dass die so konstruierten Automaten im schlimmsten Fall 2^n Knoten haben können. Durch die vielen Epsilon-Kanten und zugehörigen Knoten wird das auch nicht besser. Unter Klausurstress kann das fatale Folgen haben ... Hier im Beispiel könnte man sich noch überlegen, direkt den Pfad q0,q1,q3,q0 durch eine Schleife von q0 nach q0 bei Eingabe b zu ersetzen, also falls möglich die durch Epsilon-Kanten verbundenen Knoten zu vereinigen und die Kanten entsprechend zu verbiegen. Dieses "scharfe Hinsehen" ist allerdings auch nicht jedermanns Sache ...
Wise people talk, because they have something to say; fools, because they have to say something. (Plato)

Antworten

Zurück zu „Archiv“