Teoría de autómatas | conjunto 2

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

1) ¿Cuál es el complemento del lenguaje aceptado por la NFA que se muestra a continuación? Suponga que ∑ = {a} y ε es la string vacía 

(A) Φ 
(B) ε 
(C) un 
(D) {a, ε} 

Respuesta (B) 
El alfabeto dado ∑ contiene solo un símbolo {a} y el NFA dado acepta todas las strings con cualquier número de ocurrencias de ‘a’. En otras palabras, la NFA acepta a+. Por lo tanto, el complemento del lenguaje aceptado por los autómatas es una string vacía. 

2) Dado el lenguaje L = {ab, aa, baa}, ¿cuáles de las siguientes strings están en L*? 
….1) abaabaaabaa 
….2) aaaabaaaa 
….3) baaaaabaaaab 
….4) baaaaabaa 
(A) 1, 2 y 3 
(B) 2, 3 y 4 
(C) 1, 2 y 4 
(D) 1, 3 y 4 

Respuesta (C) 
Cualquier combinación de strings en el conjunto {ab, aa, baa} estará en L*. 
…. 1) «abaabaaabaa» se puede dividir como una combinación de strings en el conjunto {ab, aa, baa}. Las particiones son “ab aa baa ab aa” 
…. 2) «aaaabaaaa» se puede dividir como una combinación de strings en el conjunto {ab, aa, baa}. Las particiones son “aa ab aa aa” 
…. 3) “baaaaabaaaab” no se puede dividir como una combinación de strings en el conjunto {ab, aa, baa} 
…. 4) “baaaaabaa” se puede dividir como una combinación de strings en el conjunto {ab, aa, baa}. Las particiones son “baa aa ab aa” 

3) ¿Cuáles de los siguientes problemas son decidibles? 
….1) ¿Un programa dado alguna vez produce una salida? 
….2) Si L es un lenguaje libre de contexto, entonces ¿L’ (complemento de L) también es libre de contexto? 
….3) Si L es un lenguaje regular, ¿entonces L’ también es regular? 
….4) Si L es un lenguaje recursivo, entonces, ¿L’ también es recursivo?  
(A) 1, 2, 3, 4 
(B) 1, 2, 
(C) 2, 3, 4 
(D) 3, 4 

Respuesta (D) 
…. 1) Es una variación del problema de detención de la máquina de Turing y es indecidible. 
…. 2) Los lenguajes libres de contexto no se cierran bajo intersección y complemento. Vea esto para más detalles. 
…. 3) 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. 
…. 4) Los lenguajes recursivos están cerrados bajo complemento. Vea esto para más detalles. 

4) Considere el conjunto de strings en {0,1} en el que cada substring de 3 símbolos tiene como máximo dos ceros. Por ejemplo , 001110 y 011001 están en el idioma, pero 100010 no lo está. Todas las strings de longitud inferior a 3 también están en el idioma. A continuación se muestra un DFA parcialmente completado que acepta este idioma. 
 

Los arcos que faltan en el DFA son 

Respuesta (D) 
El estado ‘q’ es un estado trampa. Todos los demás estados son estados aceptados. En el estado 00, DFA debe moverse a ‘q’ para el símbolo de entrada 0. Todos los estados (sin captura) indican nombres que indican los caracteres vistos antes de llegar a ese estado en particular. La opción (D) es la única opción que sigue estas reglas. 

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.