Teoría de autómatas | conjunto 4

Se han hecho las siguientes preguntas en el examen GATE CS 2011.

1) 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 &in ;N}). Entonces, ¿cuál de los siguientes es SIEMPRE regular?
(A) P ∩ Q
(B) P – Q
(C) ∑* – P
(D) ∑* – Q

Respuesta (C)
La expresión ∑* – P representa el complemento de P que es un lenguaje regular. El complemento de los lenguajes regulares también es regular. Entonces, se puede obtener un DFA que acepte el complemento de L, es decir, ∑* – L, intercambiando sus estados de aceptación con sus estados de no aceptación.

2) Considere el lenguaje L1, L2, L3 como se indica a continuación.
L1={0 ^p 1 ^q | p, q & en; N}
L2={0 ^p 1 ^q | p, q & en; N y p=q}
L3={0 ^p 1 ^q 0 ^r | p,q,r ∈N y p=q=r}
¿Cuál de las siguientes afirmaciones NO ES VERDADERA?
(A) Push Down Automata (PDA) se puede usar para reconocer L1 y L2
(B) L1 es un lenguaje normal
(C) Los tres lenguajes son independientes del contexto
(D) La máquina de Turing se puede usar para reconocer los tres lenguajes

Respuesta (C)
El lenguaje L3 no está libre de contexto. Consulte esto para obtener más detalles.

3) La definición de un idioma L con el alfabeto {a} se da a continuación. L= { un ^nk | k > 0, y n es una constante entera positiva} ¿Cuál es el número mínimo de estados necesarios en un DFA para reconocer L?
(A) k+1
(B) n+1
(C) 2 ⁿ⁺¹
(D) 2 ^k+1

Respuesta (B)
Tenga en cuenta que n es una constante y k es cualquier número entero positivo. Por ejemplo, si n se da como 3, entonces el DFA debe poder aceptar 3a, 6a, 9a, 12a, .. Para construir tal DFA, necesitamos 4 estados.

Consulte GATE Corner para ver todos los documentos/soluciones/explicaciones del año anterior, programa de estudios, fechas importantes, notas, etc.

Escriba comentarios si encuentra que alguna de las respuestas/explicaciones es incorrecta, o si desea compartir más información sobre los temas discutidos anteriormente.