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

Question

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

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

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

Answer 1

Echa un vistazo a [1] y la discusión en la Sección 4, generación de autómatas aleatorias. El documento comparó diferentes algoritmos de minimización de DFA. Se utiliza un generador aleatorio uniforme que produce representaciones de cadenas canónicas de DFA completos con $ N $ estados y símbolos de $ K $. También discuten otros métodos.

---

[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 los algoritmos, 3.

Answer 2

Deberías mirar Página de inicio 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 y aplicaciones puras 19 (2-3) (2009) 1-16.

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

Answer 3

Hay algoritmos para generar DFA al azar hasta una permutación http://paranthoen.thomas.free.fr/papers/randdfatoappearintcs.ps.gz.

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

Pero desde mi punto de vista, si desea probar la velocidad de su implementación, verifíquelo con lo que desea usarlo: con conjuntos de palabras aleatorios o regex aleatorios, cree un NFA o un DFA, y luego minimice el DFA resultante .

Answer 4

Una estrategia natural es considerar el DFA como un gráfico y luego hay muchas distribuciones aleatorias "naturales" y altamente estudiadas, lo más simple es probablemente Erdos-Renyi. En ese caso, trata a todos los estados del DFA como nodos del gráfico y se elige algún porcentaje fijo de todos los bordes posibles (transiciones de DFA). Las distribuciones más sofisticadas que se estudian mucho en la era más reciente son mundo pequeño gráficos. Para la estrategia que menciona en su pregunta, aparentemente está eligiendo el caso especial $ p = 1/n $ donde $ n $ es el número de nodos en el gráfico. Sin embargo, su estrategia, ni Erdos-Renyi, no garantiza que todos los estados de la DFA estén conectados [una restricción natural para agregar].