PUERTA | PUERTA-CS-2005 | Pregunta 55

Considere los idiomas:

L1 = {anbncm | n, m > 0} 
L2 = {anbmcm | n, m > 0} 

¿Cuál de las siguientes afirmaciones es falsa?
(A) L1 ∩ L2 es un lenguaje libre de contexto
(B) L1 U L2 es un lenguaje libre de contexto
(C) L1 y L2 son lenguajes libres de contexto
(D) L1 ∩ L2 es un lenguaje sensible al contexto

Respuesta: (A )
Explicación: podemos reconocer strings de un idioma dado usando una pila. Estos idiomas dados son independientes del contexto, por lo que también son sensibles al contexto.
Debido a que las CFL están cerradas bajo la propiedad de la Unión, la unión de idiomas dados también estará libre de contexto.
Pero las CFL no están cerradas bajo la propiedad Intersección, por lo que la intersección de dos CFL puede no ser CFL.
Dado que L1 y L2 son dos lenguajes libres de contexto, su intersección L1 ∩ L2 no está libre de contexto porque no podemos identificar las strings del lenguaje resultante con la ayuda de una pila:

L1 = { un ^norte segundo ^norte C ^metro  | norte > 0 y metro > 0 } y L2 = { un ^metro segundo ^norte do ^norte  | n > 0 y m > 0 }

L3 = L1 ∩ L2 = { un ^norte segundo ^norte C ^norte  | n > 0 } no está libre de contexto.

Entonces, la opción (a) es falsa.

Consulte la página de wikipedia para ver las propiedades de cierre.
Cuestionario de esta pregunta