AUTOMATAS II BIM F-V6

1. El lenguaje de una gramática G, está representado por. El conjunto de cadenas que la G puede derivar. El conjunto de reglas que conforman la G. El conjunto de cadenas y de reglas de la G.

2. La derivación: a. Permite construir sentencias. b. Permite reemplazar reglas. c. Permite comprobar cadenas.

3. ¿Cuál de las siguientes elementos no es parte de la definición formal de una gramática ?. V -> conjunto de no terminales. X -> orden de derivación de las reglas. S ->Símbolo inicial.

4. Un lenguaje independiente de contexto. Es más amplio que uno regular. Es mas débil que uno regular. Tiene la misma potencia que uno regular.

5. 1. Dada la gramática : S -> ASB S -> A A -> a A -> vacio B -> b Elabore los árboles de derivación necesarios y determine ¿Cuál de las siguientes cadenas no puede ser generada?. a. “b”. b. “ab”. c. “a”.

6. ¿Cuál de las siguientes gramáticas permite generar una sentencia para declarar variables como la siguiente?. int a,b,c;. VAR -> TIPO LISTA ; TIPO -> int TIPO -> char LISTA -> id LISTA -> id , LISTA. VAR -> int VARIABLES VAR -> char VARIABLES VARIABLES -> id, VARIABLES ; VARIABLES -> id ,. VARIABLES -> int LISTAVAR VARIABLES -> char LISTAVAR LISTAVAR -> id, VARIABLES LISTAVAR -> id.

7. 1. Dada la gramática siguiente: E -> E + T E -> T T -> T * F T -> F F -> numero (numero es un terminal) F -> (E) Elabore los árboles de derivación necesarios y determine ¿Cuál de las siguientes cadenas no se puede generar?. (numero * numero) * (numero * numero). (numero ) + numero + numero. (numero) * numero) + (numero numero).

8. 1. Dada la gramática : S -> Ab A -> b A -> a ¿Cuál de las siguientes cadenas no puede ser generada?. “ab”. “bb”. “ba”.

9. 1. Dada la gramática : IF -> C IF ELSE IF -> if (condicion) B B -> sentencia ELSE -> else B ¿Cuál de las siguientes cadenas no puede ser generada?. “if condicion sentencia”. “if (condicion) sentencia else sentencia”. “if (condicion) sentencia”.

10. ¿Cuál de las siguientes gramáticas permite crear la sentencia: locomotora vagon vagon vagon?. <TREN> --> locomotora <RESTOTREN> <RESTOTREN> --> vagon <RESTOTREN> <RESTOTREN> --> vagon. <TREN> --> locomotora <RESTOTREN> <LOCOMOTORA> --> locomotora <RESTOTREN> --> vagon <RESTOTREN> --> vagon vagon. <TREN> --> locomotora <RESTOTREN> <LOCOMOTORA> --> locomotora <RESTOTREN> --> vagon <RESTOTREN> --> vagon.

11. Dada la gramática : S -> aSb S -> BaC B -> a C -> b Elabore los árboles de derivación necesarios y determine ¿Cuál de las siguientes cadenas puede ser generada?. “aaaabbbb”. “aaaabbb”. “aaabbbb”.

12. 1. Dada la siguiente gramática: Regla 1: IFC -> IF ELSE Regla 2: IF -> if (condicion) B Regla 3: B -> sentencia Regla 4: ELSE -> else B En la siguiente sentencia: if condicion sentencia else sentencia ¿Cuál es el error?. No correctamente se aplica regla 2. No correctamente se aplica regla 3. No correctamente se aplica regla 1.

13. Cada regla de la función de transición de un autómata de pila tiene dos partes, la parte derecha está formada por: Cima de la pila, estado origen. Estado origen, Valor a escribir en la cima de la pila. Estado destino, Valor a escribir en la cima de la pila.

14. En un autómata de pila, la memoria la constituye la pila. Para escribir en esta pila se cuenta con un : . Lenguaje de la pila. . Alfabeto de la pila. . Gramática de la pila.

15. Un autómata de pila tiene. Un estado inicial. Dos estados iniciales. Varios estados iniciales.

16. La función de transición de un autómata de pila está formada por: Reglas. Símbolos. Estados.

