Teoria de Automatas

1. Compare los conjuntos A y B y escoja la conclusión más adecuada a, b, c Casa, Si, No, a, b, c, 1, 2. a. A es alfabeto y B es lenguaje. b. B es alfabeto. c. Los dos son lenguajes.

2. Las cadenas conforman. a. Lenguajes. b. Autómatas. c. Expresiones regulares.

3. En la definición de un autómata finito determinista el símbolo Σ (sigma) se relaciona con: a. Procesador de transiciones. b. Símbolos de entrada. c. Estados de aceptación.

4. Una cadena. a. Es una secuencia de palabras. b. Está conformada por símbolos. c. Es parte de un alfabeto.

5. Un autómata finito NO determinista se compone de. a. Estados, aristas y un a cadena a reconocer. b. Estados, aristas y una función reconocedora. c. Alfabeto, aristas, estados y una función reconocedora.

6. Un autómata finito determinista permite. a. Estar en un solo estado a la vez. b. Estar en dos estados a la vez. c. Estar en más de dos estados a la vez.

7. Se denomina transición. a. Al paso de un símbolo a otro. b. Al paso de un estado a otro. c. El pasar de un símbolo a un estado.

8. Un autómata finito determinista. a. Permite reconocer cadenas. b. Permite reconocer frases completas. c. Solo permite reconocer símbolos.

9. De los siguientes conjuntos seleccione el que no puede considerarse un alfabeto. a. a, b, c. b. 0, 1. c. si, no, ya.

10. En el siguiente alfabeto: 0, 1, a, b, si, no existe un error, identifique cuál de las siguientes opciones indica el error. a. No se puede mezclar letras y números. b. No puede haber símbolos con dos letras. c. Se requiere al menos 2n símbolos.

11. ¿Cuál de las siguientes formas es la menos adecuada para representar un autómata?. a. Expresiones regulares. b. Gramáticas. c. Expresión gramatical.

12. Al comparar un AFND y un AFD. a. El AFD tiene capacidad para reconocer más cadenas. b. El AFND tiene capacidad para reconocer más cadenas. c. Reconocen la misma cantidad de cadenas.

13. La siguiente sección de código permite reconocer un identificador: Estado = 0 i = 0 Mientras no fin de archivo Símbolo = cadena [i] Si estado = 0 y símbolo = letra Estado = 1 Sino Si estado = 0 y símbolo = numero error Sino Si estado = 1 y símbolo = numero Estado = 1 Sino Si símbolo = “ “ (espacio en blanco) Presenta “éxito” terminar i = i + 1 fin mientras. a. que puede empezar con letras o con números. b. que puede empezar solo con números. c. que puede empezar solo con letras.

13. La siguiente sección de código permite reconocer un identificador: Estado = 0 i = 0 Mientras no fin de archivo Símbolo = cadena [i] Si estado = 0 y símbolo = letra Estado = 1 Sino Si estado = 0 y símbolo = numero error Sino Si estado = 1 y símbolo = numero Estado = 1 Sino Si símbolo = “ “ (espacio en blanco) Presenta “éxito” terminar i = i + 1 fin mientras a. que puede empezar con letras o con números b. que puede empezar solo con números c. que puede empezar solo con letras 14. A que expresión regular satisface la siguiente sección de pseudocódigo Estado = 0 I = 0 Mientras no fin de archivo Símbolo = cadena[i] Si estado = 0 y símbolo = “a” Estado = 0 Si estado = 0 y símbolo = “ “ (espacio en blanco) Terminar i = i + 1 Fin mientras. a. A+. b. A*. c. A* ó B.

15. Una expresión regular: a. Permite representar un alfabeto. b. Permite representar una cadena. c. Permite representar un lenguaje.

16. Un autómata está compuesto por. a. Estados. b. Estados y transiciones. c. Transiciones y reconocedores.

17. El siguiente gráfico, ¿qué expresión regular representa?. a. ( (a b) ó a ) c*. b. (abc*). c. (ab) ó ac*.

18. En una expresión regular, el símbolo * (asterisco). a. Indica que se repite cero veces. b. Indica que se repite cero o más veces. c. Indica que se repite una o mas veces.

19. Dada la siguiente expresión regular: (a ó b)+ c, ¿Cuál de las siguientes cadenas se puede generar?. a. ab. b. abc. c. c.

20. ¿Cuál de las siguientes expresiones regulares permite reconocer cadenas de unos y ceros de forma alterna?. a. 10+. b. (10)+. c. (10)*.

