Intersección de lenguajes regulares

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

Idea de la demostración

Tenemos dos lenguajes regulares L₁ y L₂ y queremos demostrar que su intersecció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.

Una palabra pertenece a la intersección de lenguajes si pertenece a L₁ y a la vez a L₂. Es decir, la palabra debe ser aceptada por el autómata A₁ y a la vez por el autómata A₂. Aprovechamos exactamente la misma idea que en la unión de lenguajes regulares; solo cambiamos el conjunto de estados finales.

Formalización del procedimiento

Tenemos dos autómatas,

$$\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 A = ⟨Q, Σ, δ, q, F⟩ que acepta el lenguaje L(A₁) ∩ L(A₂). Se cumple que

• Q = Q₁ × Q₂
• Σ= Σ₁ ∩ Σ₂
• q = ⟨q₀, p₀⟩
• F = F₁ × F₂

Para la función de transición δ se cumplirá la siguiente relación:

$$\mathrm{\forall }q\in Q_1,p\in Q_2:\delta (⟨q,p⟩,a)=⟨{\delta }_1(q,a),{\delta }_2(p,a)⟩$$

Ejemplo

Tomemos este autómata A₁, que acepta todas las palabras que contienen un número par de 1:

y el autómata A₂, que acepta las palabras que contienen un número impar de 0:

Construimos un autómata que aceptará la intersección de estos lenguajes. El conjunto de estados de este autómata tiene la forma Q = Q₁ × Q₂, el estado inicial es el estado ⟨q₀, p₀⟩ y los estados finales son F₁ × F₂:

A continuación completamos las transiciones de modo que δ(⟨q,p⟩, a) = ⟨δ₁(q, a), δ₂(p, a)⟩:

En este autómata, por ejemplo, desde el estado ⟨q₀, p₀⟩ hay una transición con el símbolo 0 al estado ⟨q₀,p₁⟩. Significa que el autómata A₁ tiene desde el estado q₀ una transición con el símbolo 0 de vuelta al estado q₀. El autómata A₂, por su parte, tiene con el símbolo 0 una transición desde el estado p₀ al estado p₁.

Podemos probar el autómata. Debería aceptar palabras como 110 o 00000 (contienen un número par de 1 y a la vez un número impar de 0), pero no debería aceptar palabras como 11, 111, 1010.

Fuentes

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