DFA-Minimierung Brzozowski-Algorithmus
https://stackoverflow.com/questions/5893690
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianFrage
Ich versuche, den Brzozowski-Algorithmus zur Minimierung meines DFA zu implementieren Es folgt der Algorithmus für dasselbe.
DFA = d(r(d(r(NFA))))
wobei r() die Umkehrung von NFA ist und D() NFA in DFA konvertiert.
Aber ich verstehe nicht, was die Suche nach r() bei Google bedeutet. Außerdem gibt es nicht viele Informationen.
Kann jemand bitte erklären, was der r() von NFA ist.
Alle anderen verfügbaren einfachen Algorithmen oder C ++ - Implementierungen teilen mir bitte den Link mit.
Lösung
Im Code für reverse.c (gefunden hier , aber jetzt nicht mehr vorhanden) finden Sie einen Kommentar /* Create reversed edges */.Ich würde also sagen, dass r() die Richtung aller Kanten umkehrt (und außerdem sicherstellt, dass der umgekehrte Automat einen genau definierten Startzustand hat).
Andere Tipps
Dies ist die Implementierung vonOpenFst.
In ist dieses Papier ein Diagramm (Seite 15), dasErgebnisse der Anwendung der umgekehrten Operation anzeigen.
Eine einfachere Möglichkeit, FSM-Vorgänge zu verstehen, besteht darin, eine Bibliothek wie OpenFst zu verwenden, um die Maschinen zu erstellen und zu bearbeiten und die Ergebnisse dann mit Graphviz zu visualisieren.
