AUTOMATAS 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. 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
	d. 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.

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.

Incorrecto

Puntos para este envío: 0/1.

Question2

Puntos: 1

Para que una palabra de entrada sea aceptada en un AP se deben cumplir las condiciones siguientes:

Seleccione al menos una respuesta.

	a. La palabra de entrada se debe haber agotado (consumido totalmente).
	b. La pila debe tener lambda como elemento final.
	c. El AP se debe encontrar en un estado final.
	d. La pila debe estar vacía.

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 qué recuerda cada cual.

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 → a (Palíndromos con símbolos pares)
	b. S → lambda ( Palíndromos con símbolos pares )
	c. S → b (Palíndromos con símbolos pares)
	d. S → a | S → b (Palíndromos con símbolos impares)

Al realizar el árbol de derivación y el desarrollo de la gramática, las reglas que llevan a crear palíndromos impares son: S → a produce la cadena ω = baaab (impar) y S → b produce la cadena ω = babab (impar) y S → alanda produce la cadena ω = baab (par).

Correcto

Puntos para este envío: 1/1.

Question4

Puntos: 1

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

Seleccione una respuesta.

	a. 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.
	b. Al igual que los AF, los AP tienen estados finales, que permiten distinguir cuando una palabra de entrada es aceptada
	c. Una de las condiciones para que una palabra de entrada sea aceptada en un AP la pila debe estar vacía.
	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.

Question5

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 símbolo topo de la pila
	b. A cada estado
	c. A cada movimiento de la pila
	d. A cada símbolo de entrada (Incluyendo la cadena vacía)

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.

Question6

Puntos: 1

Identifique los aspectos que se deben tener para garantizar el determinismo en un Autómata de pila finito determinista (AFPD).

Tenga en cuenta además de los componentes (tupla) de la pila que::

f: es la función de transición:

e: es una transición dada espontanea.

Seleccione al menos una respuesta.

	a. El determinismo se da cuando no hay alternativas de movimiento para el mismo estado, usando la misma entrada y el mismo símbolo de pila.
	b. La definición de la función de transición (f) requiere que haya por lo menos un símbolo en la pila. No se permiten operaciones con la pila vacía.
	c. Las transiciones lambda en un AFPD permiten que el autómata cambie el contenido de la pila, sin procesar (o consumir) símbolos sobre la cinta de entrada.
	d. Las operaciones: f(q,a,s)y f(q,e,s) con a ∑ ,, q Q y s (pertenecen) al alfabeto de la pila y no pueden estar simultáneamente definidos o declarados.

Parcialmente correcto

Puntos para este envío: 0.8/1.

Question7

Puntos: 1

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

Seleccione una respuesta.

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

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.

Question8

Puntos: 1

Dado un alfabeto ∑, los símbolos Ø, lambda, y los operadores + (unión), ∙ (concatenación) y * (clausura), se define una EXPRESION REGULAR (ER) sobre el alfabeto ∑ en la que son válidas las siguientes relaciones:

Nota. ω es una cadena sobre un lenguaje L

Seleccione al menos una respuesta.

	a. Si ω = a y a pertenece ∑ entonces L (ω) no pertenece ∑
	b. Si ω = lambda entonces L (lambda) = { lambda}
	c. Si ω = Ø entonces L (ω) = Ø
	d. Si ω* es una ER entonces L (ω*) no es una ER

La notación de conjuntos nos permite describir los lenguajes regulares, pero nosotros quisiéramos una notación en que las representaciones de los lenguajes fueran simplemente texto (cadenas de caracteres). Así las representaciones de los lenguajes regulares serían simplemente palabras de un lenguaje (el de las representaciones correctamente formadas).

Correcto

Puntos para este envío: 1/1.

Question9

Puntos: 1

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

Seleccione una respuesta.

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

Incorrecto

Puntos para este envío: 0/1.

Question10

Puntos: 1

Para eL siguiente árbol de derivación identifique las operaciones correctas sobre el mismo:

Seleccione al menos una respuesta.

	a. La gramática que lo genera es: S --> SbS | ScS | a
	b. La gramática que lo genera es: S -->SaS | SbS | Sc | a
	c. La derivación de la cadena {abaca} es: S --> SbS --> SbScS ---> SbSca ---> Sbaca ---> abaca
	d. La derivación de la cadena {abaca} es: S ---> ScS ---> SbScS ---> abScS ---> abacS ---> abaca

Parcialmente correcto

Puntos para este envío: 0.5/1.

1

Puntos: 1

Dada la gramática S → aS; S→ aSbS; S→ λ. Indique cuál de las siguientes afirmaciones es falsa:

Seleccione una respuesta.

	a. Cualquier cadena generada por la gramática contiene una subcadena no vacía donde el número de letras a es igual al número de letras b
	b. La cadena {b} es rechazada
	c. El lenguaje generado por la gramática es estructurado por frases
	d. Para cualquier prefijo de una cadena generada por la gramática se verifica que el número de letras a es mayor o igual al número de letras b. Prefijo de una cadena w es toda cadena no vacía x para la que existe una cadena u tal que w = xu

Incorrecto

Puntos para este envío: 0/1.

Question2

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 no determinista (en sentido estricto)
	b. Regular
	c. Estructurado por frases (en sentido estricto).
	d. Independiente del contexto determinista (en sentido estricto)

Correcto

Puntos para este envío: 1/1.

Question3

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 | 1S1 | 2
	b. S –> 0A0 | 1S2 | 10
	c. S –> 0A0 | 1S2 | 1 | 0
	d. S –> 0A0 | 1S0 | 2 | 0

