Was ist ein guter Algorithmus zur Generierung zufälliger DFAs?

Question

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

Der Algorithmus, den ich gerade verwende, ist wie folgt: Für jeden Zustand $ Q $ für jedes Symbol im Alphabet $ C $ add $ delta (q, c) $ zu einem zufälligen Zustand. Jeder Staat hat die gleiche Wahrscheinlichkeit, ein endgültiger Zustand zu werden.

Ist dies eine gute Methode zur Erzeugung unvoreingenommener DFAs? Außerdem erzeugt dieser Algorithmus keine DFA (eine DFA ohne veraltete Zustände). Ich frage mich also, ob es eine bessere Möglichkeit gibt, zufällige DFAs zu erzeugen, die irgendwie sicherstellen können, dass er Trim ist?

Answer 1

Schauen Sie sich [1] und die Diskussion in Abschnitt 4, zufällige Automatengeneration an. Die Papierbenchmarks unterschiedliche DFA -Minimierungsalgorithmen. Ein einheitlicher Zufallsgenerator wird verwendet, der kanonische Zeichenfolge Darstellungen vollständiger DFAs mit $ n $ States und $ k $ -Symbole erzeugt. Sie diskutieren auch andere Methoden.

---

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

Answer 2

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

F. Bassino, J. David und C. Nicaud, Aufzählung und zufällige Generation möglicherweise unvollständiger deterministischer Automaten, Reine Mathematik und Anwendungen 19 (2-3) (2009) 1-16.

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

Answer 3

Es gibt Algorithmen, die zufällig DFAs bis zu einer Permutation erzeugen http://paranthoen.thomas.free.fr/papers/randdfatoappearintcs.ps.gz.

In dem obigen Papier wird aber auch erwähnt, dass fast alle DFAs bereits minimal sind. Nicht minimale DFAs sind wie Primzahlen ... es gibt nur wenige von ihnen. Und wenn Sie diesen Algorithmus verwenden, um den Minimierungsalgorithmus zu testen, wird es so sein, als hätten Sie einen Algorithmus auf der Primzahl mit einem einfachen Zufallszahlengenerator getestet. Um mehr nicht minimale DFAs zu haben, können Sie den Algorithmus durch Hinzufügen eines Sinkzustands verändern und einen wichtigen Prozentsatz der Übergänge in diesen Sinkzustand umleiten.

Wenn Sie jedoch die Schnelligkeit Ihrer Implementierung testen möchten, überprüfen Sie sie anhand dessen, was Sie verwenden möchten: Erstellen Sie mit zufälligen Wortsätzen oder zufälligen Regex eine NFA oder eine DFA und minimieren Sie dann die resultierende DFA .

Answer 4

Eine natürliche Strategie besteht darin, die DFA als Diagramm zu betrachten, und dann gibt es viele "natürliche" und hoch untersuchte zufällige Verteilungen von Graphen, der einfachste ist wahrscheinlich Erdos-renyi. In diesem Fall behandeln Sie alle Zustände der DFA als Knoten des Diagramms, und einige feste Prozent der möglichen Kanten (DFA -Übergänge) werden ausgewählt. Weiterentwickelte Verteilungen, die in der neueren Ära viel untersucht werden, sind kleine Welt Grafiken. Für die Strategie, die Sie in Ihrer Frage erwähnen, wählen Sie anscheinend den Sonderfall $ p = 1/n $, wobei $ n $ die Anzahl der Knoten im Diagramm ist. Ihre Strategie und auch nicht erdos-renyi garantiert nicht, dass alle Zustände in der DFA verbunden sind [eine natürliche Einschränkung].