PUERTA | GATE-CS-2017 (Conjunto 1) | Pregunta 52

Considere los siguientes idiomas sobre el alfabeto ∑= {a,b,c}. Sea L ₁ = {un ^norte segundo ^norte C ^metro | metro, norte >= 0 } y L ₂ = {un ^metro segundo ^norte do ^norte | m, n >= 0}.

¿Cuáles de los siguientes son lenguajes libres de contexto?

I. L ₁ ∪ L ₂
II. L ₁ ∩ L ₂

(A) Solo I
(B) Solo II
(C) I y II
(D) Ni I ni II

Respuesta: (A)
Explicación: La unión de lenguaje libre de contexto es también lenguaje libre de contexto.

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

L3 = L1 ∪ L2 = { un norte segundo ^norte C ^{metro ∪} un ^{metro segundo} norte C ^norte | n >= 0, m >= 0 } también es independiente del contexto.

L1 dice que el número de a debe ser igual al número de b y L2 dice que el número de b debe ser igual al número de c. Su unión dice que cualquiera de las dos condiciones es verdadera. Por lo tanto, también es un lenguaje libre de contexto.

La intersección de CFG puede o no ser CFG.
L3 = L1 ∩ L2 = { un ^norte segundo ^norte C ^norte | n >= 0 } no necesita estar libre de contexto.

Esta solución es aportada por parul sharma .

Cuestionario de esta pregunta