Was ist ein guter Algorithmus zum Generieren von zufälligen DFAs?

Ich generiere zufällige DFAs, um einen DFA-Reduktionsalgorithmus auf ihnen zu testen.

Der Algorithmus, der ich jetzt bin verwendet , ist wie folgt: für jeden Zustand , für jedes Symbol des Alphabets , fügen bis zu einem gewissen zufälligen Zustand. Jeder Staat hat die gleiche Wahrscheinlichkeit, ein Endzustand zu werden.$q$$c$$\delta (q, c)$

Ist dies eine gute Methode, um unvoreingenommene DFAs zu generieren? Außerdem generiert dieser Algorithmus keinen Trimm-DFA (einen DFA ohne veraltete Zustände). Ich frage mich also, ob es eine bessere Möglichkeit gibt, zufällige DFAs zu generieren, die irgendwie sicherstellen können, dass es sich um einen Trimm-DFA handelt.

Lesen Sie [1] und die Diskussion in Abschnitt 4, Zufällige Automatengenerierung. Das Papier vergleicht verschiedene DFA-Minimierungsalgorithmen. Es wird ein einheitlicher Zufallsgenerator verwendet, der kanonische Zeichenfolgendarstellungen vollständiger DFAs mit Zuständen und Symbolen erzeugt. Sie diskutieren auch andere Methoden.$n$$k$

[1] Almeida, M., Moreira, N. & Reis, R. (2007). Zur Leistung von Algorithmen zur Minimierung von Automaten. Logik und Theorie der Algorithmen, 3.

Sie sollten sich die Homepage von Cyril Nicaud ansehen . Insbesondere sind die folgenden Referenzen für Ihre Frage relevant:

F. Bassino, J. David und C. Nicaud, Aufzählung und zufällige Erzeugung möglicherweise unvollständiger deterministischer Automaten, Pure Mathematics and Applications 19 (2-3) (2009) 1-16.

F. Bassino und C. Nicaud. Aufzählung und zufällige Generierung zugänglicher Automaten. Theor. Comp. Sc. . 381 (2007) 86-104.

Es gibt Algorithmen zum zufälligen Generieren von DFAs bis zu einer Permutation http://paranthoen.thomas.free.fr/PAPERS/RandDFAToAppearInTCS.ps.gz .

In dem obigen Artikel wird jedoch auch erwähnt, dass fast alle DFAs bereits minimal sind. Nicht minimale DFAs sind wie Primzahlen ... es gibt nur wenige davon. Und wenn Sie diesen Algorithmus verwenden, um den Minimierungsalgorithmus zu testen, ist es so, als würden Sie einen Algorithmus mit einem einfachen Zufallszahlengenerator auf Primzahlen testen. Um mehr nicht minimale DFAs zu erhalten, können Sie den Algorithmus ändern, indem Sie einen Senkenstatus hinzufügen und einen wichtigen Prozentsatz der Übergänge in diesen Senkenstatus umleiten.

Wenn Sie jedoch aus meiner Sicht die Schnelligkeit Ihrer Implementierung testen möchten, vergleichen Sie sie mit dem, wofür Sie sie verwenden möchten: Erstellen Sie mit zufälligen Wortmengen oder zufälligem REGEX einen NFA oder einen DFA und minimieren Sie dann den resultierenden DFA .

$p=1/n$$n$ist die Anzahl der Knoten im Diagramm. Ihre Strategie oder Erdos-Renyi garantieren jedoch nicht, dass alle Staaten im EDA miteinander verbunden sind [eine natürliche Einschränkung, die hinzugefügt werden muss].