Download Endbericht

3.2. AUTOMATEN
119
geschieht implizit während der Minimierung. Daher empfiehlt sich die BrzozowskiMinimierung vor allem für diesen Automatentyp.
Das Verfahren ist bezüglich Rechenzeit und Speicherplatzbedarf heuristisch. Beide
sind im worst-case im Verhältnis zur DFA-Zustandsanzahl exponentiell (da determinisiert wird), in vielen Fällen beobachtet man jedoch erstaunlich gute Rechenzeiten.
• Hopcroft-Minimierung: Bei diesem Verfahren wird ebenfalls eine Partition der
Zustände berechnet, allerdings startet man dabei mit der Partition, die nur aus zwei
Mengen besteht, nämlich der Menge akzeptierender und der Menge nicht akzeptierender Zustände. Diese Partition wird schrittweise verfeinert, so dass am Ende die
gleiche Partition entsteht wie bei der oben erwähnten Huffman-Minimierung. Es
wird aber bei n Zuständen nur Rechenzeit O(n · log n) benötigt. Die Alphabetgröße
bzw. die Anzahl verschiedener Symbolmengen in der Eingabe geht als Konstante in
die Laufzeit ein.
3.2.1.8
Weitere Funktionalität
Eine wichtige Anforderung für Bibliotheken ist, dass sie flexibel sind. Dazu gehört, dass
sie mit universellen Formaten umgehen können. Eine Interaktion mit schon vorhandenen
System ist wünschenswert.
3.2.1.8.1
XML Für viele Anwendungen reicht es nicht aus, dass Automaten nur tem-
porär existieren, es ist häufig notwendig, sie weiterzuverarbeiten oder sie auf einem Sekundärspeicher persistent zu machen.
Für diese beiden Zwecke steht die Möglichkeit zur Verfügung, zu einem Automaten eine
XML-Repräsentation zu berechnen. Diese kann (in Form eines org.w3c.dom.DocumentObjektes) entweder direkt weiterverarbeitet oder als Textdatei gespeichert werden.
Die dabei entstehenden Ergebnisse sollen möglichst redundanzfrei, aber noch von Menschen lesbar sein. Daher wurde keine Standardlösung gewählt, sondern ein eigener Weg
beschritten. Die wichtigste Idee dabei ist, Objekte als Teil-XML-Bäume darzustellen, wobei einfache Attribute eines Objekts (z. B. vom Typ String oder int) als Attribute des
Wurzelknoten modelliert werden und komplexere member-Objekte bzw. Sammlungen davon als Unterbäume repräsentiert werden. Diese Lösung ist keine allgemeine, sondern
wurde nur für Objekte erdacht, die Teile von Automaten sind (Zustände, Transitionen,
...).
Für ein Objekt, das auf diese Weise dargestellt werden soll, muss eine ConverterImplementierung zur Verfügung stehen (siehe Abbildung 3.8). Converter ist eine ab-