¿Cuál es un buen algoritmo para generar DFA aleatorios?

Estoy generando DFA aleatorios para probar un algoritmo de reducción de DFA en ellos.

El algoritmo que estoy usando en este momento es el siguiente: para cada estado , para cada símbolo en el alfabeto , agregue a algún estado aleatorio. Cada estado tiene la misma probabilidad de convertirse en un estado final.$q$$c$$\delta (q, c)$

¿Es este un buen método para generar DFA imparciales? Además, este algoritmo no genera un DFA de recorte (un DFA sin estados obsoletos), por lo que me pregunto si hay una mejor manera de generar DFA aleatorios que de alguna manera puedan garantizar que sea un recorte.

Vea [1] y la discusión en la Sección 4, Generación de Autómatas Aleatorios. El documento compara diferentes algoritmos de minimización de DFA. Se utiliza un generador aleatorio uniforme que produce representaciones de cadenas canónicas de DFA completos con estados y k símbolos. También discuten otros métodos.$n$$k$

[1] Almeida, M., Moreira, N. y Reis, R. (2007). Sobre el rendimiento de los algoritmos de minimización de autómatas. Lógica y Teoría de Algoritmos, 3.

Deberías mirar la página de Cyril Nicaud . En particular, las siguientes referencias son relevantes para su pregunta:

F. Bassino, J. David y C. Nicaud, Enumeración y generación aleatoria de autómatas deterministas posiblemente incompletos, Matemáticas puras y aplicaciones 19 (2-3) (2009) 1-16.

F. Bassino y C. Nicaud. Enumeración y generación aleatoria de autómatas accesibles. Theor Comp. Carolina del Sur. . 381 (2007) 86-104.

Existen algoritmos para generar aleatoriamente DFA hasta una permutación http://paranthoen.thomas.free.fr/PAPERS/RandDFAToAppearInTCS.ps.gz .

Pero, también se menciona en el documento anterior que casi todos los DFA ya son mínimos. Los DFA no mínimos son como números primos ... solo hay unos pocos. Y si usa este algoritmo para probar el algoritmo de minimización, será como si estuviera probando un algoritmo en número primo con un simple generador de números aleatorios. Para tener más DFA no mínimos, puede alterar el algoritmo agregando un estado sumidero y redirigir un porcentaje importante de las transiciones a este estado sumidero.

Pero desde mi punto de vista, si desea probar la rapidez de su implementación, compárela con lo que desea usar: con conjuntos de palabras aleatorias o REGEX aleatorio, cree un NFA o un DFA, y luego minimice el DFA resultante .

$p=1/n$$n$es el número de nodos en el gráfico. sin embargo, su estrategia, ni Erdos-Renyi, no garantiza que todos los estados en el DFA estén conectados [una restricción natural para agregar].