Demostracion de que la interseccion de dos LRE´S es un LRE

Sean L1 y L2 dos lenguajes regulares enumerables.

Sea L el lenguaje interseccion entre L1 y L2.

Las clases Lre de los lenguajes recursivamente enumerables son cerradas respecto a la intersección.

X es una cadena que pertenece al lenguaje L.

Tenemos M1 que sabemos que es una maquina que acepta las cadenas del lenguaje L1.

Tenemos M2 que sabemos que es una maquina que acepta las cadenas del lenguaje L2.

Queremos saber si la interseccion de dos LRE´S tambien va a ser un LRE.

Con las maquinas M1 y M2 podemos construir una maquina M que nos diga si va a reconocer a una cadena X del lenguaje L.

Funcionamiento de M:

Le pasamos una cadena X a la maquina M.Para que la maquina acepte esa cadena la cadena X tiene que pertenecer al lenguaje L1 , lo acepta la maquina M1,y tambien al lenguaje L2, lo acepta la maquina M2. Cuando haya aceptado las dos maquinas entonces podremos decir que la acepta la maquina M y por lo tanto pertenecera al lenguaje L que es la interseccion de los lenguajes L1 y L2.

Sabemos por definicion que la interseccion de dos LRE´S son cerrados, por lo que sabemos que

X pertenece al lenguaje L que lo acepta la maquina M y que L es un LRE.