21. La expresión regular a* b* NO permite reconocer una de las siguientes cadenas, ¿Cuál de ellas?. a. “aa”. b. “a”. c. “ba”.

22. ¿Cuál de las siguientes expresiones regulares representa el autómata del gráfico?. a. (a ó b) ó (c o d). b. (ab) ó (cd). c. ( (a ó b) ó (c ó d) )*.

23. Para el siguiente autómata, dado el conjunto T= 2,3,5,7,14,15,20,16 y a=”e” ¿Cuál es el conjunto cerradura vacía de Mueve (T, a)?. a. 21, 18, 19, 15,17. b. 21, 18, 19, 15, 20, 16. c. 221, 17, 18, 19, 15, 20.

24. ¿Cuál de las siguientes expresiones regulares representa el autómata del gráfico?. a. a+ ó b+. b. ab. c. a ó b.

25. La expresión regular ab+ permite reconocer la cadena. a. “abbb”. b. “bbb”. c. “a.

26. La expresión regular a+ b+ permite reconocer la cadena. a. “ba”. b. “abab”. c. “aabb”.

27. La clausura aplicada a un lenguaje regular da como resultado. a. Un lenguaje regular. b. Un lenguaje no regular. c. No se puede aplicar clausura.

28. La intersección de dos lenguajes regulares da como resultado: a. Un lenguaje regular. b. Un lenguaje no regular. c. No es posible obtener la intersección de dos lenguajes regulares.

29. La diferencia entre dos lenguajes regulares da como resultado. a. Un lenguaje regular. b. Un lenguaje no regular. c. No se puede aplicar diferencia.

30. El homomorfismo de un Lenguaje Regular arroja como resultado. a. Un lenguaje regular. b. Un lenguaje no regular. c. No se puede aplicar homomorfismo.

31. Para el siguiente autómata, Dado el conjunto T= 0, 1, 2, 3, 5 y a=”a” ¿Cuál es el conjunto Mueve (T, a)?. a. 0. b. 5. c. 4.

32. Para el siguiente autómata, dado el conjunto T= 0, 1, 2, 3, 5 y a=”a” ¿Cuál es el conjunto Cerradura vacía de Mueve (T, a)?. a. 4, 7, 8, 9, 10. b. 7, 8, 9, 10, 2, 3, 5. c. 4, 7, 8, 2, 3, 5, 1.

33. Para el siguiente autómata, dado el conjunto T= 1, 2, 3, 5, 10, 8, 11 y a=”b” ¿Cuál es el conjunto Mueve (T, a)?. a. 4. b. 9. c. 6.

34. Dado el siguiente autómata, ¿El conjunto cerradura vacía del estado 2 es?. a. (1,2,8,9,10). b. (3, 4, 5). c. (2, 3, 5).

35. Para el siguiente autómata, dado el conjunto T= 1, 2, 3, 5, 10, 8, 11 y a=”e” ¿Cuál es el conjunto Mueve (T, a)?. a. 17. b. 21. c. 20.

36. Para el siguiente autómata, dado el conjunto T= 1, 2, 3, 5, 7 y a=”c” ¿Cuál es el conjunto Mueve (T, a)?. a. 4. b. 6. c. 8.

37. Para el siguiente autómata, dado el conjunto T= 12,13,14,1510,8,11 y a=”c” ¿Cuál es el conjunto cerradura vacía de Mueve (T, a)?. a. 9,13,14,15,20,16,10,8,11. b. 4,7,14,15,20,16,2,3,5,10. c. 4,7,14,15,20,16,2,3,5,10.

38. Para el siguiente autómata, dado el conjunto T= 2,3,5,7,14,15,20,16 y a=”f” ¿Cuál es el conjunto cerradura vacía de Mueve (T, a)?. a. 17,19, 20, 21,15. b. 17,18,19,15,20,16. c. 17,18,1920,21,15,16.

39. Para el siguiente autómata, dado el conjunto T= 1, 2, 3, 5, 7 y a=”c” ¿Cuál es el conjunto cerradura vacía de Mueve (T, a)?. a. 8,9,10, 11, 2, 3, 5, 7. b. 2, 3, 5, 7, 8, 9,10. c. 2,3,5,7,9,10.

40. Para el siguiente autómata, dado el conjunto T= 2,3,5,7,14,15,20,16 y a=”a” ¿Cuál es el conjunto cerradura vacía de Mueve (T, a)?. a. 4, 7, 21, 18, 19, 15,17. b. 21, 18, 19, 15, 20, 16. c. 4,7,2,3,5,14,15,20,16.