Minimización de autómatas

Por minimización de un autómata entendemos hallar un autómata equivalente que contenga el menor número posible de estados. Incluso un autómata que no contiene ningún estado superfluo puede simplificarse todavía más.

Ejemplo

Tomemos este autómata:

El autómata acepta únicamente las palabras 01 y 11. Es evidente que existe un autómata más sencillo, con tres estados, que acepta el mismo lenguaje. Los estados q₁ y q₂ pueden fusionarse en un nuevo estado {q₁, q₂}; las transiciones que llegaban a q₁ o a q₂ llegarán al nuevo estado, y lo mismo ocurre con las transiciones que salían de q₁ y de q₂. Obtenemos este autómata:

Este autómata acepta, evidentemente, el mismo lenguaje que el anterior y, además, tiene menos estados.

Equivalencia de estados

Tomemos un autómata A = ⟨Q, Σ, δ, q₀, F⟩. Definimos el lenguaje del estado q ∈ Q, que denotamos L(q), como

$L (q) = L (⟨ Q, Σ, δ, q, F ⟩)$

Es decir, cambiamos el estado inicial del autómata A de q₀ a q y calculamos el lenguaje que acepta ese autómata. Dicho de otro modo, en el lenguaje L(q) están todas las palabras w tales que, en el autómata A, desde el estado q llegamos con la palabra w a un estado final del autómata. Si volvemos al autómata anterior, se cumple L(q₁) = {1}.

Decimos que dos estados distintos q₁ y q₂ son equivalentes si se cumple

$L (q_{1}) = L (q_{2})$

¿Qué significa esto? Si los estados q₁, q₂ son equivalentes, al convertirlos en estados iniciales del autómata generarán el mismo lenguaje. Dicho de otro modo: si el autómata llega a las configuraciones ⟨q₁, w⟩ y ⟨q₂, w⟩, en ambos casos debe aceptar o en ambos casos rechazar.

Si volvemos al autómata anterior, los estados q₁ y q₂ son equivalentes, porque si estamos en el estado q₁, solo podemos aceptar la palabra de entrada si la parte aún no leída de la palabra es igual a 1. Lo mismo ocurre si estamos en el estado q₂.

Minimizar un autómata consiste, por tanto, en hallar los estados equivalentes y eliminarlos fusionándolos en un único estado nuevo, igual que hicimos en el ejemplo anterior.

Cómo hallar los estados equivalentes

¿Qué estados no serán equivalentes con toda seguridad? Un estado final y uno no final no pueden ser equivalentes, porque el lenguaje del estado final es distinto del lenguaje del estado no final: el estado final acepta con seguridad la palabra ε y el no final no. Mostraremos el procedimiento directamente con un ejemplo. Tomemos este autómata:

Empezamos creando dos conjuntos de estados:

$\begin{array}{rcl} S_{1} & = & F = {q_{3}, q_{6}}, \\ S_{2} & = & Q ∖ F = {q_{0}, q_{1}, q_{2}, q_{4}, q_{5}} . \end{array}$

Ahora creamos la tabla de transiciones y conservamos la información sobre los grupos S₁ y S₂:

$\begin{array}{ccccc} grupo & estado & 0 & 1 \\ S_{1} & q_{3} & q_{5} & q_{4} \\ q_{6} & — & — \\ S_{2} & q_{0} & q_{1} & q_{2} \\ q_{1} & — & q_{3} \\ q_{2} & — & q_{3} \\ q_{4} & q_{6} & — \\ q_{5} & q_{6} & — \end{array}$

Ahora modificamos la tabla: en lugar de escribir directamente a qué estados se va con cada símbolo, anotamos solo el grupo al que pasamos. Por ejemplo, desde el estado q₃ con 0 llegamos al estado q₅, que está en el grupo S₂. En lugar de q₅ escribimos, pues, en la tabla S₂:

$\begin{array}{ccccc} grupo & estado & 0 & 1 \\ S_{1} & q_{3} & S_{2} & S_{2} \\ q_{6} & — & — \\ S_{2} & q_{0} & S_{2} & S_{2} \\ q_{1} & — & S_{1} \\ q_{2} & — & S_{1} \\ q_{4} & S_{1} & — \\ q_{5} & S_{1} & — \end{array}$

Ahora dividimos de nuevo ambos grupos. En los mismos grupos colocamos siempre los estados que pasan a los mismos grupos para todos los símbolos. Por ejemplo, los estados q₃ y q₆ no estarán en el mismo grupo, porque ni con 0 ni con 1 van al mismo grupo. En cambio, los estados q₁ y q₂ estarán en el mismo grupo, porque ninguno de los dos tiene transición para 0 y ambos van con 1 al grupo S₁. Creamos así nuevos grupos:

$\begin{array}{ccccc} grupo & estado & 0 & 1 \\ q_{3} & S_{2} & S_{2} \\ q_{6} & — & — \\ q_{0} & S_{2} & S_{2} \\ q_{1} & — & S_{1} \\ q_{2} & — & S_{1} \\ q_{4} & S_{1} & — \\ q_{5} & S_{1} & — \end{array}$

En cada grupo tenemos las mismas transiciones. Nombramos los grupos recién creados y volvemos a averiguar a cuál de estos nuevos grupos se dirigen los estados:

$\begin{array}{ccccc} grupo & estado & 0 & 1 \\ S_{1} & q_{3} & S_{5} & S_{5} \\ S_{2} & q_{6} & — & — \\ S_{3} & q_{0} & S_{4} & S_{4} \\ S_{4} & q_{1} & — & S_{1} \\ q_{2} & — & S_{1} \\ S_{5} & q_{4} & S_{2} & — \\ q_{5} & S_{2} & — \end{array}$

En este momento realizamos otra división de los grupos. Pero vemos que ya no podemos dividir más; obtendríamos los mismos grupos, porque los estados q₁ y q₂ tienen las mismas transiciones respecto de los grupos, pero ya están en el mismo grupo y no hay ningún otro estado en el grupo S₄. El algoritmo de búsqueda de estados equivalentes ha terminado. De cada grupo nos basta elegir un estado; los demás los borramos, y todas las transiciones que llevaban a los estados borrados llevarán al único estado que hemos elegido.

Podemos elegir, por ejemplo, que nuestro nuevo autómata tenga los estados q₃, q₆, q₀, q₁, q₄ y eliminar los estados q₂ y q₅. Todas las transiciones que llevaban a q₂ llevarán ahora a q₁ y todas las que llevaban a q₅ llevarán a q₄:

Procedimiento de minimización de un autómata

Eliminamos los estados inaccesibles,
eliminamos los estados superfluos,
eliminamos los estados equivalentes.

Fuentes

Capítulos: Estados inaccesibles, Estados superfluos, Minimización de autómatas

« Anterior: Estados superfluos

Siguiente: Propiedades de cierre de los lenguajes regulares »