AUTOMATAS UNIDAD 2 RESPUESTAS

1

Puntos: 1

Del diseño y naturaleza de los autómatas de pila (PDA), es válido afirmar:

Seleccione una respuesta.

	a. Un Autómata de Pila al igual que una Máquina de Turing o un Autómata Finito, su definición básica es de naturaleza no determinista
	b. Para poder simular un autómata de Pila se debe tener en cuenta: Las columnas de una traza de ejecución para un AP son: el estado en que se encuentra el autómata, lo que ha leido hasta el momento o estado actual al inicio de la simulación, y el contenido de la memoria al final del recorrido.
	c. Un autómata de pila no puede hacer las funciones de "contador" ya que sus recorridos varían en la cinta y lo que le importa a esta automatización es el estado final y la salida del dato.
	d. A la hora de diseñar un AP tenemos que repartir lo que requiere ser “recordado” entre los estados y la pila. Distintos diseños para un mismo problema pueden tomar decisiones diferentes en cuanto a que recuerda cada cual

A la hora de diseñar un AP tenemos que repartir lo que requiere ser “recordado” entre los estados y la pila. Distintos diseños para un mismo problema pueden tomar decisiones diferentes en cuanto a que recuerda cada cual.

Correcto

Puntos para este envío: 1/1.

Question2

Puntos: 1

Los errores más comunes al diseñar gramáticas (GLC) son:

Seleccione al menos una respuesta.

	a. Combinar gramáticas
	b. Que “sobren palabras”
	c. Que “falten palabras”,
	d. Reutilizar gramáticas y modificarlas para ajustarlas al lenguaje generado

El problema del diseño de GLC consiste en proponer, dado un lenguaje L, una GLC G tal que su lenguaje generado es exactamente L.

Parcialmente correcto

Puntos para este envío: 0.5/1.

Question3

Puntos: 1

Dado el siguiente autómata finito (AF), reconoce el lenguaje generado por la gramática:

