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

Veamos cómo convertir cualquier expresión regular en un autómata finito no determinista.

Ejemplo

Antes de describir el algoritmo en sí, veamos con un ejemplo de qué se trata. Tomemos esta expresión regular: a(b ∣ c)x^∗. Con palabras describiríamos el lenguaje que genera la expresión regular como las palabras que empiezan por la letra «a», seguida de «b» o de «c», y a continuación una cantidad cualquiera de letras «x». ¿Sabríamos construir un autómata que aceptara este lenguaje? Pues sí, mira:

Este autómata acepta, evidentemente, el mismo lenguaje. Surge entonces la pregunta de si para toda expresión regular existe un autómata que acepte el lenguaje correspondiente. Pues sí.

Descripción del algoritmo de conversión de una expresión regular en un autómata

Suponemos que tenemos como entrada una expresión regular R. De la parte anterior sobre las expresiones regulares sabemos que una expresión regular puede tener en total seis formas distintas. Distinguimos, por tanto, seis casos:

1. R = a para algún símbolo a ∈ Σ. Es decir, la expresión regular es solo un símbolo del alfabeto Σ sobre el que trabajamos. El autómata que aceptara un único símbolo a tendría este aspecto:

   

2. R = ϵ, la palabra vacía. El autómata que aceptara la palabra vacía tendría este aspecto:

   

3. R = ∅, una expresión regular que genera el lenguaje vacío. El autómata que reconoce ese lenguaje es este:

   

4. R = R₁ ∪ R₂, donde R₁, R₂ son expresiones regulares. Ya sabemos que la unión de lenguajes regulares es de nuevo un lenguaje regular y que sabemos construir un autómata que acepte ese lenguaje. Dicho de otro modo, suponemos que tenemos autómatas que reconocen el lenguaje generado por las expresiones R₁ y R₂ y con ellos construimos un autómata que acepta el lenguaje generado por la expresión R₁ ∪ R₂. Ejemplo: si R₁ = a y R₂ = ϵ, según el procedimiento obtenemos este autómata:

   

5. R = R₁ ∘ R₂, donde R₁, R₂ son expresiones regulares. Es el mismo caso que en el punto anterior. La concatenación de lenguajes regulares es un lenguaje regular y por eso sabemos construir un autómata que acepte ese lenguaje. Así que, si R₁ = a, R₂ = b, la concatenación tendría este aspecto:

   

6. $R=(R_1^{\ast })$, donde R₁ es una expresión regular. De nuevo sabemos que la clausura de un lenguaje regular es un lenguaje regular. Así que, si R = a^∗, el autómata tendría este aspecto:

   

Aplicando sucesivamente estos puntos convertimos toda la expresión regular en un autómata finito.

Ejemplo completo

Intentemos convertir la expresión regular (a ∣ bc)^∗. Iremos obteniendo estos autómatas:

Este autómata resultante acepta el lenguaje que genera la expresión regular (a ∣ bc)^∗. Naturalmente, el autómata es terriblemente complicado y seguro que existe un autómata mucho más sencillo que acepta el mismo lenguaje. Podemos usar el algoritmo de conversión de un AFND en un AFD y después aplicar la minimización del autómata.

Fuentes

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