Qu'est-ce qu'un bon algorithme pour générer DFA au hasard?

Question

Je suis générer DFA aléatoires pour tester un algorithme de réduction DFA sur eux.

L'algorithme que j'utilise est suit comme en ce moment: pour chaque état $ q $, pour chaque symbole dans l'alphabet $ c $, ajouter $ \ delta (q, c) $ à un état aléatoire. Chaque Etat a la même probabilité de devenir un état final.

Est-ce une bonne méthode de génération DFA impartiales? En outre, cet algorithme ne génère pas de DFA garniture (DFA sans états obsolètes), donc je me demande s'il y a une meilleure façon de générer DFA aléatoires qui peuvent en quelque sorte assurer qu'il est équilibre?

Answer 1

Voir [1] et la discussion dans la section 4, aléatoire Automata génération. Le document de référence différents algorithmes de minimisation DFA. Un générateur aléatoire uniforme est utilisé qui produit des représentations de chaîne canoniques de DFA complets avec $ n états $ et k $ symboles $. Ils discutent également d'autres méthodes.

---

[1] Almeida, M., Moreira, N., & Reis , R. (2007). Sur les performances des algorithmes de minimisation des automates. Logique et théorie des algorithmes, 3.

Answer 2

Vous devriez regarder page d'accueil de Cyril Nicaud . En particulier, les références suivantes sont pertinentes à votre question:

F. Bassino, J. David et C. Nicaud, Enumeration et génération aléatoire d'automates peut-être incomplète déterministe, Mathématiques pures et applications 19 (2-3) (2009) 1-16 .

F. Bassino et C. Nicaud. Énumération et aléatoire génération Automata accessible. Theor. Comp. Sc. . 381 (2007) 86-104.

Answer 3

Il existe des algorithmes pour générer au hasard DFA jusqu'à une permutation http: // Paranthoën .thomas.free.fr / PAPIERS / RandDFAToAppearInTCS.ps.gz .

Mais, il est également mentionné dans le document ci-dessus que presque tous les DFA sont déjà minimes. DFA non minimales sont comme les nombres premiers ... il y a juste quelques-uns d'entre eux. Et si vous utilisez cet algorithme à l'algorithme de minimisation de test, ce sera comme si vous testiez un algorithme sur nombre premier avec un simple générateur de nombres aléatoires. Afin d'avoir plus non DFA minimal, vous pouvez modifier l'algorithme en ajoutant un état de puits, et rediriger un pourcentage important des transitions à cet état de puits.

Mais de mon point de vue, si vous voulez tester la rapidité de votre implémentation, vérifiez contre ce que vous voulez l'utiliser pour: avec des jeux de mots aléatoires ou REGEX aléatoire, créez un NFA ou un DFA, puis réduisez le DFA résultant.

Answer 4

une stratégie naturelle est de considérer le DFA comme un graphique et puis il y a beaucoup de « naturelles » et très étudié les distributions aléatoires de graphiques, le plus simple est probablement Erdos-Renyi . dans ce cas, vous traitez tous les états du DFA en tant que nœuds du graphe et quelques pour cent fixe de tous les bords possibles (transitions DFA) sont choisis. des distributions plus sophistiquées qui sont étudiées plus à l'époque plus récente sont petits graphiques mondiale. pour la stratégie que vous mentionnez dans votre question que vous choisissez apparemment le cas particulier $ p = 1 / n $ où $ n $ est le nombre de noeuds dans le graphique. mais votre stratégie, ni Erdos-Renyi, ne garantit pas que tous les Etats de la DFA sont connectés [une contrainte naturelle à ajouter].