Autor Tema: Re: Minimización de autómatas (Leído 3280 veces)

De Profundiis · « **en:** Viernes 22 de Noviembre de 2002, 13:42 »

Hola,
estoy realizando un generador aleatorio de autómatas en C. Con un máximo de 20 estados y alfabeto {a,b} únicamente. El problema es que una vez tengo el autómata necesito minimizarlo y no encuentro un algoritmo adecuado para implementar la minimización. Cualquier ayuda sería bien recibida (aunque prefiero que no me deis enlaces, porque llevo 5 días navegando buscando información de ese tipo y solo he encontrado un algoritmo incorrecto).
MUCHAS GRACIAS.
Un saludo.

De Profundiis

Hola de nuevo,
ya lo tengo implementado, pero lo he hecho tal y como lo haría sobre el papel buscando las clases de equivalencia y con el teorema de Nerode. Funciona. Pero sé que no es el mejor algoritmo el que he hecho. Si alguien supiese algún algoritmo eficiente, pues que lo escriba o me mande un enlace o lo que sea, aunque ya no corre prisa.
Gracias,
saludos.

deldar

Mandame el problema quizas se me ocurra algo, Por cierto estos algoritmos estan en su mayoria mas que estudiados en brebe te podre pasar bibliografia:)

De Profundiis

Hola... jejeje

Ahora necesito un algoritmo que me haga una muestra estructuralmente completa partiendo de un autómata y otro que me haga una muestra completa. Y, luego, alguna implementación del algoritmo RPNI para aprender autómatas partiendo de muestras aleatorias (lo que ahora no tengo muy claro es si las muestras deben ser completas o solo positivas).

Bueno, de todos modos yo ya estoy en ello.

Saludos y gracias por todo deldar.

Pablo! · « **Respuesta #4 en:** Martes 1 de Julio de 2003, 21:37 »

Hace tiempo que vengo buscando un algiritmo para simplificar automatas. Sería posible que me manden algo de su trabajo?. Realmente en internet hay muy poco de teoria al respecto.
Muchisimas Gracias.
Pablo!