Unión de lenguajes regulares

Tomemos dos lenguajes regulares L₁, L₂. Demostraremos que su unión L = L₁ ∪ L₂ es también un lenguaje regular.

Procedimiento con un autómata determinista

Idea del procedimiento

Tenemos dos lenguajes regulares L₁ y L₂ y queremos demostrar que su unión L₁ ∪ L₂ es de nuevo un lenguaje regular. Como L₁ y L₂ son lenguajes regulares, existen autómatas finitos A₁ y A₂ que aceptan los lenguajes L₁ y L₂, es decir, se cumple L(A₁) = L₁ y L(A₂) = L₂. A continuación construiremos un autómata finito A que aceptará el lenguaje L₁ ∪ L₂, con lo que demostraremos que el lenguaje L₁ ∪ L₂ es regular.

¿Cómo lo hacemos? Disponemos de los autómatas finitos A₁ y A₂, que aceptan cada uno de los lenguajes. Podemos decir que la palabra w pertenece al lenguaje L₁ ∪ L₂ si y solo si la acepta al menos uno de los autómatas A₁ o A₂.

El autómata A podría funcionar así: para la entrada w, simulará el cómputo del autómata A₁ para la entrada w. Si A₁ acepta la palabra w, también la aceptará A. Si A₁ rechaza la palabra w, A intentará todavía simular el cómputo de A₂ para la entrada w. Si A₂ acepta la palabra w, también A la aceptará. En caso contrario, la rechazará.

Nos queda formalizar qué significa que el autómata A «simula» el cómputo de otro autómata.

Formalización

Tenemos dos lenguajes regulares L₁ y L₂, que son aceptados por los autómatas finitos

$\begin{array}{rcl} A_{1} & = & ⟨ Q_{1}, Σ_{1}, δ_{1}, q_{1}, F_{1} ⟩ \\ A_{2} & = & ⟨ Q_{2}, Σ_{2}, δ_{2}, q_{2}, F_{2} ⟩ . \end{array}$

Construimos un autómata finito A = ⟨Q, Σ, δ, q, F⟩ que aceptará el lenguaje L = L₁ ∪ L₂. Aprovechamos la idea de simular dos autómatas A₁, A₂. Imaginemos que en la entrada tenemos la palabra w = w₁w₂… w_n y que vamos a simular a la vez el funcionamiento de los autómatas A₁ y A₂ para la palabra w. La configuración inicial del autómata A₁ es ⟨q₁, w₁w₂… w_n⟩ y la configuración inicial de A₂ es ⟨q₂, w₁w₂… w_n⟩. En cada autómata realizamos ahora un paso de cómputo, con lo que llegamos a las configuraciones ⟨δ₁(q₁, w₁), w₂… w_n⟩ y ⟨δ₂(q₂, w₁), w₂… w_n⟩.

Vemos que estas configuraciones se diferencian solo en la primera componente; la segunda —la parte aún no leída de la palabra— es siempre la misma. Durante la simulación no necesitamos, por tanto, mantener dos configuraciones de dos autómatas, sino que nos basta una configuración de la forma ⟨⟨q_i, q_j⟩, w_l… w_n⟩, donde q_i ∈ Q₁ y q_j ∈ Q₂. Dicho de otro modo, nuestro autómata A tendrá la configuración inicial ⟨⟨q₁, q₂⟩, w⟩. La primera parte del par ⟨q₁, q₂⟩ representa el estado en el que se encuentra en ese momento el autómata A₁ y la segunda componente representa el estado actual del autómata A₂.

Podemos escribir, pues, que el autómata A que construimos tendrá un conjunto de estados igual a Q = Q₁ × Q₂. Será el producto cartesiano de los estados de los dos autómatas anteriores. La idea siguiente es que el autómata A tendrá el estado inicial ⟨q₁, q₂⟩ y que, si el autómata A₁ pasa con el símbolo w₁ al estado q_i y el autómata A₂ pasa con el símbolo w₁ al estado q_j, el autómata A pasará con el símbolo w₁ al estado ⟨q_i, q_j⟩.

La función de transición δ la escribimos así (aquí ya suponemos que nos encontramos en los estados q_i y q_j):

$δ (⟨ q_{i}, q_{j} ⟩, w) = ⟨ δ_{1} (q_{i}, w), δ_{2} (q_{j}, w) ⟩$

