PUERTA | Cuestionario para Sudo GATE 2021 | Pregunta 43

¿Cuál(es) de las siguientes opciones es(n) correcta(s)?

• (I) La unión de dos lenguajes sensibles al contexto es un lenguaje sensible al contexto.
• (II) Todo PDA no determinista se puede convertir en un PDA determinista equivalente.
• (III) El complemento de una lengua RE es también una lengua RE.
• (IV) Hay más de un DFA mínimo para cada idioma normal.

Nota: esta pregunta es de selección múltiple (MSQ).
(A) La afirmación (I) es falsa.
(B) La declaración (II) es falsa.
(C) La afirmación (III) es falsa.
(D) La afirmación (IV) es falsa.

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

1. La afirmación (I) es verdadera. La unión, intersección, concatenación de dos lenguajes sensibles al contexto es sensible al contexto, también el Kleene plus y el complemento de un lenguaje sensible al contexto son sensibles al contexto.
2. La afirmación (II) es falsa. Hay algunos PDA no deterministas que no se pueden convertir en PDA equivalentes debido a que no hay un algoritmo mecánico.
3. La afirmación (III) es falsa. A diferencia de los idiomas REC, los idiomas RE no están cerrados bajo complementan, lo que significa que el complemento del idioma RE no necesita ser RE.
4. La afirmación (IV) es falsa. Existe un DFA mínimo único para cada idioma normal.

Entonces, las opciones (A), (B) y (D) son correctas.
Cuestionario de esta pregunta