Incorrecto

Puntos para este envío: 0/1.

Question4

Puntos: 1

Indique cuál de las siguientes afirmaciones es verdadera

Seleccione una respuesta.

	a. Los autómatas finitos tienen un número finito de estados
	b. Los autómatas de pila reconocen lenguajes generados por gramáticas de tipo 3
	c. Los autómatas finitos sólo pueden aceptar lenguajes finitos
	d. Las máquinas de Turing y los autómatas de pila son autómatas finitos

Incorrecto

Puntos para este envío: 0/1.

Question5

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 LIC contiene al conjunto de los lenguajes regulares.
	d. El conjunto de los lenguajes regulares contiene al conjunto de las GIC.

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)

Incorrecto

Puntos para este envío: 0/1.

Question6

Puntos: 1

Cual de las siguientes afirmaciones es VERDADERA

Seleccione una respuesta.

	a. En un árbol de derivación cada nodo solamente puede tener otro hijo nodo. De lo contrario se formaría otro nodo.
	b. En los arboles de derivación, los nodos raíces siempre derivan en dos ramas.
	c. Los lenguajes generados por una Gramática Independiente del Contexto son llamados Lenguajes Regulares
	d. 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.

Es posible probar que cualquier palabra que sea aceptada por el AFD M, puede ser generada por la gramática regular G. Esto significa que L(G) = L(M).

Incorrecto

Puntos para este envío: 0/1.

Question7

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. El número de letras a es igual al de letras b en w
	b. 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.
	c. w = xc | x ∈ (a∪ b)*
	d. Las cadenas {abc, c} son aceptadas

Incorrecto

Puntos para este envío: 0/1.

Question8

Puntos: 1

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

Seleccione una respuesta.

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

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

Incorrecto

Puntos para este envío: 0/1.

Question9

Puntos: 1

Indique cuál de los siguientes lenguajes genera esta gramática:

S ---> X

X --> Y

X --> xXy

Y ---> xxYx

X ---> lambda

Y ---> lambda

Seleccione una respuesta.

	a. el lenguaje x (potencia m) y (potencia n) tal que n ≤ m < 2n;
	b. el lenguaje x (potencia m) y (potencia n) tal que n ≤ m ≤ 2n;
	c. el lenguaje x (potencia m) y (potencia n) tal que 2m = 3n;
	d. el lenguaje x (potencia m) y (potencia n) tal que n < m ≤ 2n

Incorrecto

Puntos para este envío: 0/1.

Question10

Puntos: 1

La concatenación de dos lenguajes del alfabeto Σ es un subconjunto de:

Seleccione una respuesta.

	a. Σ∗×Σ∗
	b. Σ∪Σ
	c. (Σ*)*
	d. Σ×Σ

La concatenación de dos lenguajes es el lenguaje que resulta al concatenar las respectivas cadenas (la concatenación de dos cadenas es una nueva cadena) y por tanto pertenece a Σ*. Σ∪Σ=Σ ; Σ×Σ es el conjunto de pares ordenados formados por dos símbolos de Σ, y Σ*×Σ* es el conjunto de pares ordenados formados por dos cadenas de Σ*.

Incorrecto

Puntos para este envío: 0/1.

Question11

Puntos: 1

Si una gramática independiente del contexto tiene todas sus reglas de la forma: A → wB, o bien de la forma A → w, donde w es una cadena de uno o más terminales, y A y Bson símbolos no terminales, entonces el lenguaje generado por dicha gramática es:

Seleccione una respuesta.

	a. Estructurado por frases y no independiente del contexto
	b. Independiente del contexto no regular
	c. Regular
	d. Decidible

Correcto

Puntos para este envío: 1/1.

Question12

Puntos: 1

Desarrolle la siguiente gramática cuyos símbolos terminales son {a,b}

S ---> aAA, A ---> bS, A ---> lambda

Identifique las apreciaciones válidas. Se recomienda desarrollar el árbol de derivación

Seleccione al menos una respuesta.

	a. La cadena más sencilla que genera el L(G) es: {aba}
	b. El lenguaje que genera la gramática es L(G) = a(ba)*
	c. El autómata más sencillo que Acepta L(G) es un autómata de pila (AP). Una cadena válida sería {abab}
	d. El autómata más sencillo que Acepta L(G) es un autómata finito

Correcto

Puntos para este envío: 1/1.

Question13

Puntos: 1

Dado el lenguaje L = {a, abb, ba, bbba, b} indique cuántas cadenas de longitud estrictamente menor que 3 hay en L*:

Seleccione una respuesta.

	a. 6
	b. 5
	c. 4
	d. 7

Correcto

Puntos para este envío: 1/1.

Question14

Puntos: 1

Considere la gramática: S→ 0S, S→ 1S, S→ S0, S→ λ. Indique cuáles de las

siguientes afirmaciones son verdaderas

Seleccione al menos una respuesta.

	a. La gramática es equivalente a S→0S, S→ 1S, S→ λ
	b. Las cadenas {0101, 1001] no son parte del lenguaje que genera
	c. Existen derivaciones distintas que generan cadenas idénticas
	d. La regla S→ S0 es innecesaria

Correcto

Puntos para este envío: 1/1.

Question15

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 –> 001 A –> 0010
	b. S –> 0A –> 01S –> 010 A –> 0100
	c. S –> 0A –> 00A –> 001S –> 0010 A –> 00100
	d. S –> 0A –> 0A –> 00A –> 000

Correcto

Puntos para este envío: 1/1.