La intersección de dos LR's es un LR

Esta entrada tratará de demostrar que la familia de los Lenguajes Recursivos (L.R.) es cerrada respecto de la intersección, es decir, que la intersección de dos lenguajes regulares da como resultado un L.R.

Hemos encontrado dos formas de demostrarlo:

• Demostración 1: De Morgan
  

Sean L1 y L2  L.R. . Se sabe por los teoremas 7.4 y 7.5 que los L.R. son cerrados bajo las operaciones de unión y complementación. De esto podemos deducir usando las leyes de De Morgan que la intersección también lo es:

¬(L1 ∪ L2) <=> ¬L1 ∩ ¬L2

Como sabemos que la primera parte de la equivalencia da como resultado un L.R. (por los teoremas antes mencionados), podemos afirmar que la intersección de los complementarios de ambos L.R. también es un L.R. y por tanto, la intersección en una propiedad de clausura para los L.R.

• Demostración 2: Contruyendo la Máquina
  

Sean L1 y L2 , L.R. ⇒ ∃ M1 , M2 | L1 = L(M1), L2 = L(M2) y M1 y M2 siempre paran:

- si x ∈ L1 , M1 acepta la cadena x y si x no pertenece a L1 , M1 rechaza la cadena x. 

- si x ∈ L2 , M2 acepta la cadena x y si x no pertenece a L2 , M2 rechaza la cadena x.

Sea L = L1 ∪ L2 , ¿∃ M | L = L(M) y M siempre para? Sí, construyendo la máquina que se presenta en la figura: 

La construcción es correcta puesto que 

 - si x ∈ L1 AND x ∈ L2 ⇒ x ∈ L1 ∩ L2 = L (M1 y M2 aceptan ⇒ M acepta) 

 - si x no pertenece a L1 OR x no pertenece a L2 ⇒ x no pertenece a L1 ∩ L2 = L (M1 ó M2 rechazan ⇒ M rechaza). 

Por lo tanto, M siempre para y si x ∈ L, M acepta y si x no pertenece a L, M rechaza.