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

Para demostrar este enunciado, nos hemos basado en teoremas anteriores, sobretodo en el 7.4, La unión de dos lenguajes recursivos es un lenguaje recursivo.

Para la realización de la demostración de este teorema, nos basamos en que para que un lenguaje intersección de dos lenguajes, solo acepta cadenas que pertenezcan a ambos lenguajes. Por tanto, procedemos a la demostración:

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 ∉ a L1 , M1 rechaza la cadena x.

- si x ∈ L2 , M2 acepta la cadena x y si x ∉ 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 ∉ L1 OR x ∉ L2 ⇒ x ∉ L1 ∩ L2 = L (M1 ó M2 rechazan ⇒ M rechaza).

Por lo tanto, M siempre para y si x ∈ L, M acepta y si x ∉ L, M rechaza.

PD: Espero que no nos hagas pagar © por tus apuntes Gloria :p.