1
Download Endbericht
Transcript
2.4. EXISTIERENDE LÖSUNGEN 59 müssen nicht veröffentlicht werden. Das heißt, die Software steht nicht unter der Einschränkung des Copylefts. Die BSD-Lizenz schränkt einen User nur bezüglich der Copyright-Vermerke ein. Diese dürfen unter keinen Umständen entfernt werden. 2.4.2.2 dk.brics.automaton dk.brics.automaton [?] ist von Anders Møller am BRICS research center der Universität von Aarhus entwickelt worden. Es handelt sich hierbei um eine Bibliothek, die DFA/NFA-Automaten und reguläre Ausdrücke implementiert. Diese Bibliothek wird ständig weiterentwickelt. Die letzte verfügbare Version wurde am 8. August 2005 veröffentlicht und ist bereits an Java 1.5 angepaßt. Ältere Versionen für Java 1.4 sind ebenfalls erhältlich. Der Sourcecode ist nutzbar unter den Bedingungen der Open Source BSD Lizenz. Funktionsumfang: Mit Hilfe von dk.brics.automaton lassen sich Automaten auf zwei Arten modellieren. Zum einen kann man einen Automaten durch explizite Angabe der Zustände und Zustandsübergangsfunktion modellieren. Auf diese Art lassen sich auch NFAs implementieren. Die zweite Möglichkeit besteht darin, einen Automaten durch die Angabe eines regulären Ausdrucks erzeugen zu lassen. Automat: Auf Automaten sind eine Vielzahl weiterer Operationen erlaubt: Es stehen drei Algorithmen zur Minimierung von Automaten zur Verfügung: Brzozowski’s O(2n ); Hopcroft’s O(n log n); Huffman’s O(n2 ), Komplement, Produktsprache, Quotientensprache, Entfernen von überflüssigen Zuständen, Vereinigung von Automaten, Kleene’scher Abschluss von Automaten, Konvertieren eines NFA-Automaten in einen DFA-Automaten. Fazit: dk.brics.automaton ist eine sehr kleine und übersichtliche Automatenbibliothek. Sie besteht aus sechs Klassen, was sie sehr übersichtlich und verständlich macht. Sie erfüllt so gut wie alle Ansprüche an eine Automatenbibliothek und arbeitet darüber hinaus sehr effizient. Sehr positiv fällt außerdem auf, dass ein Automat aus Zuständen und Zustandsübergangsfunktion identisch zum Automaten seines regulären Ausdrucks ist. Dies klingt selbstverständlich, ist aber bei allen anderen Bibliotheken leider nicht der Fall.
