AUTÓMATAS Y LENGUAJES FORMALES: Act 8: Lección Evaluativa Unidad 2

TODAS CORRECTAS

1.

 El lenguaje que reconoce un autómata a pila pertenece al grupo (IDENTIFIQUELO EN EL SIGUIENTE DIBUJO ) en la clasificación de la Jerarquía de Chomsky. 

 Seleccione una respuesta. 

 a. G2 Correcto corresponde a lenguaje libre de contexto

 b. G0

 c. G1

 d. G3

2.

La Máquina de Turing, y un autómata fintio, tienen similitudes como: 

Seleccione al menos una respuesta. 

 a. Un control finito Correcto

 b. Una cabeza lectora Correcto

 c. Un alfabeto para la cinta y un alfabeto de entrada

 d. Un cabezal de lectura y otro para escritura

3.

 Respecto a la relación entre un AF y un AP cuál afirmación es cierta: 

Seleccione una respuesta. 

 a. Todo lenguaje aceptado por un AF es también aceptado por un AP Correcto

 b. Un AP es infifnito por su capacidad de memoria. Un AF es finito por su número de estados.

 c. Estas dos máquinas no permiten regularidades.

 d. Los AF y los AP tienen la misma capacidad de memoria

4.

 Cuál es el objetivo de aplicar una gramática: 

Seleccione al menos una respuesta.

 a. Representar linealmente (no gráficamente) el comportamiento de una Autómata Finito (ya sea AFN ó AFND)

 b. Generar Lenguajes aceptables por una AP o una MT

 c. La gramática permite formar correctamente las frases o generar palabras de un Lenguaje. Correcto

 d. Es que se parte de una variable, llamada siımbolo inicial, y se aplican repetidamente las reglas gramaticales, hasta que ya no haya variables en la palabra. Correcto

5.

 En un autómata de pila (AP), la función d etransición aplica o interviene a:

Seleccione al menos una respuesta. 

 a. A cada estado Correcto

 b. A cada símbolo topo de la pila  Correcto

 c. A cda movimiento de la pila  Correcto

 d. A cada símbolo de entrada (Incluyendo la cadena vacía)  Correcto

6.

 Cuando se trabajan Autómatas de Pila (AP) ó (PD) es válido afirmar: 

Seleccione al menos una respuesta. 

 a. La pila tiene un alfabeto propio y debe coincidir con el alfabeto de la palabra de entrada.

 b. Los autómatas de pilas no tienen metodología tan generalmente aplicable, solo se debe tener una estrategia clara para el manejo de la pila. Correcto

 c. En los AP las transiciones de un estado a otro indican los caracteres que se consumen de la enytrada, pero no lo que se saca del topo de la pila.

 d. Cuando desarrollamos un autómata de pilas tenemos que repetir lo que quiere ser recordado entre los estados y las pilas. Correcto

7.

Sea G la siguiente gramática de símbolos terminales {a, b}: S → aAA, A → bS, A → λ Se puede afirmar que: 

Seleccione una respuesta. 

 a. El autómata más sencillo que acepta L(G) es un autómata de pila no determinista

 b. El autómata más sencillo que acepta L(G) es un autómata de pila determinista

 c. El autómata más sencillo que acepta L(G) es un autómata finito Correcto

 d. Los únicos autómatas que aceptan L(G) son las máquinas de Turing

8.

 Cuando las gramáticas son demasiado extensas y generan árboles de derivación grandes, se suele usar: 

Seleccione una respuesta. 

 a. Producciones de tipo GIC con un solo nodo terminal

 b. Formas de Greibach

 c. Formas de LIC

 d. Formas canónicas que restrinja los tipos de producciones que pueden utilizarse. Correcto

9.

 Se propone la siguiente GLC (Gramática Libre de Contexto) para que genere el lenguaje de los palíndromos en el alfabeto ∑ = {a,b} G = S → aSa | bSb | a | b | 

 Dada esa gramática, determine cuáles reglas corresponden a los palíndromos generados. 

 Seleccione al menos una respuesta. 

 a. S → a | S → b (Palíndromos con símbolos impares) Correcto

 b. S → b (Palíndromos con símbolos pares)

 c. S → lambda ( Palíndromos con símbolos pares ) Correcto

 d. S → a (Palíndromos con símbolos pares)

10.

 Marque la notación más frecuentemente utilizada para expresar gramáticas libres de contexto. 

Seleccione una respuesta. 

 a. Formas Normales de Greibach

 b. Arboles de Derivación

 c. Backus-Naur Correcto

 d. Formas Normales de Chomsky