17. ¿Cuál de los siguientes componentes no es parte de la definición formal de un autómata de pila?. Un conjunto finito de estados. Alfabeto de transición. Símbolo inicial.

18. ¿Cuál de los siguientes componentes no es parte de la definición formal de un autómata de pila?. a. Conjunto de estados. b. Alfabeto dual. c. Función de transición.

19. Dado el siguiente autómata de pila: Regal 1: (q0, 1, Z) → (q1, Z) Regla 2: (q0, 0, Z) →(q1, Z) Regla 3: (q1, 1, Z) →(q0, Z) Regla 4: (q1, 0, Z) → (q0, Z). Se reconocen cadenas que empiezan con 1. Se reconocen cadenas que empiezan con 0. Se reconocen cadenas que empiecen con 1 o con 0.

20. La siguiente regla significa: (q1, “a”, X) -> (q1, vacio). Que reconoce el símbolo “a” en el mismo estado. Que reconoce el símbolo “a” cuando la pila está vacía. Que reconoce “a” y coloca X en la cima de la pila.

21. De los siguientes autómatas, ¿cuál es el más apropiado para reconocer cadenas de unos que terminen con #?. (q1, “1”, X) -> (q1, X) (q1, “#”, X) -> (q2, reconocer). (q1, “1”, X) -> (q2, 1X) (q2, “1”, X) -> (q2, vacío) (q2, “1”, X) -> (q2, reconocer). (q1, “1”, X) -> (q2, 1X) (q2, “#”, X) -> (q2, reconocer).

