Grupo07IS17
lunes, 12 de mayo de 2008,4:08
La intersección de dos LREs es un LRE
Sean L1 y L2, L.R.E.-> existe M1,M2 | L1 = L(M1),L2 = L(M2), es decir, si x pertence a L1, M1 acepta y si x pertenece a L2, M2 acepta. Sea L = L1 intersección L2, ¿existe M | L = L(M)? Sí, construyendo M de la siguiente forma:

La construcción es correcta puesto que si x pertenece a L1 AND x pertenece a L2 ) x pertenece a (L1 intersección L2) = L .
(M1 y M2 aceptan -> M acepta) por lo tanto, si x pertenece a L, M acepta.
Si x no pertenece a L1 o L2 -> M1 o M2 no aceptan, por lo tanto M no acepta.
 
Posteado por: Jon o Jon Ander (según persona) Link ~


0 Opiniones:


Publicar un comentario ~ Atrás