Teoría de autómatas | conjunto 6

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

1) Sea L={w ∈ (0 + 1)*|w tiene un número par de 1s}, es decir, L es el conjunto de todas las strings de bits con un número par de 1s. ¿Cuál de las siguientes expresiones regulares representa L?
(A) (0*10*1)*
(B) 0*(10*10*)*
(C) 0*(10*1*)*0*
(D) 0*1(10*1)*10 *

Respuesta (B)
La opción (A) es incorrecta porque no puede aceptar “110”
La opción (C) es incorrecta porque acepta una string con un solo 1.
La opción (D) es incorrecta porque no puede aceptar 11101

2) Sea L1 un lenguaje recursivo. Sean L2 y L3 lenguajes recursivamente enumerables pero no recursivos. ¿Cuál de las siguientes afirmaciones no es necesariamente cierta?
(A) L2 – L1 es recursivamente enumerable.
(B) L1 – L3 es recursivamente numerable
(C) L2 ∩ L1 es recursivamente numerable
(D) L2 ∪ L1 es recursivamente numerable

Respuesta (B)

3) Considere los lenguajes L1={0 ⁱ 1 ^j | i != j}, L2={0 ⁱ 1 ^j | yo = j}, L3 = {0 ^yo 1 ^j | yo = 2j+1}, L4 = {0 ^yo 1 ^j | i != 2j}. ¿Cuál de las siguientes afirmaciones es verdadera?
(A) Solo L2 está libre de contexto
(B) Solo L2 y L3 están libres de contexto
(C) Solo L1 y L2 están libres de contexto
(D) Todos están libres de contexto

Respuesta (D)
Se puede construir un autómata pushdown para los cuatro idiomas.

4) Sea w cualquier string de longitud n {0,1}*. Sea L el conjunto de todas las substrings de w. ¿Cuál es el número mínimo de estados en un autómata finito no determinista que acepta L?
(A) n-1
(B) n
(C) n+1
(D) 2n-1

Respuesta (C)
Necesitamos un mínimo de n+1 estados para construir NFA que acepte todas las substrings de una string binaria. Por ejemplo, seguir NFA acepta todas las substrings de «010» y tiene 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.