Conversión de un autómata en una expresión regular

Veamos cómo convertir cualquier autómata finito en una expresión regular.

Descripción del algoritmo

Como entrada tenemos un AFND A. Primero lo convertimos en un AFND generalizado. En la segunda fase, en cada paso eliminamos un estado, modificamos adecuadamente la función de transición y repetimos hasta que solo queden dos estados: el inicial y el final. Entre ellos habrá una arista cuya etiqueta será una expresión regular, que será el resultado de todo el algoritmo. Todo el procedimiento consiste, pues, sobre todo en eliminar un estado y corregir después el autómata de modo que obtengamos un autómata equivalente.

Eliminación de un estado

Cómo se elimina un estado podemos mostrarlo con un ejemplo sencillo. Supongamos que una parte de nuestro autómata tiene este aspecto:

donde R_i son algunas expresiones regulares. ¿Qué aspecto tendría el autómata si eliminásemos el estado q_r? Podemos imaginarlo así: estamos en el estado q_i y nos preguntamos qué palabras somos capaces de generar en este tramo. Si vamos directamente del estado q_i al estado q_j, serán todas las palabras que corresponden a la expresión regular R₄.

Pero si vamos al estado q_r, podemos generar palabras de la forma R₁. En el estado q_r, sin embargo, podemos dar vueltas con la expresión regular R₂, de modo que en realidad podemos generar palabras de la forma $R_1\circ (R_2^{\ast })$. Y como además podemos pasar del estado q_r al estado q_j, añadimos todavía la expresión regular R₃. En total, por este camino podemos obtener palabras de la forma $R_1\circ (R_2^{\ast })\circ R_3$.

Ahora sabemos que de esta parte del autómata pueden surgir palabras de la forma R₄ o de la forma $R_1\circ (R_2^{\ast })\circ R_3$. Eso, naturalmente, podemos escribirlo en forma de expresión regular como $(R_4)\mid (R_1\circ (R_2^{\ast })\circ R_3)$.

Ya podemos eliminar sin más el estado q_r y dejar solo los dos estados q_i y q_j, y en lugar de R₄ escribimos la expresión regular que acabamos de calcular:

Este procedimiento lo aplicamos a cada arista de cada estado q_i a algún estado q_j, incluidos los bucles, es decir, incluido el caso en que q_i = q_j.

Tras eliminar un estado obtenemos un autómata equivalente: un autómata que reconoce el mismo lenguaje.

Algoritmo completo

Como entrada tenemos un AFND A = ⟨Q, Σ, δ, q₀, F⟩.

1. Convertimos el AFND A en un AFND generalizado Z = ⟨Q′, Σ, δ′, q₀′, q_f′⟩. En adelante denotaremos con la letra k el número de estados de Z.
2. Si k = 2, el algoritmo termina y en la arista entre el estado inicial y el final está la expresión regular resultante.
3. Si k>2, elegimos un estado cualquiera q_r distinto del estado inicial y del final, es decir, q_r ≠ q₀′ y q_r ≠ q_f′. A continuación creamos un nuevo AFND generalizado Z′ = ⟨Q′′, Σ, δ′′,q₀′,q_f′⟩, para el cual se cumplirá: $$Q^{\prime \prime }=Q^{\prime }\setminus \left\{q_r\right\}$$ y para todo q_i ∈ Q′′ ∖ {q_f′} y para todo q_j ∈ Q′′ ∖ {q₀′} sea $${\delta }^{\prime \prime }(q_i,q_j)=(R_4)\mid (R_1(R_2^{\ast })R_3),$$ donde R₁ = δ′(q_i,q_r), R₂ = δ′(q_r,q_r), R₃ = δ′(q_r, q_j), R₄ = δ′(q_i, q_j). Después continúa con el paso 2.

Ejemplo

Tomemos como entrada este autómata finito:

Primero lo convertimos en un AFND generalizado (las transiciones ∅ innecesarias no las representaremos):

Ahora aplicamos la segunda parte del algoritmo y eliminamos algún nodo. Empezamos con el nodo q₂. Eliminamos el nodo q₂ y añadimos una transición del estado q₁ al estado q_f. Esta transición la etiquetamos con b(a ∣ b)^∗, porque desde el nodo q₁ llegamos al estado q₂ con palabras de la forma b, después podemos dar vueltas con a ∣ b, con lo que obtenemos (a ∣ b)^∗, y por último pasamos a q_f mediante la regla ε. Además se cumple que b(a ∣ b)^∗ϵ = b(a ∣ b)^∗. Obtenemos el autómata:

Nos queda eliminar el último estado, q₁. Añadimos una arista del estado q_s al estado q_f. ¿Cómo la etiquetamos? Al estado q₁ llegamos mediante la regla ε, que podemos omitir sin más. Después podemos dar vueltas con a, con lo que obtenemos la expresión regular a^∗. Y por último, por la arista llegamos a q_f, así que concatenamos la expresión con b(a ∣ b)^∗. La arista la etiquetamos, pues, con la expresión regular a^∗ b(a ∣ b)^∗.

El autómata ya solo tiene dos estados, así que el algoritmo termina. En la arista está la expresión regular resultante.

Fuentes

• El ejemplo y la descripción del algoritmo proceden de M. Sipser: Introduction to the Theory of Computation