Qual é um bom algoritmo para gerar DFAs aleatórios?

Estou gerando DFAs aleatórios para testar um algoritmo de redução de DFA neles.

O algoritmo que estou usando agora é o seguinte: para cada estado , para cada símbolo no alfabeto c , adicione δ ( q , c ) a algum estado aleatório. Cada estado tem a mesma probabilidade de se tornar um estado final.$q$$c$$\delta (q, c)$

Esse é um bom método para gerar DFAs imparciais? Além disso, esse algoritmo não gera um DFA aparado (um DFA sem estados obsoletos), então, estou me perguntando se existe uma maneira melhor de gerar DFAs aleatórios que, de alguma forma, possam garantir que seja aparado?

Confira [1] e a discussão na Seção 4, Geração aleatória de autômatos. O documento faz referência a diferentes algoritmos de minimização do DFA. É usado um gerador aleatório uniforme que produz representações de cordas canônicas de DFAs completos com estados e símbolos k . Eles também discutem outros métodos.$n$$k$

[1] Almeida, M., Moreira, N. & Reis, R. (2007). Sobre o desempenho de algoritmos de minimização de autômatos. Lógica e Teoria de Algoritmos, 3.

Você deve olhar a página inicial de Cyril Nicaud . Em particular, as seguintes referências são relevantes para sua pergunta:

F. Bassino, J. David e C. Nicaud, enumeração e geração aleatória de autômatos determinísticos possivelmente incompletos, Pure Mathematics and Applications 19 (2-3) (2009) 1-16.

F. Bassino e C. Nicaud. Enumeração e geração aleatória de autômatos acessíveis. Theor. Comp. Sc. . 381 (2007) 86-104.

Existem algoritmos para gerar DFAs aleatoriamente até uma permutação http://paranthoen.thomas.free.fr/PAPERS/RandDFAToAppearInTCS.ps.gz .

Porém, também é mencionado no artigo acima que quase todos os DFAs já são mínimos. DFAs não mínimos são como números primos ... existem apenas alguns deles. E se você usar esse algoritmo para testar o algoritmo de minimização, será como se você estivesse testando um algoritmo em número primo com um simples gerador de números aleatórios. Para ter DFAs não mínimos, você pode alterar o algoritmo adicionando um estado de coletor e redirecionar uma porcentagem importante das transições para esse estado de coletor.

Mas, do meu ponto de vista, se você quiser testar a rapidez da sua implementação, verifique com o que deseja usá-la: com conjuntos de palavras aleatórios ou REGEX aleatório, crie um NFA ou DFA e minimize o DFA resultante .

$p=1/n$$n$é o número de nós no gráfico. no entanto, sua estratégia, nem Erdos-Renyi, não garante que todos os estados do DFA estejam conectados [uma restrição natural a acrescentar].