Estados inaccesibles

Un autómata finito puede tener estados a los que no es posible llegar. A estos estados los llamamos estados inaccesibles. Normalmente queremos eliminarlos, porque solo complican innecesariamente todo el autómata.

Ejemplo de estados inaccesibles

Tomemos este autómata:

Vemos que, hagamos lo que hagamos, nunca llegaremos al estado q₃, porque no entra en él ninguna transición. Del estado q₃ decimos, por tanto, que es inaccesible. Una pregunta: ¿sería accesible el estado q₃ si entrara en él alguna transición desde otro estado? Si trazáramos una arista desde uno de los estados q₀, q₁, q₂, q₅, sería accesible. Si añadiéramos otro nodo y trazáramos una transición desde él…

…entonces, naturalmente, los dos estados q₃ y q₄ serían inaccesibles.

Definición de estado inaccesible

Primero definimos el estado accesible. Tomemos un autómata finito A = ⟨Q, Σ, δ, q₀, F⟩. Decimos que un estado q ∈ Q es accesible si existe una palabra w ∈ Σ^∗ tal que

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

Un estado q ∈ Q es inaccesible si no es accesible.

Cómo eliminar los estados inaccesibles

Si un autómata ya tiene algunos estados inaccesibles, conviene eliminarlos. Construimos así un autómata equivalente A′ = ⟨Q′, Σ, δ′, q₀, F′⟩ que no tendrá estados inaccesibles.

Construiremos de forma iterativa el conjunto de estados accesibles. Empezamos con el conjunto S₀ = {q₀}, porque el estado inicial es sin duda accesible. El conjunto siguiente lo construimos así:

$$S_i=\{r\mid \delta (q,a)=r\text{ para algún }q\in S_{i-1},a\in \mathrm{\Sigma }\}\cup S_{i-1}$$

Dicho en lenguaje llano, el conjunto S₀ está dado siempre; el conjunto S₁ lo construimos tomando todos los estados del conjunto S₀ y averiguando adónde llevan las transiciones para todos los símbolos de Σ. Unimos estos estados con el conjunto original de estados S₀. Con el mismo procedimiento obtenemos el conjunto S₂ y los siguientes. Es evidente que se cumplirá S_{i − 1} ⊆ S_i.

El conjunto de estados accesibles se puede obtener entonces así:

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

Puede parecer extraño que intentemos unir infinitos conjuntos S_i, pero el autómata contiene solo un número finito de estados. Eso significa que en algún momento los conjuntos S_j y S_{j + 1} y todos los siguientes serán iguales, de modo que incluso después de unir infinitos conjuntos podemos obtener un conjunto finito de estados.

Volvamos al autómata

e intentemos hallar el conjunto de estados accesibles. Empezamos planteando la igualdad básica

$$S_0=\left\{q_0\right\}$$

Ahora calculamos el conjunto S₁. Debemos hallar todas las transiciones desde el estado q₀ y añadir sus estados de destino al conjunto S₀. Como se cumple q₀ → ^a q₁ y q₀ → ^bq₂, el conjunto S₁ contendrá además los estados q₁ y q₂:

$$S_1=\{q_0,q_1,q_2\}$$

A continuación construimos el conjunto S₂. Miramos adónde podemos llegar desde los estados q₀, q₁, q₂. El único estado nuevo es q₅, al que podemos llegar desde el estado q₁:

$$S_2=\{q_0,q_1,q_2,q_5\}$$

Después construimos el conjunto S₃. ¿Podemos llegar desde los estados q₀, q₁, q₂, q₅ a algún estado nuevo? No, así que el conjunto S₃ contendrá los mismos elementos que S₂:

$$S_3=\{q_0,q_1,q_2,q_5\}$$

Como S₂ = S₃, también S₃ = S₄ = S₅ = … Si unimos todos los S_i, obtenemos el conjunto S₂, porque ningún otro elemento se añadirá ya en ningún otro conjunto.

El conjunto de estados accesibles del autómata es, por tanto, igual a {q₀, q₁, q₂, q₅}. Los estados inaccesibles los obtenemos mediante la simple diferencia de conjuntos:

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

El conjunto de estados inaccesibles de nuestro autómata es {q₃, q₄}. Eliminamos del autómata A todos los estados inaccesibles y todas las transiciones que contenían algún estado inaccesible. Es decir, el autómata equivalente sin estados inaccesibles A′ = ⟨Q′, Σ, δ′, q₀, F′⟩ al autómata A = ⟨Q, Σ, δ, q₀, F⟩ lo definimos como:

• $Q^{\prime }=\bigcup _{i=1}^{\mathrm{\infty }}{S}_i$
• ∀q ∈ Q′, a ∈ Σ:  δ′(q, a) = δ(q, a)
• $F^{\prime }=F\cap Q^{\prime }=F\cap \bigcup _{i=1}^{\mathrm{\infty }}{S}_i$

Fuentes

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