Teoría de autómatas | conjunto 5

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

1) S –> aSa| bSb| un| b ;El lenguaje generado por la gramática anterior sobre el alfabeto {a,b} es el conjunto de
(A) Todos los palíndromos.
(B) Todos los palíndromos de longitud impar.
(C) Strings que comienzan y terminan con el mismo símbolo
(D) Todos los palíndromos de longitud uniforme.

Respuesta (B)
Las strings aceptadas por idioma son {a, b, aaa, bbb, aba, bab, ..}. Todas estas strings son palíndromos de longitud impar.

2) ¿Cuál de los siguientes idiomas sobre el alfabeto {0,1} se describe con la expresión regular: (0+1)*0(0+1)*0(0+1)*?
(A) El conjunto de todas las strings que contienen la substring 00.
(B) El conjunto de todas las strings que contienen como máximo dos 0.
(C) El conjunto de todas las strings que contienen al menos dos 0.
(D) El conjunto de todas las strings que comienzan y terminan con 0 o 1.

Respuesta (C)
La expresión regular tiene dos 0 rodeados por (0+1)*, lo que significa que las strings aceptadas deben tener al menos 2 0.

3) ¿Cuál de las siguientes es FALSA?
(A) Existe un DFA mínimo único para cada idioma regular
(B) Cada NFA se puede convertir en un PDA equivalente.
(C) El complemento de todo lenguaje libre de contexto es recursivo.
(D) Todo PDA no determinista se puede convertir en un PDA determinista equivalente.

Respuesta (D)
El PDA determinista no puede manejar lenguajes o gramáticas con ambigüedad, pero NDPDA puede manejar lenguajes con ambigüedad y cualquier gramática libre de contexto. Por lo tanto, cada PDA no determinista no se puede convertir en un PDA determinista equivalente.

4) Haga coincidir todos los elementos del Grupo 1 con las opciones correctas de las que se dan en el Grupo 2.

Group 1                          Group 2
P. Regular expression        1. Syntax analysis
Q. Pushdown automata         2. Code generation
R. Dataflow analysis         3. Lexical analysis
S. Register allocation       4. Code optimization

(A) P-4. Q-1, R-2, S-3
(B) P-3, Q-1, R-4, S-2
(C) P-3, Q-4, R-1, S-2
(D) P-2, Q-1, R-4, S-3

Respuesta (B)

5) . Sea L = L1 ∩ L2, donde L1 y L2 son lenguajes como se definen a continuación:
L1 = {a ^m b ^m ca ⁿ b ⁿ | metro, norte >= 0 }
L2 = {a ^yo segundo ^j c ^k | i, j, k >= 0 }
Entonces L es
(A) No recursivo
(B) Regular
(C) Libre de contexto pero no regular
(D) Enumerable recursivamente pero no libre de contexto.

Respuesta (C)
El lenguaje L1 acepta strings {c, abc, abcab, aabbcab, aabbcaabb,…} y L2 acepta strings {a, b, c, ab, abc, aabc, aabbc,…}. La intersección de estos dos idiomas es L1 ∩L2 = {a ^k b ^k c | k >= 0} que no tiene contexto, pero no es regular.

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.