automatas

AUTOMATAS

1. ALGORITMO PARA LA MINIMIZACION DE UN AUTOMATA FINITO
En la minimización de un autómata finito se pretende buscar estados que realizan la mima función en el autómata para agruparlos(minimizarlos) en un solo estado. Para ello, el algoritmo realiza una partición de los estados:, en la que dos estados estarán en la misma clase de equivalencia si realizan la misma función.Estas clases de equivalencia se obtienen por sucesivas aproximaciones:

PASO I:
Los estados finales nunca van a ser equivalentes a los estados no finales, ya que en los primeros se reconoce lapalabra, mientras que en los segundos se rechaza. Por tanto, la primera partición de estados es la siguiente:


= estados finales
=estados no finales
PASO II:
A partir de se obtiene de lasiguiente manera:
que pertenezcan a la misma clase en , siguen estando en si ` transitan igual (a la misma clase de equivalencia)
Cuando se ha obtenido la participación definitiva:
AUTOMATA MINIMORESULTANTE:
Los estados del autómata son las clases de equivalencia obtenidas. Por lo demás, se trata de mantener las características del autómata de partida:
La clase inicial es la que contenga alestado inicial.
Las clases finales son todas aquellas que se compongan de estados finales.
Las transiciones deben der las mismas que el autómata de parida (teniendo en cuenta que si dos estados estánen la misma clase es precisamente por que transitan igual).


Ejemplo: Minimizar el siguiente AFD:



SOLUCION


Obtención de :
: no merece ningún análisis, ya que se compone se un únicoestado, por tanto, no ha podido minimizarse. A continuación se estudia los tres estados de siguen transitando igual o no. Si bien, es importante recordar que se toma en consideración no el estado dedestino, sino la clase de destino, ya que estamos suponiendo que todos los estados de la misma clase son equivalentes. Por ejemplo, en este caso, da igual transitar a , que a o que , ya que en...