Concatenación de lenguajes regulares

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

Qué es la concatenación

Al concatenar las dos palabras «010» y «1111» se obtiene la palabra «0101111». La concatenación de lenguajes produce así un nuevo lenguaje, que construimos concatenando cada palabra de un lenguaje con cada palabra del otro. La concatenación de dos palabras y de dos lenguajes la representaremos con un círculo: ∘. Entonces podemos definir la concatenación de los lenguajes L₁ y L₂ así:

$$L_1\circ L_2=\{a\circ b\mid a\in L_1,b\in L_2\}$$

Idea de la demostración

Tenemos dos lenguajes regulares L₁, L₂ y dos autómatas que aceptan estos lenguajes:

$$\begin{array}{rcl}{A}_1& =& ⟨Q_1,{\mathrm{\Sigma }}_1,{\delta }_1,q_0,F_1⟩\\ A_2& =& ⟨Q_2,{\mathrm{\Sigma }}_2,{\delta }_2,p_0,F_2⟩\end{array}$$

Construiremos un autómata no determinista A = ⟨Q, Σ, δ, q, F⟩ que «contenga en su interior» los dos autómatas A₁ y A₂. La idea básica es que empezamos a aceptar la palabra con el autómata A₁ y, cuando el autómata A₁ llega a un estado final, intentamos aceptar el resto de la palabra con el autómata A₂. Si este autómata también acepta esa parte de la palabra, el autómata A acepta la palabra.

Ejemplo

Tomemos este autómata A₁, que acepta las palabras no vacías formadas solo por ceros y las palabras formadas por un uno seguido únicamente de ceros (1, 10, 100, …):

y tomemos además este autómata A₂, que acepta las palabras que terminan en 01:

Unimos los autómatas así: desde todos los estados finales del autómata A₁ añadimos transiciones ε hacia el estado inicial del autómata A₂ y después convertimos los estados finales de A₁ en estados ordinarios. El estado inicial del nuevo autómata completo será el estado inicial del autómata A₁:

¿Cómo funcionará el autómata? Empezamos simulando el funcionamiento del autómata A₁. Si pasamos a un antiguo estado final, q₁ o q₂, sabemos que el autómata A₁ acepta una parte de la palabra. Para que la palabra completa pertenezca al lenguaje L₁ ∘ L₂, el segundo autómata A₂ tiene que aceptar todavía el resto de la palabra; por eso de todos los antiguos estados finales salen transiciones ε hacia el estado inicial original del autómata A₂.

Tomemos como ejemplo la palabra 0001. Pertenece a la concatenación de ambos lenguajes, porque la palabra puede obtenerse concatenando las palabras 00 ∘ 01. Pero también puede obtenerse concatenando las palabras 0 ∘ 001. En nuestro autómata podemos simular ambas formas. El autómata puede seguir este camino:

$$q_0{\to }^0{q}_1{\to }^0{q}_1{\to }^{\epsilon }{p}_0{\to }^0{p}_1{\to }^1{p}_2$$

Con este camino el autómata «aceptaría» primero la parte 00 de la palabra y después la parte 01. O puede seguir este otro camino:

$$q_0{\to }^0{q}_1{\to }^{\epsilon }{p}_0{\to }^0{p}_0{\to }^0{p}_1{\to }^1{p}_2$$

y el autómata «aceptaría» así primero la parte 0 de la palabra y luego la parte 001. En ambos casos llegamos, naturalmente, al estado final p₂.

Procedimiento formal

Una vez más: tenemos dos lenguajes regulares L₁, L₂ y dos autómatas que aceptan estos lenguajes:

$$\begin{array}{rcl}{A}_1& =& ⟨Q_1,{\mathrm{\Sigma }}_1,{\delta }_1,q_0,F_1⟩\\ A_2& =& ⟨Q_2,{\mathrm{\Sigma }}_2,{\delta }_2,p_0,F_2⟩\end{array}$$

Construimos un autómata no determinista A = ⟨Q, Σ, δ, q, F⟩ que cumple:

• Q = Q₁ ∪ Q₂ (suponemos además que Q₁ ∩ Q₂ = ∅)
• Σ= Σ₁ ∪ Σ₂
• q = q₀
• F = F₂

La función de transición δ la construimos por casos:

$$\delta (q,a)=\{\begin{array}{lll}{\delta }_1(q,a)& \text{si}& q\in Q_1\wedge q\notin F_1\\ {\delta }_1(q,a)& \text{si}& q\in F_1\wedge a\ne \epsilon \\ {\delta }_1(q,a)\cup \left\{p_0\right\}& \text{si}& q\in F_1\wedge a=\epsilon \\ {\delta }_2(q,a)& \text{si}& q\in Q_2\end{array}$$

Fuentes

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