Solo nos quedan unos detalles. Para el alfabeto se cumple Σ= Σ₁ ∪ Σ₂. El estado inicial es q = ⟨q₁, q₂⟩. Y los estados finales son todos los pares ⟨q_i, q_j⟩ tales que q_i ∈ F₁ o q_j ∈ F₂.

Ilustración del procedimiento

Tomemos dos autómatas. El primero es el autómata A₁, que acepta todas las palabras (incluida la palabra vacía) en las que se alternan ceros y unos, es decir, las palabras de la forma 01, 0101, 010101, …

El otro autómata, A₂, acepta las palabras que contienen al menos un cero:

La unión de estos lenguajes está formada por las palabras que contienen un cero o que son de la forma 01, 0101, … Ahora construimos el autómata finito A = ⟨Q, Σ, δ, q, F⟩ que aceptará precisamente este lenguaje unión. Primero mostraremos cómo serán los estados de este nuevo autómata A. Será el producto cartesiano de los estados del primer y del segundo autómata:

$Q = Q_{1} \times Q_{2} = {⟨ q_{0}, p_{0} ⟩, ⟨ q_{0}, p_{1} ⟩, ⟨ q_{1}, p_{0} ⟩, ⟨ q_{1}, p_{1} ⟩, ⟨ q_{2}, p_{0} ⟩, ⟨ q_{2}, p_{1} ⟩}$

Así son los seis estados del autómata A, que acepta el lenguaje unión L(A₁) ∪ L(A₂). En el diagrama tendrían este aspecto:

No te asustes al ver que hay estados formados por pares de estados: sirve solo para orientarnos mejor en lo que ocurre en el autómata. Los estados podrían llamarse tranquilamente, como siempre, q₀, …, q₅. Los estados finales son los que contienen el estado q₀ o el estado p₁, que son los estados finales de los autómatas originales. El estado inicial es ⟨q₀, p₀⟩.

Ahora debemos hallar todas las transiciones. Escribimos una tabla como esta:

$\begin{array}{ccc} 0 & 1 \\ ⟨ q_{0}, p_{0} ⟩ \\ ⟨ q_{0}, p_{1} ⟩ \\ ⟨ q_{1}, p_{0} ⟩ \\ ⟨ q_{1}, p_{1} ⟩ \\ ⟨ q_{2}, p_{0} ⟩ \\ ⟨ q_{2}, p_{1} ⟩ \end{array}$

Y la iremos completando poco a poco. Primero averiguamos adónde llevará la transición desde el estado ⟨q₀, p₀⟩ con la entrada 0. Vemos adónde lleva la transición desde el estado q₀ con la entrada 0 en el autómata A₁: lleva al estado q₁. En el autómata A₂, la transición desde p₀ con cero lleva al estado p₁. Así que en la tabla escribimos ⟨q₁, p₁⟩:

$\begin{array}{ccc} 0 & 1 \\ ⟨ q_{0}, p_{0} ⟩ & ⟨ q_{1}, p_{1} ⟩ \\ ⟨ q_{0}, p_{1} ⟩ \\ ⟨ q_{1}, p_{0} ⟩ \\ ⟨ q_{1}, p_{1} ⟩ \\ ⟨ q_{2}, p_{0} ⟩ \\ ⟨ q_{2}, p_{1} ⟩ \end{array}$

Con la entrada 1 obtenemos: para el autómata A₁ tenemos δ₁(q₀, 1) = q₂ y para el autómata A₂ tenemos δ₂(p₀, 1) = p₀. Obtenemos así el estado ⟨q₂, p₀⟩.

$\begin{array}{ccc} 0 & 1 \\ ⟨ q_{0}, p_{0} ⟩ & ⟨ q_{1}, p_{1} ⟩ & ⟨ q_{2}, p_{0} ⟩ \\ ⟨ q_{0}, p_{1} ⟩ \\ ⟨ q_{1}, p_{0} ⟩ \\ ⟨ q_{1}, p_{1} ⟩ \\ ⟨ q_{2}, p_{0} ⟩ \\ ⟨ q_{2}, p_{1} ⟩ \end{array}$

Completamos el resto de la tabla:

$\begin{array}{ccc} 0 & 1 \\ ⟨ q_{0}, p_{0} ⟩ & ⟨ q_{1}, p_{1} ⟩ & ⟨ q_{2}, p_{0} ⟩ \\ ⟨ q_{0}, p_{1} ⟩ & ⟨ q_{1}, p_{1} ⟩ & ⟨ q_{2}, p_{1} ⟩ \\ ⟨ q_{1}, p_{0} ⟩ & ⟨ q_{2}, p_{1} ⟩ & ⟨ q_{0}, p_{0} ⟩ \\ ⟨ q_{1}, p_{1} ⟩ & ⟨ q_{2}, p_{1} ⟩ & ⟨ q_{0}, p_{1} ⟩ \\ ⟨ q_{2}, p_{0} ⟩ & ⟨ q_{2}, p_{1} ⟩ & ⟨ q_{2}, p_{0} ⟩ \\ ⟨ q_{2}, p_{1} ⟩ & ⟨ q_{2}, p_{1} ⟩ & ⟨ q_{2}, p_{1} ⟩ \end{array}$

Y a partir de esta tabla solo nos queda dibujar el resto del diagrama.

Podemos comprobar que el autómata funciona como debe. Intentemos aceptar la palabra 0100. El autómata pasa sucesivamente por los estados

$⟨ q_{0}, p_{0} ⟩, ⟨ q_{1}, p_{1} ⟩, ⟨ q_{0}, p_{1} ⟩, ⟨ q_{1}, p_{1} ⟩, ⟨ q_{2}, p_{1} ⟩$

Como el estado ⟨q₂, p₁⟩ es final, el autómata A acepta la palabra 0100. ¿Qué ocurriría si intentáramos aceptar la palabra 0100 con los autómatas A₁ y A₂? El autómata A₁ pasaría sucesivamente por estos estados:

$q_{0}, q_{1}, q_{0}, q_{1}, q_{2}$

El autómata terminó en el estado q₂, que no es final, así que el autómata A₁ no aceptaría esta palabra. ¿Y el autómata A₂?

$p_{0}, p_{1}, p_{1}, p_{1}, p_{1}$

El estado p₁ es final, así que el autómata A₂ sí aceptaría la palabra 0100. Fíjate en que los autómatas A₁ y A₂ terminaron en los estados q₂ y p₁, lo que concuerda con que el autómata A terminara en el estado ⟨q₂, p₁⟩.

Procedimiento con un autómata no determinista

Ejemplo

Que el conjunto de los lenguajes regulares es cerrado respecto de la unión podemos demostrarlo también construyendo un autómata no determinista, que será mucho más sencillo.

Tenemos dos lenguajes regulares L₁, L₂ y queremos demostrar que su unión L = L₁ ∪ L₂ es también un lenguaje regular. Como L₁, L₂ son lenguajes regulares, deben existir autómatas A₁, A₂ que acepten estos lenguajes, es decir, se cumple que L(A₁) = L₁ y L(A₂) = L₂. Con estos autómatas construiremos un autómata A que aceptará el lenguaje L, es decir, L(A) = L.

Supongamos que los autómatas finitos A₁ y A₂ tienen este aspecto:

El autómata que aceptara la unión de ambos lenguajes lo construiríamos creando un nuevo estado inicial y trazando desde él dos transiciones ε hacia los estados iniciales originales. Eso es todo. El autómata tendría este aspecto:

Formalización

Tenemos dos autómatas A₁ = ⟨Q₁, Σ, δ₁, q₁, F₁⟩ y A₂ = ⟨Q₂, Σ, δ₂, q₂, F₂⟩. Construimos un autómata A = ⟨Q, Σ, δ, q₀, F⟩ que aceptará la unión de los lenguajes aceptados por los autómatas anteriores, es decir, L(A) = L(A₁) ∪ L(A₂). Se cumple que:

Q = Q₁ ∪ Q₂ ∪ {q₀}
F = F₁ ∪ F₂

Y la función de transición δ la definimos así:

$δ (q, a) = {\begin{cases} δ_{1} (q, a) & si & q \in Q_{1} \\ δ_{2} (q, a) & si & q \in Q_{2} \\ {q_{1}, q_{2}} & si & q = q_{0} \land a = ε \\ \emptyset & si & q = q_{0} \land a \neq ε \end{cases}$

Fuentes

Capítulos: Propiedades de cierre de los lenguajes regulares, Unión de lenguajes regulares, Intersección de lenguajes regulares, Diferencia de lenguajes regulares, Complemento de un lenguaje regular, Concatenación de lenguajes regulares, Clausura de un lenguaje regular

« Anterior: Propiedades de cierre de los lenguajes regulares

Siguiente: Intersección de lenguajes regulares »