Seleccione una respuesta.

	a. G= {S -->0B | 0A , A ---> 1B | lambda , B ---> lambda
	b. G={S ---> 0A| lambda,, A ---> 0A | 1B, B ---> 1B|lambda}
	c. G = { S --->A |lambda , A ---> 0B | lambda,, B ---> lambda}
	d. G = { S --->B |lambda , A ---> 1B | lambda,, B ---> lambda}

Correcto

Puntos para este envío: 1/1.

Question4

Puntos: 1

Sea un autómata (finito o de pila) M y una cadena x ∈ L(M). Si el autómata lee la cadena x, ¿llegará necesariamente a un estado de aceptación?

Seleccione una respuesta.

	a. Si, si M es un autómata finito.
	b. Nunca, Queda en un bucle ya que solo recorre un símbolo.
	c. No todas las veces, dado que puede tratarse de un autómata no determinista.
	d. Sí, siempre.

Correcto

Puntos para este envío: 1/1.

Question5

Puntos: 1

Dada la siguiente gramática regular G , identifique el conjunto de cadenas o palabras válidas que puede generar el Autómata Finito que lo representa: (Para el desarrollo del ejercicio se sugiere graficar o recrear el autómata)

S → aA | bA

A → aB | bB | a

B → aA | bA

Seleccione una respuesta.

	a. El conjunto de cadenas que pueda generar la ER = a*b*a
	b. {aa, aaaa, bbba, ba, bba, baaa, baba}
	c. {a,b}
	d. {baaaa, aaaaa, bba}

Correcto

Puntos para este envío: 1/1.

Question6

Puntos: 1

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

Seleccione una respuesta.

	a. Formas de LIC
	b. Producciones de tipo GIC con un solo nodo terminal
	c. Formas canónicas que restrinjan los tipos de producciones que pueden utilizarse.
	d. Formas de Greibach

La definición de una gramática independiente del contexto es demasiado amplia, y por lo tanto, es deseable establecer una forma canónica que restrinja los tipos de producciones que pueden utilizarse.

Correcto

Puntos para este envío: 1/1.

Question7

Puntos: 1

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

Seleccione al menos una respuesta.

	a. A cada estado
	b. A cada símbolo de entrada (Incluyendo la cadena vacía)
	c. A cada movimiento de la pila
	d. A cada símbolo topo de la pila

La función de transición aplica cada estado, cada símbolo de entrada (incluyendo la cadena vacía) y cada símbolo tope de la pila en un conjunto de posibles movimientos. Cada movimiento parte de un estado, un símbolo de la cinta de entrada y un símbolo tope de la pila. El movimiento en sí consiste en un cambio de estado, en la lectura del símbolo de entrada y en la substitución del símbolo tope de la pila por una cadena de símbolos.

Correcto

Puntos para este envío: 1/1.

Question8

Puntos: 1

Si ∑ es un alfabeto, se le llama ∑n al conjunto de todas las palabras de longitud n sobre ∑.

Identifique las notaciones de conjuntos válidas para la creación de palabras sobre el alfabeto ∑

Seleccione al menos una respuesta.

	a. ∑ * = Conjunto de todas las cadenas de cualquier longitud sobre ∑
	b. ∑0 = {lambda} Conjunto cuyo único elemento es la palabra vacía.
	c. ∑0 = Conjunto de todas las cadenas sobre el alfabeto ∑ excepto la vacía.
	d. ∑+ = Conjunto de todas las cadenas positivas excepto la vacía

La longitud de una cadena ω que se denota como |ω| es el número de letras que aparecen en ω. A la cadena que no tiene símbolos o que es lo mismo decir que tiene longitud cero, se le llama palabra vacía. Si ∑ es un alfabeto, se le llama ∑ n al conjunto de todas las palabras de longitud n sobre ∑. La estrella * genera el conjunto de todas las cadena de cualquier longitud sobre ∑. Si se analiza ∑ + esta representa al conjunto de todas las cadenas sobre el alfabeto ∑ excepto la vacía.

Correcto

Puntos para este envío: 1/1.

Question9

Puntos: 1

Acerca del funcionamiento de un Autómata de Pila, cuál de las siguientes operaciones o comportamientosNO las hace este autómata.

Seleccione una respuesta.

	a. Una de las condiciones para que una palabra de entrada sea aceptada en un AP la pila debe estar vacía.
	b. En la Pila una transición de un estado a otro Arroja la información de lo que sale de la pila (tope), no de lo que entra ya que el avance es progresivo hacia adelante y no hacia atrás.
	c. Al igual que los AF, los AP tienen estados finales, que permiten distinguir cuando una palabra de entrada es aceptada
	d. La pila no tiene límite en sus extremos. A diferencia de las MT que son cerradas por la izquierda.

Para verificar el funcionamiento del autómata, podemos simular su ejecución, listando las situaciones sucesivas en que se encuentra, mediante una tabla que llamaremos “traza de ejecución”. Las columnas de una traza de ejecución para un AP son: el estado en que se encuentra el autómata, lo que falta por leer de la palabra de entrada, y el contenido de la pila

Correcto

Puntos para este envío: 1/1.

Question10

Puntos: 1

Indique cuál de las siguientes afirmaciones es verdadera:

Seleccione al menos una respuesta.

	a. Con un autómata de pila no puede reconocerse un lenguaje regular
	b. Para reconocer un lenguaje regular mediante un autómata de pila no es necesario que el alfabeto de la pila contenga ningún símbolo
	c. Para reconocer un lenguaje regular mediante un autómata de pila el alfabeto de la pila debe contener al menos un símbolo
	d. Cuando se dice que un AFPD (autómata de pila determinista) es más sencillo , se refiere a que es menos potente y no se refiere ala sencillez de su diseño.

Parcialmente correcto

Puntos para este envío: 0.5/1.

1

Puntos: 1

Indique cuál de las siguientes afirmaciones es falsa:

Seleccione una respuesta.

	a. La intersección de dos lenguajes estructurados por frases es un lenguaje estructurado por frases
	b. La unión de un número finito de lenguajes estructurados por frases es un lenguaje estructurado por frases
	c. Todo lenguaje cuyo complementario sea un lenguaje finito es independiente del contexto
	d. La intersección de un lenguaje regular con un lenguaje independiente del contexto es siempre un lenguaje regular.

Correcto

Puntos para este envío: 1/1.

Question2

Puntos: 1

En la descripción de las gramáticas, las producciones unitarias tienen la forma:

Seleccione una respuesta.

	a. A --> B
	b. A -->sB
	c. S-->a
	d. S-->ABs

Las producciones unitarias son las que tienen la forma A → B

Correcto

Puntos para este envío: 1/1.

Question3

Puntos: 1

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 | lambda

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

Seleccione al menos una respuesta.

	a. S → b (Palíndromos con símbolos pares)
	b. S → a (Palíndromos con símbolos pares)
	c. S → lambda ( Palíndromos con símbolos pares )
	d. S → a | S → b (Palíndromos con símbolos impares)

Correcto

Puntos para este envío: 1/1.

Question4

Puntos: 1

Que apreciaciones son ciertas con referencia a lo que describe el siguiente árbol de derivación:

Seleccione al menos una respuesta.

	a. Acepta el lenguaje de las palabras que empiezan por “a”, terinan por “c” y además en medio de estas dos letras pueden haber una “b” o muchas “b”s
	b. La ER que representa el lenguaje que acepta ese árbol de derivación es ab*c
	c. Acepta el lenguaje de las palabras que empiezan por S y terminan en una o muchas A”s. La ER que lo representa es SA*
	d. Este árbol de derivación es producto de la gramática lineal por la derecha: S –>aA | A ---> bA | c

Correcto

Puntos para este envío: 1/1.

Question5

Puntos: 1

Considere la gramática S →Rc, R → aRbR, R → λ. Siendo w una cadena cualquiera generada por dicha gramática, indique cuál de las siguientes afirmaciones es falsa:

Seleccione una respuesta.

	a. w = xc | x ∈ (a∪ b)*
	b. El número de letras a es igual al de letras b en w
	c. El número de letras a es mayor o igual al de letras b en todo prefijo de w. Prefijo de una cadena w es toda cadena no vacía x para la que existe una cadena u tal que w = xu.
	d. Las cadenas {abc, c} son aceptadas

Correcto

Puntos para este envío: 1/1.

Question6

Puntos: 1

Una gramática independiente del contexto (GIC) genera un lenguaje independiente del contexto (LIC), lo que indica que hay LIC que no son lenguajes regulares y por lo tanto:

Seleccione una respuesta.

	a. El conjunto de los lenguajes regulares contiene al conjunto de los LIC.
	b. El conjunto de los lenguajes regulares y el conjunto de los LIC son conjuntos independientes.
	c. El conjunto de los lenguajes regulares contiene al conjunto de las GIC.
	d. El conjunto de los LIC contiene al conjunto de los lenguajes regulares.

Una gramática independiente del contexto (GIC) es una cuádrupla G=(N, Σ, S, P), donde: N: es una colección finita (no vacía) de símbolos no terminales. Σ: es un alfabeto. S: es un no terminal llamado símbolo inicial. P: un conjunto de producciones tal que P⊆ N (N∪ Σ)*. Los lenguajes generados por una GIC son llamados Lenguajes Independientes del Contexto (LIC)

Correcto

Puntos para este envío: 1/1.

Question7

Puntos: 1

Que significan las reglas de la forma A → lambda

Seleccione al menos una respuesta.

	a. Generan lenguajes que contienen la palabra vacía
	b. Que estén en una gramática, deben permitir que el lenguaje no se cambie o altere
	c. No se pueden eliminar en una gramática ya que si se hiciere, modifican el lenguaje
	d. Se le llaman producciones nulas

Incorrecto

Puntos para este envío: 0/1.

Question8

Puntos: 1

La relación entre un AP y un LLC (Lenguaje Libre de contexto) permite que dada una Gramática G, existe entonces un AP que acepta exactamente el lenguaje generado por G.

Dado el siguiente autómata de pila (AP) cuyo funcionamiento se representa en la siguiente tabla, identifique la gramática correcta y sus reglas que aceptan el LLC dado por el AP.

Seleccione una respuesta.

	a. S –> 0A0 | 1S0 | 2 | 0
	b. S –> 0A0 | 1S1 | 2
	c. S –> 0A0 | 1S2 | 1 | 0
	d. S –> 0A0 | 1S2 | 10

Incorrecto

Puntos para este envío: 0/1.

Question9

Puntos: 1

Cual de las siguientes afirmaciones se asocia correctamente al diseño y funcionamiento de los árboles de derivación.

Seleccione una respuesta.

	a. Los lenguajes generados por una Gramática Independiente del Contexto son llamados Lenguajes Regulares
	b. En un árbol de derivación, una gramática es ambigua cuando hay dos o más árboles de derivación distintos para una misma cadena.
	c. En un árbol de derivación cada nodo solamente puede tener otro hijo nodo
	d. En los árboles de derivación, no es necesario usar nodo raíz

Al derivar una cadena a través de una GIC, el símbolo inicial se sustituye por alguna cadena. Los no terminales se van sustituyendo uno tras otro por otras cadenas hasta que ya no quedan símbolos no terminales, queda una cadena con sólo símbolos terminales. A veces es útil realizar un gráfico de la derivación. Tales gráficos tienen forma de árbol y se llaman “árbol de derivación” o “árbol de análisis”. Para una derivación dada, el símbolo inicial “S” etiqueta la raíz del árbol. El nodo raíz tiene unos nodos hijos para cada símbolo que aparezca en el lado derecho de la producción, usados para reemplazar el símbolo inicial. De igual forma, cada símbolo no terminal tiene unos nodos hijos etiquetados con símbolos del lado derecho de la producción usada para sustituir ese no terminal.

Correcto

Puntos para este envío: 1/1.

Question10

Puntos: 1

Dada la siguiente gramática con las siguientes producciones: Determine que opciones son verdaderas y aplican al diseño y análisis de la misma.

Seleccione al menos una respuesta.

	a. Es una gramática independiente de contexto
	b. La gramática debe aplicar las reglas 2n veces para que genere el lenguaje L = {x (potencia m) y (potencia n) | 0 <= n <= m }
	c. Genera le lenguaje : L = {x (potencia m) y (potencia n) | 0 <= n <= m <= 3n }
	d. Reconoce las cadenas {xx, yy}

Correcto

Puntos para este envío: 1/1.

Question11

Puntos: 1

El lenguaje x (potencia m) y (potencia n) z (potencia p), donde m, n y p son enteros no negativos tales que m+n=p, es:

Seleccione una respuesta.

	a. Independiente del contexto determinista (en sentido estricto)
	b. Independiente del contexto no determinista (en sentido estricto)
	c. Regular
	d. Estructurado por frases (en sentido estricto).

Correcto

Puntos para este envío: 1/1.

Question12

Puntos: 1

Dado un alfabeto, el número máximo de estados de un autómata finito determinista:

Seleccione una respuesta.

	a. Puede ser infinito
	b. No hay número máximo
	c. Depende del alfabeto sobre el que está definido
	d. Es directamente proporcional al número de cadenas del lenguaje que reconoce

Correcto

Puntos para este envío: 1/1.

Question13

Puntos: 1

La combinación de autómatas se demostró en los Autómatas Finitos de la Unidad 1 en as que era viable combinar dos Autómatas que generaban el miso lenguaje y obtener otro que genera las mismas cadenas que los autómatas combinados.
Con referencia a los Autómatas de Pila (AP), este tema de combinación tiene aspectos a analizar. identifique cuál es válido para estas operaciones:

Seleccione una respuesta.

	a. Las operaciones de combinar AP solo es viable cuando los dos Autónomas leen el mismo alfabeto.
	b. Un AP se puede combinar con una MT siempre y cuando lean y acepten el mismo lenguaje.
	c. Solo la operación de Unión de los lenguajes de dos AP es permitida.
	d. Se pueden obtener AP que acepten operaciones de Unión y Concatenación de los lenguajes aceptados por los Autónomas de Pila dados.

En los AP también es posible aplicar métodos de combinación modular de autómatas, como se hizo con los autómatas finitos. En particular, es posible obtener AP que acepten la unión y concatenación de los lenguajes aceptados por dos AP dados.

Incorrecto

Puntos para este envío: 0/1.

Question14

Puntos: 1

Dada la siguiente gramática G= (VN= {S, A}, VT= {0,1}, S, P) donde P son las producciones:

Seleccione al menos una respuesta.

	a. S –> 0A –> 00A –> 001S –> 0010 A –> 00100
	b. S –> 0A –> 01S –> 010 A –> 0100
	c. S –> 0A –> 00A –> 001 A –> 0010
	d. S –> 0A –> 0A –> 00A –> 000

Correcto

Puntos para este envío: 1/1.

Question15

Puntos: 1

Dado el alfabeto Σ={x, y, z}, indique cuál de las siguientes afirmaciones es verdadera:

Seleccione una respuesta.

	a. La expresión regular y*(xy*x)*y* representa el lenguaje formado por todas las cadenas que contienen un número par de x’s
	b. La gramática S→ SS, S→ xy, S→ yx genera el lenguaje formado por las cadenas que contienen tantas x’s como y’s;
	c. El lenguaje formado por las cadenas que contienen la secuencia xyxz es regular
	d. El lenguaje x (potencia n) y (potencia n) z (potencia n) no es decidible

Correcto

Puntos para este envío: 1/1.