Anleitung zu Cetacea
Übersicht
1) Vorwort
Das Programm Cetacea wurde als Veranschaulichung des Determiniserungs und Minimierungsalgorithmus für "deterministische ednliche Automaten" (DEA) der in dem Kurs "Theoretische Informatik und Logik" an der Technischen Universität Wien vorgestellt wurde.
Wenn sie kein Wissen über endliche Automaten haben könnten die folgenden Links hilfreich bei der Verwendung des Programms sein (auf Englisch):
Deterministische endliche Automaten,
Nichtdeterministische endliche Automaten
Wissen über reguläre Sprachen kann ebenfalls nützlich sein.
2) Das Benutzerinterface
Buttons zum erstellen eines Automaten:
Mit diesem Button kann ein Initialzustand plaziert werden, es wird in jedem Automaten ein, und zwar genau ein, Initialzustand benötigt (dieser kann allerdings gleichzeitig auch ein Endzustand sein). Dieser Button wird folgend als "Startbutton" bezeichnet.
Mit diesem Button kann ein Start/End Zustand plaziert werden. Folgend wird dieser Button "Start/Endbutton" genannt.
Mit diesem Button kann ein Endzustand plaziert werden, ein Automat benötigt nicht zwingend einen Endzustand, es können allerdings beliebig viele plaziert werden. Folgend wird dieser Button als "Endbutton" bezeichnen.
Mit diesem Button kann ein "normaler" Zustand plaziert werden, er hat keine besonderen Eigenschaften. Es können beliebig viele plaziert werden. Folgend wird dieser Button als "Defaultbutton" bezeichnet.
Mit diesem Button kann eine Kante plaziert werden, Kanten beschreiben Zustandsübergänge und bestimmen ob ein Automat deterministisch ist oder nicht. Folgend wird dieser Button als "Kantenbutton" bezeichnet.
Statusbezeichnung: Es wird der aktuelle "Status" (NEA, DEA, Undefiniert) des Automaten angezeigt.
- DEA: Der Automat ist im Moment deterministisch.
- NFA: Der Automat ist im Moment nichtdeterministisch und kann determinisiert werden.
- Undefiniert: Der Automat hat keinen Initialzustand und ist deswegen undefiniert.
determinisieren Button: Drücken dieses Buttons startet das determinisieren des Automaten.
layout Button: Versucht den Automaten so anzuordnen das er relativ gut anzusehen ist, nicht alle Resultate sind optimal, meistens sollte das Ergebnis allerdings relativ gut sein. Probleme bestehen im Moment noch falls ein Zustand keine Kanten (werder ein noch ausgehend) besitzt oder wenn alle Kanten von einem Zustand ausgehen. (Für die Interessierten, verwendet wird ein Kräfte basierender Algorithmus).
3) Erstellen und editieren eines Automaten
Erstellen:
Zustände können plaziert werden indem man zuerst einen der Buttons auswählt mit denen man Zustände plazieren kann, und dann auf die "Zeichenfläche" clickt, der neue Zustand wird nun an der angeklicketen Stelle erscheinen. (Der Modus zum setzen von Zuständen wird durch plazieren eines Zustandes beendet).
Um eine Kante zu erstellen clickt man zuerst auf den "Kantenbutton" und dann auf einen Zustand bei dem man will das die Kante beginnt, dannach auf den zweiten Zustand zu dem die Kante führen soll (Start und Endzustand können gleich sein). Dieser Modus wird nicht durch das plazieren einer Kante beendet.
Um generell den aktuellen Plaziermodus zu beenden (also entweder Kanten oder Zustandsmodus) einfach die rechte Maustaste drücken.
Editieren:
Um den Namen eines Zustands zu ändern muss zuerst jeder Plaziermodus beendet werden, danach kann mit einem Doppelclick auf den Zustand dessen Name geändert werden. Die Namen der Zustände sind eindeutig. Zulässige Namen sind folgende: [a-z,A-Z,0-9]+
Um den Wert einer Kante (bzw. Zustandsübergang) zu editieren, clickt man doppelt auf die Kante und gibt die Werte ein, diese sind separiert durch Kommata. Falls der Leerstring (epsilon) enthalten werden soll, müssen zwei Kommas verwendet werden (zB: a,,).
Knoten und Kanten können nachdem sie selektiert wurden, durch das drücken der Entfernen Taste gelöscht werden.
4) Determinisieren
Wie der Determinisierungsalgorithmus funktioniert
Ich werde nun Anhand eines Beispiels illustrieren wie der Algorithmus zum determinisieren funktioniert und wie das Programm zu bedienen ist.
Wir starten nun mit diesem einfachen Automaten der sich aber gut zur Illustation des Algorithmus eignet.
Am besten verwendet man diesen Link um den beispielautomaten zu laden: Determinisierungsbeispiel
Wenn man nun auf den Button "determinize" clickt, bekommt man zusätzlich die übergangstabelle (Transition table) des Automaten angezeigt. Diese sieht wie folgt aus:
Der erste Schritt besteht nun darin die erweiterte übergangstabelle (ETT) zu berechnen.
Diese stellt einen Zwischenschritt dar, sie besitzt schon keine Epsilonübergänge mehr, besitzt aber noch nicht alle nötigen Zustände und Zustandsübergänge. Ihr Initialzustand ist mit allen (nicht Epsilon) übergängen der normalen übergangstabelle gefüllt.
Nun wollen wir die ETT Schritt für Schritt berechnen. Dazu gibt es die Toolbar auf der rechten Seite.
Mit ihr kann man jeweils einen Schritt weiter (->) bzw einen Schritt zurück (<-) gehen, sollte man schon genug gesehen haben kann man auf den Button "End" drücken um die Determinisierung abzuschließen.
Wie entsteht nun die ETT?
Es wird von jedem Zustand ausgehen überprüft welche anderen Zustände erreicht werden können wenn dabei nur ein Symbol "verbraucht" wird. Alle die man mit diesem einen Symbol erreicht werden können, werden in die passende Spalte eingetragen, und der neueste Eintrag wird farblich hervorgehoben. Zb. kann in unserem Beispiel der Zustand p0 über das Symbol 0 sowohl sich selbst, als auch die Zustände p1 und p2 erreichen.
p0 ~0~> p0 ~E~> p1 ~E~> p2 | In Worten: Der Weg geht zuerst über die Kante die wieder zu p0 führt, dann über die Epsilon (E) Kante die zu p1 führt und dann mit der E-Kante nach p2.
Die ETT die diesen Fall gerade darstellt (Plus einiger vorhergehender) sieht folgendermaßen aus:
Nachdem die ETT nun fertig gestellt wurde, wird die übergangstabelle des determinisierten Automaten (DTT) erstellt.
Dabei werden zuerst alle sich unterscheidenden "Zustandskombinationen" die in der ETT zu finen sind als neue Zustände in der DTT eingetragen.
Der Zustand {p1} ist im Gegenteil zu {p2} nicht zu finden. Das liegt daran das {p1} die gleichen Zustandsübergänge wie der Zustand {p1,p2} hat, und in diesem auch enthalten ist, und deswegen von diesem "verschluckt" wird.
Die Zustandsübergänge der neuen Zustände sind nun einfach eine Kombination der übergänge der in diesem Zustand enthaltenen Zustände. Sollte dabei eine neue Kombination entstehen, die selbst noch kein Zustand ist, wird dieser auch in der Liste der Zustände erscheinen. Im ETT werden die "Zustandszeilen" die zusammengefasst werden farblich hinterlegt, während im DTT die gerade befüllte Zelle farblich hervorgehoben wird.
{p0,p1,p2} enthält somit alle Zustandsübergänge der Zustände p0,p1 und p2 aus der ETT. Gleiche übergänge werden dabei zusammengefasst.
{p0} unterscheidet sich nicht von {p0,p1,p2} wieso wird er nicht verschluckt?
Das liegt daran das {p0} der alte (und auch neue) Initialzustand ist und deswegen immer seperat hinzugefügt wird.
Jeder neue Zustand der einen der alten Endzustände enthält, also im Beispiel p2, wird im neu erstellten Automaten wieder ein Endzustand sein.
Die fertige DTT sieht folgendermaßen aus:
Jetzt drücken wir auf "End" und der determinisierte Automat wird erstellt.
5) Troubleshooting / Bugs
Mir selbst ist passiert das ich die Zustände und Kanten nicht umbenennen konnte nach einem neuladen der Seite. Ein update der Java RE auf 1.6.0_16 hat dieses Problem behoben, hier kann die aktuellste Version heruntergeladen werden: Java SE download
Sollten sie auf Bugs aufmerksam werden bitte schreiben Sie mir mit einer Beschreibung des Automaten (am besten als String den man über den Menüpunkt Save...->as String) bekommt.
Weiters freue ich mich über Anregungen und Ideen, erreicht werden kann ich unter: ben dot eizinger at gmx dot at
