Che cosa è un buon algoritmo per la generazione di DFA casuali?

Question

sto generando DFA casuali per testare un algoritmo di riduzione del DFA su di loro.

L'algoritmo che sto usando in questo momento è la seguente: per ogni stato $ q $, per ogni simbolo in alfabeto $ c $, aggiungere $ \ delta (q, c) $ a qualche stato casuale. Ogni stato ha la stessa probabilità di diventare uno stato finale.

E 'questo un buon metodo di generazione di DFA imparziali? Inoltre, questo algoritmo non genera un DFA assetto (un DFA senza stati obsoleti) quindi mi chiedo se c'è un modo migliore di generare DFA casuali che possa in qualche modo garantire che si tratta di assetto?

Answer 1

Scopri [1] e la discussione nella sezione 4, Random Automata Generation. La carta benchmark diversi algoritmi di minimizzazione DFA. Un generatore casuale uniforme viene utilizzato che produce canoniche rappresentazioni di stringa di DFA completi con $ n $ stati e $ k $ simboli. Essi illustrano anche altri metodi.

---

[1] Almeida, M., Moreira, N., & Reis , R. (2007). Sulle prestazioni di algoritmi di minimizzazione automi. Logica e teoria degli algoritmi, 3.

Answer 2

Si dovrebbe guardare homepage Cirillo di Nicaud . In particolare, i seguenti riferimenti sono rilevanti per la tua domanda:

F. Bassino, J. David e C. Nicaud, enumerazione e la generazione casuale di automi anche incompleta deterministici, Pure Matematica e Applicazioni 19 (2-3) (2009) 1-16 .

F. Bassino e C. Nicaud. Enumerazione e Random Generazione di accessibile Automata. Theor. Comp. Sc. . 381 (2007) 86-104.

Answer 3

Non ci sono algoritmi per la generazione casuale DFA fino ad una permutazione http: // paranthoen .thomas.free.fr / documenti / RandDFAToAppearInTCS.ps.gz .

Ma, è anche menzionate nelle carta oltre che quasi tutti i DFA sono già minime. DFA non minime sono come i numeri primi ... ci sono solo alcuni di essi. E se si utilizza questo algoritmo algoritmo di prova minimizzazione sarà come se si stesse testando un algoritmo sul numero primo con un semplice generatore di numeri casuali. Al fine di avere più DFA non minimi, è possibile modificare l'algoritmo con l'aggiunta di uno stato lavandino, e reindirizzare una percentuale importante delle transizioni a questo stato lavandino.

Ma dal mio punto di vista, se si vuole testare la rapidità dell'implementazione, check it contro ciò che si desidera utilizzare per: con i set di parole casuali o REGEX caso, creare un NFA o un DFA, e quindi ridurre al minimo la risultante DFA.

Answer 4

Una strategia naturale è quello di considerare il DFA come grafico e poi ci sono molti "naturali" e altamente studiati distribuzioni casuali di grafici, il più semplice è probabilmente Erdos-Renyi . in tal caso si trattano tutti gli stati del DFA come nodi del grafo e alcuni percentuale fissa di tutti gli spigoli possibili transizioni (DFA) vengono scelti. distribuzioni più sofisticati che si studiano molto in epoca più recente sono piccoli grafici mondo . per la strategia si parla nella domanda si sta a quanto pare la scelta del caso speciale $ p = 1 / n $ dove $ n $ è il numero di nodi nel grafo. tuttavia la vostra strategia, né Erdos-Renyi, non garantisce che tutti gli Stati della DFA sono connessi [un vincolo naturale per aggiungere].