PUERTA | PUERTA CS 2021 | Juego 2 | Pregunta 22

Sea L ₁ un lenguaje regular y L ₂ un lenguaje libre de contexto. ¿Cuál de los siguientes lenguajes es/son libres de contexto?
(A) L ₁ ∩L ₂ ‘
(B) (L ₁ ‘∪L ₂ ‘)’
(C) L ₁ ∪(L ₂ ∪L ₂ ‘)
(D) (L ₁ ∩L ₂ )∪(L ₁ ∩L ₂ )

Respuesta: (B) (C) (D)
Explicación:

• (A) Unión regular CSL = CSL. Opción incorrecta
• (B) (L1’U L2′)’ se puede escribir como (L1 ∩ L2)”. Entonces, después de simplificar, sería L1 ∩ L2, por lo tanto, es CFL. Opción correcta.
• (C) L2 U L2′ significa usando lógica de complemento su conjunto universal representado por Σ*. Entonces, cualquier unión con Σ* es Σ* en sí misma y Σ* es regular, por lo tanto, también es CFL por defecto. Opción correcta
• (D) (L1∩L2)∪(L1∩L2), Aquí observamos claramente CFL U CFL = CFL. Opción correcta.

Cuestionario de esta pregunta