• Author / Uploaded
• German Matt

• Categories
• Algoritmos
• Matemáticas Aplicadas
• Física y matemáticas
• Matemáticas
• Informática teórica

Citation preview

Algoritmo de Minimización ***Iniciamos mencionándole a grandes rasgos en que consiste el algoritmo de minimización.***

***dicho algoritmo recibe como entrada un autómata finito determinista y encuentra los estados distinguibles entre si.***

***La finalidad de este algoritmo es obtener un autómata equivalente al recibido, pero con menos estados, y logra esto eliminando estados sumideros y estados no alcanzables ***

***Iniciaremos el algoritmo estudiando el autómata finito determinista y observaremos las transiciones de dicho autómata junto con los valores que permiten que se realicen dichas transiciones como vemos en el papel bon tenemos el autómata en la parte izquierda y a la derecha la tabla donde encontramos las transiciones de cada estado según los valores de “a” y “b” que guían el autómata.

Luego de analizar dicha información podremos iniciar el algoritmo de minimización que para efectos de comprensión en nuestro caso consta de 6 pasos ***

***Como paso uno tenemos que separar los estados finales de los no finales para crear dos subconjuntos. Según nuestro ejemplo el subconjunto de estados no finales está formado por los estados uno, dos, tres y cuatro y el subconjunto de estados finales está conformado por el estado cinco.***

***Con el paso uno completado procedemos al paso dos que recorre cada estado con un símbolo de transición a la vez para ver el comportamiento de los estados en cada subconjunto. Como vemos en la tabla iniciamos con el símbolo

de transición “a” y el subconjunto de los estados no finales, así creamos la transición del estado uno con la hilera “a” y llegamos al estado dos***

***Seguimos con el estado dos del subconjunto en el que estamos trabajando, que sería el estado dos y hacemos la transición con “a” para llegar a el mismo, el estado dos***

***lo mismo para el estado cuatro y transición “a” para llegar al estado dos.***

***Continuamos con el siguiente subconjunto de estados finales y le aplicamos el mismo procedimiento; en este caso este subconjunto solo posee un estado, por lo que no es necesario separar dicho conjunto, de igual forma podemos colocar en la tabla, la transición del estado cinco con “a” para llegar al estado dos.***

*** Si al realizar el paso dos con la primera transición no hay cambios en los subconjuntos entonces continuamos con el siguiente símbolo de transición, si nuevamente no hay cambios en los subconjuntos, utilizamos el siguiente símbolo de transición y realizamos esto hasta obtener cambios en los subconjuntos o agotar todos los símbolos de transición.***

***Como observamos después de aplicar el paso anterior, los subconjuntos se comportaron de igual forma al aplicar la transición “a”, por lo tanto se debe

realizar el mismo procedimiento del paso dos solamente que esta vez utilizando la transición “b” ***

***Iniciamos con el subconjunto de estados no finales, y le aplicamos la transición “b” al estado uno, llegando este al estado tres***

***Continuamos con el estado dos, aplicando la transición con “b” llegamos al estado cuatro***

***Luego al estado tres aplicando la transición con “b” llega a si mismo***

***Continuamos con el estado cuatro, que al aplicar la transición con “b” llega al estado cinco***

***Continuamos con el otro subconjunto, aunque es este caso al tener solo un estado no se presentaran mayores cambios de igual forma colocamos la transición del estado cinco con “b” al estado uno***

***Como regla del algoritmo, se separan los estados de un subconjunto que al aplicarle una transición se comportan de forma diferente al resto de los demás estados de su subconjunto, formando un nuevo subconjunto de estados. Tomando en cuenta que si varios estados son los que se comportan diferente, todos ellos formaran un nuevo subconjunto.***

***Si aplicamos la regla de este paso, en el ejemplo que venimos desarrollando, en el paso tres logramos observar que al aplicar la transición con “b” en el subconjunto de estados no finales el estado cuatro tuvo un comportamiento diferente a los estados de su subconjunto, esto puesto que al aplicar la transición de desplaza al subconjunto de los estados finales a diferencia del resto de estados que se desplazan a su propio subconjunto. Por lo que el estado cuatro formara un nuevo subconjunto***

***Como podemos observar en la tabla de la derecha, el subconjunto de estados no finales se encuentra ahora conformado por dos subconjuntos uno formado por los estados uno, dos, tres y otro que corresponde al nuevo subconjunto formado por el estado cuatro***

***Continuando con el algoritmo, como paso cinco tenemos que al haber creado un nuevo subconjunto de estados en el paso anterior, debemos aplicar nuevamente los pasos dos y tres sobre todos los subconjuntos actuales. Reflejado en la tabla de la derecha, vemos el resultado de aplicar nuevamente los pasos dos y tres de nuestro algoritmo.***

***Observamos nuevamente como el estado dos se comporta diferente al resto de los estados de su subconjunto, por lo tanto aplicamos la regla del paso cuatro y separamos al estado dos en un nuevo subconjunto, lo vemos reflejado en la tabla de transición, quedándonos ahora con tres subconjuntos de estados no finales, uno formado por los estados uno y tres, otro formado por el estado dos y el ultimo conformado por el estado cuatro.***

***Aplicamos nuevamente los pasos dos y tres del algoritmo a nuestros conjuntos de estados y los resultados se encuentran reflejados en la tabla de la derecha. ***

***Como no se reflejan cambios a la hora de aplicar el paso 3, hemos llegado al final de los procedimientos a seguir, por lo tanto tenemos nuestro autómata mínimo.***

***En nuestro paso seis dibujamos el autómata obtenido al final de la minimización, en este caso el que se encuentra a la izquierda**

Basándonos en la tabla de transición obtenida al aplicar el algoritmo de minimización al autómata de entrada. Creamos el autómata donde cada estado se encuentra formado por los subconjuntos que obtuvimos al final de nuestro algoritmo Y sus transiciones son las que se muestran en la tabla obtenida con nuestro algoritmo.