La interseccion de dos LRE forman un LRE

Sean L1 y L2, L.R.E.->existe M1,M2 L1 = L(M1),L2 = L(M2), es decir, si x є L1,
M1 acepta y si x є L2, M2 acepta.

Sea L = L1 U L2, ¿existe M L = L(M)? Sí, construyendo M de la siguiente forma:

Nosotros partimos de 2 lenguajes, L1 y L2, los cuales є a L, tal que L= L1 interseccion L2. Donde L1 es reconocido por la primera maquina, M1 y L2 es reconocido por la segunda maquina, M2. En primer lugar partimos de una determinada cadena, X, el primer paso es comprobar si esa cadena es reconocida por la primera maquina, para saber si pertenece a L1, si fuera aceptada, se haría el mismo proceso con M2, y si finalmente pertenece a L2, se puede decir que X є a L, dando lugar a que є también a la interseccion de los dos lenguajes.