Unidad 3 MINIMIZACION DE ESTADOS EN UN AF.

Dos estados de un autómata finito determinista son estados equivalentes si al unirse en un sólo estado, pueden reconocer el mismo lenguaje regular que si estuviesen separados. Esta unión de estados implica la unión tanto de sus transiciones de entrada como de salida. Si dos estados no son equivalentes, se dice que son estados distinguibles. Un estado final con un estado no-final nunca serán equivalentes.

Un AFD está minimizado, si todos sus estados son distinguibles y alcanzables. Un algoritmo de minimización de AFD es el siguiente:

Eliminar los estados inaccesibles del autómata.

Construir una tabla con todos los pares (p, q) de estados restantes.

Marcar en la tabla aquellas entradas donde un estado es final y el otro es no-final, es decir, aquellos pares de estados que son claramente distinguibles.

Para cada par (p, q) y cada símbolo a del alfabeto, tal que r = δ(p,a) y s = δ(q,a):

Si (r, s) ya ha sido marcado, entonces p y q también son distinguibles, por lo tanto, marcar la entrada (p, q).

De lo contrario, colocar (p, q) en una lista asociada a la entrada (r, s).

Agrupar los pares de estados no marcados.

Luego del tercer paso, si la tabla creada queda completamente marcada, entonces el AFD inicial ya era mínimo.

finalmente se obtiene el autómata final, agrupando los estados b y f, así como c y g.

Ejemplo:

Dado un AFD M = (Q, Σ, δ, q0, F), se trata de encontrar un AFD M′ con L(M) = L(M′) y tal que M′ tenga el mínimo numero de estados posible. Para ello, el método consiste en encontrar todos los estados que son equivalentes, es decir, que son indistinguibles en el autómata. Por cada clase de estados equivalentes, el autómata mínimo necesitara un solo estado.

Dados dos estados q, q′ ∈ Q, q y q ′ son indistinguibles o equivalentes si para cualquier cadena w ∈ Σ ∗ se cumple una de las dos siguientes opciones:

·         δ(q, w) ∈ F y δ(q ′ , w) ∈ F

·         δ(q, w) 6∈ F y δ(q ′ , w) ∈ F 1

El método para minimizar un autómata consiste básicamente en encontrar todos los estados que son indistinguibles entre si y sustituirlos por un único estado. Para ello lo principal es averiguar que estados son distinguibles y cuales no.

El método para saber que estados son indistinguibles es el siguiente:

a. Si hay algún estado inalcanzable eliminarlo

b. (i := 0) Marcar todos los estados que pueden distinguirse con la cadena

vacía (es decir, todos los finales se pueden distinguir de los no finales).

c. (i := i + 1) Marcar como distinguibles q y q′

si con algún a ∈ Σ tenemos δ(q, a) y δ(q′, a) dos estados que ahora son distinguibles.

d. Si en el paso anterior se han distinguido nuevos estados, entonces volver

al paso c.