Sea L un lenguaje regular y M un lenguaje libre de contexto, ambos sobre el alfabeto Σ. Sean Lc y Mc los complementos de L y M respectivamente. ¿Cuál de las siguientes afirmaciones sobre el lenguaje Lc∪ Mc es VERDADERA?
(A) Es necesariamente regular pero no necesariamente libre de contexto
(B) Es necesariamente libre de contexto.
(C) Es necesariamente no regular.
(D) Ninguna de las anteriores
Respuesta: (D)
Explicación:
Proposición:
L es un lenguaje regular
M es un lenguaje libre de contexto
Derivación:
L_c unión M_c = complemento{L intersección M}
Ahora, L intersección M es una CFL de acuerdo con las leyes de cierre de las CFL, es decir, la intersección de una CFL con RL es siempre una CFL.
Pero, el complemento {L intersección M} podría no ser un CFL porque el complemento sobre CFL no garantiza un CFL. Incluso puede ser un RL o incluso puede estar fuera del círculo CFL. Sin duda, será un lenguaje sensible al contexto, pero no se puede decir nada más al respecto.
Conclusión:
Considerando la derivación anterior, ninguna de las afirmaciones es verdadera. Por lo tanto, la respuesta correcta sería (D) Ninguna de las anteriores.
Artículo relacionado :
https://www.geeksforgeeks.org/closure-properties-of-context-free-languages/
Esta solución es aportada por .
Cuestionario de esta pregunta
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA