Estados superfluos

Un autómata finito puede tener estados desde los que no es posible llegar a un estado final y que, por tanto, son inútiles. A estos estados los llamamos estados superfluos. Normalmente queremos eliminarlos, porque solo complican innecesariamente todo el autómata.

Ejemplo de estados superfluos

Tomemos este autómata finito:

Vemos que, en cuanto llegamos a los estados q₄ o q₅, ya nunca podremos llegar a uno de los estados finales q₁ o q₂. Estos estados son, por tanto, superfluos y podemos eliminarlos sin más; así obtendremos un autómata nuevo que será equivalente, es decir, aceptará el mismo lenguaje. Tras borrar los estados superfluos, el autómata quedaría así:

Aceptaría, pues, el mismo lenguaje. Sin embargo, hay ocasiones en que conviene tener algunos estados superfluos, por ejemplo cuando construimos un autómata completo.

Definición de estado superfluo

Tomemos un autómata finito A = ⟨Q, Σ, δ, q₀, F⟩. Decimos que un estado q ∈ Q es superfluo si no existe ninguna palabra w ∈ Σ^∗ ni ningún estado q_f ∈ F tales que

$$⟨q,w⟩{\mapsto }^{\ast }⟨q_f,\epsilon ⟩.$$

Cómo eliminar los estados superfluos

Suponemos que en la entrada tenemos un autómata A = ⟨Q, Σ, δ, q₀, F⟩ que ya no tiene estados inaccesibles. Iremos hallando los estados que llevan a estados finales, luego los estados que llevan a estados que llevan a estados finales, y así sucesivamente. De este modo obtenemos el conjunto de todos los estados que no son superfluos. Al principio tomamos S₀ = F. Construiremos otros conjuntos S_i para i ∈ ℕ según esta regla:

$$S_i=\{q\in Q\mid \mathrm{\exists }a\in \mathrm{\Sigma }:\delta (q,a)\in S_{i-1}\}\cup S_{i-1}$$

El conjunto resultante de todos los estados que no son superfluos podemos expresarlo así:

$$\bigcup _{i=1}^{\mathrm{\infty }}{S}_i.$$

Y el conjunto de los estados superfluos, como

$$Q\setminus \bigcup _{i=1}^{\mathrm{\infty }}{S}_i.$$

Dicho de otro modo: si se cumple S_i = S_{i + 1}, entonces el conjunto Q ∖ S_i contiene los estados superfluos. Ilustraremos el procedimiento con este autómata:

Primero tomamos S₀ = {q₁, q₂}. A continuación construimos el conjunto S₁ añadiendo al conjunto S₀ todos los estados que llevan a alguno de los estados de S₀. Añadimos así los estados q₀ y q₃, porque de q₀ sale una transición hacia q₁ y de q₃ sale una transición hacia q₂. Obtenemos S₁ = {q₀, q₁, q₂, q₃}. Como S₀ ≠ S₁, seguimos adelante.

Construimos el conjunto S₂. Buscamos todos los estados desde los que se puede llegar a S₁ y que todavía no están en S₁. Es un único estado, q₆, desde el que se puede llegar al estado q₃. Obtenemos S₂ = {q₀, q₁, q₂, q₃, q₆}. Como S₁ ≠ S₂, seguimos adelante.

Construimos el conjunto S₃. ¿Existe algún estado nuevo desde el que se pueda llegar a alguno de los estados de S₂? No existe: desde los estados q₄ y q₅ no se puede llegar a ninguno de los estados de S₂, y los demás estados ya están en S₂. Se cumple, pues, que S₃ = {q₀, q₁, q₂, q₃, q₆}. Como S₂ = S₃, el algoritmo termina y el conjunto S₂ es el conjunto de los estados que no son superfluos. El conjunto {q₄, q₅} es el conjunto de los estados que sí lo son.

Formalmente, el nuevo autómata equivalente sin estados superfluos se construye así. Tenemos el autómata A = ⟨Q, Σ, δ, q₀, F⟩ y construimos un autómata equivalente A′ = ⟨Q′, Σ, δ′, q₀, F⟩ sin estados superfluos.

• $Q^{\prime }=\bigcup _{i=1}^{\mathrm{\infty }}{S}_i$
• ∀q ∈ Q′, a ∈ Σ:  δ′(q, a) = δ(q, a) si δ(q, a) ∈ Q′; en caso contrario, δ′(q, a) no está definida

Fuentes

• M. Sipser: Introduction to the Theory of Computation
• Aho, Sethi, Ullman: Compilers: Principles, Techniques, and Tools