22. Dado el siguiente autómata de pila: (q1, “1”, X) -> (q2, ZX) (q2, “0”, Z) -> (q2, vacío) (q3, “#”, X) -> (reconoce). Reconoce cadenas del tipo “1010”. No reconoce cadenas de tipo “1010”. No pasa del estado q2 al estado q3.

23. 1. La siguiente regla significa: (q1, “a”, X) -> (q1, vacio). Que reconoce el símbolo “a” en el mismo estado. Que reconoce el símbolo “a” cuando la pila está vacía. Que la cima de la pila se reemplaza por vacío.

24. De las siguientes reglas, ¿cuál es la más apropiada para reconocer un símbolo 1 y registrar su reconocimiento en la pila?. (q1, “0101”, Y) -> (q2, 1X). (q1, “1”, X) -> (q2, 1X). (q1, “1010”, Y) -> (q2, vacío).

25. 1. La siguiente regla significa: (q1, “0”, X) -> (q2, ZX). Que reconoce cadenas que empiezan con 1. Que la cima de la pila X se reemplaza por ZX. Que la cima de la pila Z se reemplaza por X.

26. 1. Dado el siguiente autómata de pila: (q1, “0”, X) -> (q2, ZX) (q2, “1”, Z) -> (q2, vacío). Puede reconocer la cadena “1010” y al final la pila queda con ZX. Puede reconocer la cadena “010” y al final la pila queda con ZX. No puede reconocer la cadena “010” por que la pila queda vacía.

27. Para que una gramática sea expresada en forma normal de Chomsky. No debe tener más de 3 terminales en el lado derecho de cada regla. No debe tener más de un terminal en el lado derecho de cada regla. No puede tener más de dos símbolos en el lado izquierdo de cada regla.

28. Para que una gramática quede en forma normal de Chomsky, en la parte derecha debe tener: Máximo un terminal. Máximo dos terminales. Cualquier número de terminales.

29. Para que una gramática quede en forma normal de Chomsky, en la parte derecha debe tener: un NO terminal. dos NO terminales. varios NO terminales.

30. Para que una gramática quede en forma normal de Chomsky. No debe tener más de 3 terminales. No debe tener símbolos complementarios. No debe tener símbolos inútiles.

31. De las siguientes reglas, ¿Cuál cumple los requisitos para estar en forma normal de Chomsky?. OPERADOR ->>. OPERADOR -> id > id. OPERADOR -> id == id.

32. La siguiente gramática tiene un error en una de las reglas, este error no le permite estar en forma normal de Chomsky. S -> BC B -> a C -> C ¿En que regla está el error?. a. Regla 1. b. Regla 2. c. Regla 3.

33. ¿Cuál de las siguientes gramáticas está en forma normal de Chomsky?. S -> AB A -> 1A B -> 0. S -> AB A -> 1 B -> 0. S -> AB A -> 1A B -> 0B.

34. La siguiente gramática tiene un error en una de las reglas, este error no le permite estar en forma normal de Chomsky. S ->AB A -> aA B -> BB B -> b ¿En que regla está el error?. Regla 1. Regla 2. Regla 3.

35. Dada la siguiente gramática: S -> AB A -> C C -> 1 B ->0 Si se requiere eliminar las producciones unitarias, ¿Qué regla hay que eliminar?. Regla 2. Regla 3. Regla 4.

36. Dada la siguiente gramática: W -> while ( COND ) BLOQUE COND -> id OPERADOR id OPERADOR -> COMPARADOR COMPARADOR -> > COMPARADOR -> < COMPARADOR -> == BLOQUE -> vacío BLOQUE -> UNASENTENCIA, BLOQUE Para que la gramática quede en forma normal de Chomsky es necesario eliminar las producciones vacías, en este caso, ¿Qué regla hay que eliminar?. Regla 3. Regla 7. Regla 8.

37. Dada la siguiente gramática: E -> E +T E -> T T -> T * F T -> F F -> id Si se requiere eliminar las producciones unitarias, ¿Qué conjuntos de reglas hay que eliminar?. Regla 2, regla 3, regla 4. Regla 1, regla 2, regla 3. Regla 2, regla 4, regla 5.

38. Dada la Gramática S -> main BLOQUE. BLOQUE -> id++ Al convertirla en forma normal de Chomsky, ¿Cuál sería el resultado?. S -> MAIN BLOQUE MAIN -> main BLOQUE -> id++. S -> main BLOQUE BLOQUE -> SENTENCIA SENTENCIA -> id++. S -> MAIN SENTENCIAS MAIN -> main SENTENCIAS -> BLOQUE BLOQUE -> id++.

39. En la siguiente gramática: BLOQUE -> INICIO RESTO INICIO -> RESTO -> UNAINSTRUCCIÓN FIN FIN -> BLOQUE BLOQUE -> UNAINSTRUCCION UNAINSTRUCCION -> WHILE UNAINSTRUCCION -> FOR ¿Qué grupos de reglas hay que eliminar para que la gramática quede en forma normal de chomsky?. Regla 1, regla 3, regla 5, regla 6. Regla 2, regla 4, regla 5, regla 6. Regla 4, regla 5, regla 6, regla 7.

40. Dada la Gramática S -> aB. Al convertirla en forma normal de Chomsky, ¿Cuál sería el resultado?. S -> AB A -> a. S -> A A -> a. S -> a.

Las gramáticas tienen un alfabeto. V. F.

Los terminales de una gramática se representan con letras mayúsculas. V. F.

Terminales y no terminales de una gramática pueden derivarse. V. F.

Los no terminales de una gramática se denominan hojas cuando aparecen en un árbol de derivación. V. F.

Una regla gramatical tiene una parte izquierda y una parte derecha, la parte derecha reemplaza a la izquierda cuando se produce una derivación. V. F.

En la derivación por la izquierda, siempre se descompone (o deriva) el símbolo terminal de la izquierda. V. F.

El símbolo inicial de una gramática es un no terminal. V. F.

Derivación es un proceso en el que se van reemplazando la parte izquierda de una regla por la parte derecha de la misma. V. F.

Una gramática es ambigua cuando se puede generar más de un árbol para una misma regla. V. F.

En las gramáticas que reconocen lenguajes regulares el número de terminales de la parte izquierda es igual al número de terminales de la parte derecha. V. F.

En base a la siguiente gramática: S→aAS | B A→bc B→cdS |cd La cadena “cd” si puede ser reconocida. V. F.

En base a la siguiente gramática: 1. S→aAS | B 2. A→bc 3. B→cdS |cd La cadena “abcd” si puede ser reconocida. V. F.

En base a la siguiente gramática: S→aAS | B A→bc B→cdS |cd La cadena “abc” si puede ser reconocida. V. F.

En base a la siguiente gramática: S→aAS | B A→bc B→cdS |cd La cadena “cdcd” si puede ser reconocida. V. F.

En base a la siguiente gramática: S→aAS | B A→bc B→cdS |cd La cadena “bcd” si puede ser reconocida. V. F.

Una gramática independiente de contexto tiene como máximo dos no terminales en la parte derecha. V. F.

La regla “A→ a” es válida para una gramática en forma normal de chomsky. V. F.

Un autómata de pila reconoce cadenas. V. F.

La regla “A→aSb” es válida en una gramática en forma normal de chomsky. V. F.

Un autómata de pila tiene una estructura adicional que se denomina pila. V. F.

La pila de un autómata de pila cuenta con un alfabeto. V. F.

El argumento de recibe la función de transición de un autómata de pila es un conjunto con tres elementos que son: el estado, el símbolo de entrada y la cadena de entrada. V. F.

El autómata de pila puede tener uno o más estados iniciales. V. F.

La función de transición de un autómata de pila retorna como un conjunto con dos elementos que son: el estado de destino y la cadena que reemplaza el elemento de la cima de la pila. V. F.

En el reconocimiento por estado final se da cuando el autómata se encuentra en uno de los estados del conjunto de estados finales. V. F.

El reconocimiento por pila vacía implica que la pila tiene varios elementos y en su cima el elemento vacío. V. F.

En la siguiente gramática: A→BC C→D D→c La regla C→D es una producción unitaria. V. F.

En la siguiente gramática: A→BC C→D D→c La regla D→c es válida en una forma normal de Chomsky. V. F.

En la siguiente gramática: A→BC C→D D→c La regla A→BC es válida en una forma normal de Chomsky. V. F.

1. Un lenguaje independiente de contexto. Reconoce más cadenas que un lenguaje regular. Reconoce menos cadenas que un lenguaje regular. Tiene las mismas cadenas que un lenguaje regular.

2. Una gramática siempre tiene en la parte izquierda de la primera regla un símbolo, este símbolo es: a. Un Terminal. b. Una regla. c. Un no terminal.

3. Un símbolo terminal se utiliza para. a. Construir sentencias. b. Construir cadenas. c. Construir reglas.

4. El símbolo inicial de la gramática. a. Es un terminal. b. Es un no terminal. c. Es una regla.

5. Dada la gramática <FOR> ---> for (id=val; id <OPRELACIONAL> id; id++) <BLOQUE> <OPRELACIONAL> ---> < <OPRELACIONAL> ---> > <OPRELACIONAL> ---> == <BLOQUE> ---> <UNASENTENCIA> <BLOQUE> <BLOQUE> ---> <UNASENTENCIA> <UNASENTENCIA> ---> id++ ¿Cuál de las siguientes sentencias se puede generar?. a. For (a=1; a<10; a++) C++ D++ E++. b. For (a=1; a<10; a++) C++; D++; E++;. c. For (a=1, a<10, a++) C++ D++ E++.

6. ¿Cuál de las siguientes gramáticas permite crear la sentencia: locomotora vagon vagon vagon?. a. <TREN> --> locomotora <RESTOTREN> <RESTOTREN> --> vagon <RESTOTREN> <RESTOTREN> --> vagon. b. <TREN> --> locomotora <RESTOTREN> <LOCOMOTORA> --> locomotora <RESTOTREN> --> vagon <RESTOTREN> --> vagon vagon. c. <TREN> --> locomotora <RESTOTREN> <LOCOMOTORA> --> locomotora <RESTOTREN> --> vagon <RESTOTREN> --> vagon.

7. 1. Dada la gramática : S -> Ab A -> b A -> a ¿Cuál de las siguientes cadenas no puede ser generada?. a. “ab”. b. “bb”. c. “ba”.

8. 1. Dada la gramática : S -> aSb S -> BC B -> a C -> b Elabore los árboles de derivación necesarios y determine ¿Cuál de las siguientes cadenas no puede ser generada?. a. “aaaaabbbb”. b. “aaabbb”. c. “aaaabbbb”.

9. Dada la siguiente gramática S -> int M B M -> main B -> U B -> U B U -< F F -< for (id=val; id < val; id++) B B -> id++; ¿Cuál de las siguientes sentencias no puede ser generada?. a. int main for (a=5;a<20;a++) x++;. b. int main for (a=5;a<20;a++) x++; x++. c. int main a; a; a.

10. Dada la gramática siguiente: S -> int M B M -> main B -> U B -> U B U -> a; ¿Cuál de las siguientes sentencias no puede ser generada?. a. int main a. b. int main a; a;. c. int main a; a; a;.

11. 1. Dada la gramática siguiente: E -> E + T E -> T T -> T * F T -> F F -> valor (valor se puede reemplazar por cualquier número) ¿Cuál de las siguientes cadenas no se puede generar?. a. 4 + 6. b. 3 * 7. c. 2 * 3 - 2.

12. ¿Cuál de las siguientes gramáticas permite generar cadenas de unos y ceros alternados?. a. X -> XY10 X -> 1 Y -> 0 X -> vacio. b. X -> 10X X -> vacio. c. X -> 1Y0 Y -> 0X0 Y -> vacio.

13. La función de transición de un autómata de pila está formada por: a. Reglas. b. Símbolos. c. Estados.

14. Cada regla de la función de transición de un autómata de pila tiene dos partes, la parte derecha está formada por: a. Cima de la pila, estado origen. b. Estado origen, Valor a escribir en la cima de la pila. c. Estado destino, Valor a escribir en la cima de la pila.

15. El autómata de pila tiene. a. Dos alfabetos. b. Tres alfabetos. c. Cuatro alfabetos.

16. Un autómata de pila tiene. a. Un estado inicial. b. Dos estados iniciales. c. Varios estados iniciales.

17. ¿Qué es lo que diferencia a un autómata de pila de un autómata finito?. a. La capacidad de entrada. b. La capacidad para recordar. c. La inclusión de una función de transición.

18. ¿Cuál de los siguientes componentes no es parte de la definición formal de un autómata de pila?. a. Un conjunto finito de estados. b. Alfabeto de transición. c. Símbolo inicial.

19. Dado el siguiente autómata de pila: (q1, “1”, X) -> (q2, ZX) (q2, “0”, Z) -> (q2, vacío) (q3, “#”, X) -> (reconoce). a. Reconoce cadenas del tipo “1010”. b. No reconoce cadenas de tipo “1010”. c. No pasa del estado q2 al estado q3.

20. De las siguientes reglas, ¿cuál es la más apropiada para reconocer un símbolo 1 y registrar su reconocimiento en la pila?. a. (q1, “0101”, Y) -> (q2, 1X). b. (q1, “1”, X) -> (q2, 1X). c. (q1, “1010”, Y) -> (q2, vacío).

21. Dado el siguiente autómata de pila: (E1, “a”, X) -> (E2, ZX) (E2, “b”, Z) -> (E3, vacío) (E3, “c”, X) -> (E4, ZX) (E4, “#”, Z) -> (E4, reconoce) Se necesita reconocer la cadena “abc”# (#indica que la cadena termina) Al ejecutar el autómata, el resultado es: a. Se reconoce la cadena. b. No se puede reconocer la cadena. c. La regla 2 debe enviar al estado E3.

22. 1. La siguiente regla significa: (q1, “1”, X) -> (q2, ZX). a. Que la cima de la pila es reemplazada por Z. b. Que la cima de la pila es reemplazada por X. c. Que la cima de la pila es reemplazada por ZX.

23. Dado el siguiente autómata de pila: (q1, “1”, X) -> (q2, ZX) (q2, “0”, Z) -> (q2, vacío). a. Puede reconocer la cadena “1010” y al final la pila queda con ZX. b. Puede reconocer la cadena “1010” y al final la pila queda con X. c. No puede reconocer la cadena “1010” por que la pila queda vacía.

24. Dado el siguiente autómata de pila, al momento de reconocer una cadena el autómata: (q1, “1”, X) -> (q1, ZX) (q2, “0”, Z) -> (q2, vacío) (q3, “#”, X) -> (q3, reconoce). a. No pasa de un estado a otro. b. Pasa por todos los estados. c. Permanece en el estado 2.

25. 1. La siguiente regla significa: (q1, “a”, X) -> (q1, vacio). a. Que reconoce cadenas que contienen la a. b. Que la cima de la pila X se reemplaza por vacio. c. Que la cima está vacia y se reemplaza por X.

26. Dado el siguiente autómata de pila, para que reconozca la cadena “abc#” ¿Qué error debe corregirse? (q1, “a”, X) -> (q2, ZX) (q2, “b”, Z) -> (q2, vacío) (q3, “c”, X) -> (q4, ZX) (q4, “#”, Z) -> (q4, reconoce). a. Regla 3 debe ir desde q3 a q3. b. Regla 2 debe ir desde q2 a q3. c. Regla 4 debe terminar en q3.

27. Para que una gramática quede en forma normal de Chomsky, en la parte derecha debe tener: a. Máximo un terminal. b. Máximo dos terminales. c. Cualquier número de terminales.

28. Para que una gramática sea expresada en forma normal de Chomsky. a. No debe tener más de 3 terminales en el lado derecho de cada regla. b. No debe tener más de un terminal en el lado derecho de cada regla. c. No puede tener más de dos símbolos en el lado izquierdo de cada regla.

29. Para que una gramática quede en forma normal de Chomsky. a. No debe tener más de 3 terminales. b. No debe tener símbolos complementarios. c. No debe tener símbolos inútiles.

30. Para que una gramática quede en forma normal de Chomsky, en la parte derecha debe tener: a. un NO terminal. b. dos NO terminales. c. varios NO terminales.

31. De las siguientes reglas, ¿Cuál no puede ser parte de la gramática por no cumplir los requisitos para estar en forma normal de Chomsky?. a. VAR ->TIPO LISTA. b. TIPO -> int. c. LISTA -> UNAVAR , LISTA.

32. De las siguientes reglas, ¿Cuál cumple los requisitos para estar en forma normal de Chomsky?. a. S ->a. b. S -> aB. c. S -> aBc.

33. De las siguientes reglas, ¿Cuál cumple los requisitos para estar en forma normal de Chomsky?. a. OPERADOR ->>. b. OPERADOR -> id > id. c. OPERADOR -> id == id.

34. La siguiente gramática tiene un error en una de las reglas, este error no le permite estar en forma normal de Chomsky. S -> BC B -> a C -> C ¿En que regla está el error?. a. Regla 1. b. Regla 2. c. Regla 3.

35. Dada la Gramática E -> E + T Al convertirla en forma normal de Chomsky, ¿Cuál sería el resultado?. a. E -> E + E -> + T E -> T. b. E -> E X X -> + T. c. E -> E X X -> Y T Y -> +.

36. Dada la Gramática BLOQUE -> UNASENTENCIA BLOQUE BLOQUE -> UNASENTENCIA UNASENTENCIA -> id++ Al convertirla en forma normal de Chomsky, ¿Cuál sería el resultado?. a. BLOQUE -> UNASENTENCIA BLOQUE BLOQUE -> UNASENTENCIA UNASENTENCIA -> id++. b. BLOQUE -> UNASENTENCIA BLOQUE UNASENTENCIA -> id++. c. BLOQUE -> UNASENTENCIA BLOQUE BLOQUE -> UNASENTENCIA.

37. Dada la Gramática S -> ABC Al convertirla en forma normal de Chomsky, ¿Cuál sería el resultado?. a. S -> AB B ->BC. b. S -> A S -> B B ->BC. c. S -> aA A ->BC.

38. Dada la siguiente gramática: S -> AB A -> aAA A -> vacío B -> bBB Para que la gramática quede en forma normal de Chomsky es necesario eliminar las producciones vacías, en este caso, ¿Qué regla hay que eliminar?. a. Regla 2. b. Regla 3. c. Regla 4.

39. En la siguiente gramática: VAR -> TIPO LISTA ; TIPO -> int UNAVAR -> vacio LISTA -> UNAVAR, LISTA MASVAR -> id, LISTA Si se desea eliminar las producciones vacías, ¿Qué regla hay que eliminar?. a. Regla 2. b. Regla 3. c. Regla 4.

40. En la siguiente gramática: S -> AbC A -> a C -> D D -> b ¿en que regla se encuentra un símbolo inútil?. a. Regla 2. b. Regla 3. c. Regla 4.