PUERTA | PUERTA CS 2011 | Pregunta 24

Sea P un lenguaje regular y Q un lenguaje libre de contexto tal que Q P. (Por ejemplo, sea P el lenguaje representado por la expresión regular p*q* y Q sea {p ⁿ q ⁿ |n N}). Entonces, ¿cuál de los siguientes es SIEMPRE regular?
(A) P Q
(B) P – Q
(C) * – P
(D) * – Q

(A) A
(B) B
(C) C
(D) D

Respuesta: (C)
Explicación:

1. P ∩ Q sería Q, dado que Q ⊆ P, por lo tanto libre de contexto pero no regular.
2. P − Q = P ∩ Q puede que ni siquiera sea un lenguaje libre de contexto, debido a las propiedades de cierre de los lenguajes libres de contexto.
3. Σ∗ − P es complemento equivalente de P, por lo tanto regular. Consulte las leyes de cierre de los lenguajes regulares.
4. Σ∗ − Q es complemento equivalente de Q, por lo tanto, es posible que ni siquiera sea un lenguaje libre de contexto.

Consulte las leyes de cierre de las LFC.

Referencia: http://quiz.geeksforgeeks.org/theory-of-computation-closure-properties-of-context-free-languages/

Consulte  https://www.geeksforgeeks.org/automata-theory-set-4/

Esta solución es aportada por Vineet Purswani.

Cuestionario de esta pregunta