AUTOMATAS Y LENGUAJES FORMALES ACT5

1

Puntos: 1

Dado el siguiente autómata Finito, es válido afirmar:

Seleccione al menos una respuesta.

	a. La Er que lo representa es: (ab*a)*
	b. La ER que lo representa es: (b+ab*a)*
	c. La ER que lo representa: (b+ab*a)*ab*	Correcto
	d. La ER que lo representa es: (b*ab*a)*b*ab*	Correcto

Correcto

Puntos para este envío: 1/1.

Question2

Puntos: 1

Dado el siguiente autómata: Cambie los símbolos del alfabeto asociando a = 0 y b =1 . Para las siguientes opciones,(que están en base 10 o decimal), conviértalas a base 2 (binario) y recorra el autómata e identifique cuál número acepta el autómata.

Seleccione una respuesta.

	a. 73
	b. 205
	c. 253
	d. 182	Correcto: equivale a recorrer la cadena 10110110 (cadenas que terminen en cero “0” o en la asociación del autómata que terminen en “a”)

Correcto

Puntos para este envío: 1/1.

Question3

Puntos: 1

Para el siguiente autómata, identifique cuál es la Expresión Regular (ER) que mejor lo representa:

Seleccione una respuesta.

	a. (ab+ba) + a
	b. ab +(ab)*
	c. a +(ab)*
	d. (ab + aba)*	Correcto: Aceptará cadenas que empiecen por una a seguida de una b incluyendo la cadena vacía.

Correcto

Puntos para este envío: 1/1.

Question4

Puntos: 1

Dados los siguientes autómatas determine que características aplican en cuanto a su comportamiento y diseño.

Seleccione al menos una respuesta.

	a. El autómata A NO es “equivalente” al autómata B.	Incorrecto
	b. La cadena bababbaabb la reconocen los dos autómatas.	Correcto: esta cadena es aceptada por ambos autómatas. Además amas máquinas son equivalentes
	c. El autómata A es “equivalente” al autómata B
	d. El autómata A es un AFND y reconoce el mismo lenguaje que el autómata B

Parcialmente correcto

Puntos para este envío: 0.3/1.

Question5

Puntos: 1

Este lenguaje:

L (G) = {a (potencia n) b (potencia n) / n>=1}

Es generado por la gramática:

Seleccione una respuesta.

	a. S ---> ab| Sab
	b. S ---> Sa| Sb
	c. S ---> aSb | ab	Correcto
	d. S ---> Sab | aSb

Correcto

Puntos para este envío: 1/1.

Question6

Puntos: 1

Cual expresión regular (ER) representa el lenguaje que contiene una subcadena 11

Seleccione una respuesta.

	a. 10*0+1(0,1)*
	b. (1,0)*+(0,1)*01
	c. ((0+1))*,1,1 . ((0+1))*	Correcto: esta ER acepta la subcadena 11
	d. (((01)*+(01)*0)+((10)*+(10)*1))

Correcto

Puntos para este envío: 1/1.

Question7

Puntos: 1

Dentro de la jerarquía y clasificación de los lenguajes (Chomsky) identifique que asociaciones están erradas.

Seleccione al menos una respuesta.

	a. Una gramática regular o de tipo 3, puede generar Autómatas finitos (AF)
	b. Los lenguajes regulares pueden ser pueden ser descritos mediante expresiones regulares (ER)	Esta afirmación es verdadera. Un lenguaje puede ser descrito mediante una expresión regular (expresar de forma compacta cómo son todas las cadenas de símbolos que le pertenecen).
	c. Los lenguajes libres de contexto o de tipo 2, pueden ser generados por los autómatas de pila (AP)
	d. Los lenguajes que no poseen restricciones o de tipo 0, son reconocidos mediante Autómatas Finitos No Deterministas (AFND)	Correcto: esta afirmación está errada. Los lenguajes que no poseen restricciones o de tipo 0, son reconocidos mediante Máquinas de Turing (MT)

Parcialmente correcto

Puntos para este envío: 0.3/1.

Question8

Puntos: 1

Analice el siguiente diagrama de Moore e identifique las apreciaciones válidas:

Seleccione al menos una respuesta.

	a. Es un AF.	Correcto
	b. No tiene alfabeto definido
	c. No es un autómata válido en diseño
	d. Es una aplicación de los autómatas. Un interruptor de luz	Correcto

Correcto

Puntos para este envío: 1/1.

Question9

Puntos: 1

Dado los siguientes dos autómatas: determine cuáles afirmaciones son válida

Seleccione al menos una respuesta.

	a. El autómata B es un AFND (además posee dos estados de aceptación) y su ER es la misma que la del autómata A.
	b. El autómata A es un AFD pero no reconoce el mismo lenguaje que el autómata B	Correcto: Ambos autómatas son AFD y o reconocen el mismo lenguaje
	c. Ambos son AFD y reconocen el mismo lenguaje
	d. El autómata B es un AFD pero no reconoce el mismo lenguaje que el autómata A	Correcto: Ambos autómatas son AFD y o reconocen el mismo lenguaje.

Correcto

Puntos para este envío: 1/1.

Question10

Puntos: 1

Sea el autómata A = (∑, Q, f, q1, F) donde:

∑ ={a,b}, Q = {q1, q2, q3, q4}, F= { q4} y la función f vienen dada por la siguiente tabla:

Determine qué aspectos son válidos para el autómata

Seleccione al menos una respuesta.

	a. El lenguaje reconocido por el autómata es: a (b*b | a*b) a*	Correcto: Es un AFND. El lenguaje que reconoce es : a (b*b | a*b) a* o también a (b* | a* ) ba* para efectos de mejor comprensión, hay que recrear o realizar el autómata mediante un diagrama de Moore
	b. El lenguaje reconocido por el autómata es: a (b* | a* ) ba*	Correcto: Es un AFND. El lenguaje que reconoce es : a (b*b | a*b) a* o también a (b* | a* ) ba* para efectos de mejor comprensión, hay que recrear o realizar el autómata mediante un diagrama de Moore
	c. Es un Autómata Finito Determinístico con lambda transiciones
	d. Es un Autómata Finito Determinístico (AFD)

Correcto

Puntos para este envío: 1/1.

Question11

Puntos: 1

Dado los siguientes dos autómatas: identifique las apreciaciones verdaderas con respecto al comportamiento de los dos autómatas:

Seleccione una respuesta.

	a. Ambos autómatas son AFD	Correcto
	b. Solo un autómata es una máquina de estados que representa un lenguaje regular
	c. Ambos autómatas aceptan las mismas cadenas, como por ejemplo: {012,011,11,2222,1122,001122}
	d. Un autómata es AFD y el otro es AFND

Correcto

Puntos para este envío: 1/1.

Question12

Puntos: 1

Delos autómatas finitos (AF) es válido afirmar:

Seleccione al menos una respuesta.

	a. De manera informal se puede decir que un Autómata Finito aceptará una palabra de entrada si, comenzando por un estado especial llamado estado inicial y estando la cabeza de lectura apuntando al primer símbolo de la cadena, la máquina alcanza un estado final o de aceptación después de leer el último símbolo de la cadena	Correcto
	b. Los AF (Autómatas Finitos) pueden considerarse como mecanismos aceptadores o reconocedores de palabras	Correcto
	c. La memoria de un Autómata Finito (AF), está dada por sus estados	Correcto
	d. Un AF es una máquina sin memoria externa; son los estados los que resumen de alguna forma la información procesada	Correcto

Correcto

Puntos para este envío: 1/1.

Question13

Puntos: 1

Dados los siguientes dos autómatas finitos, identifique los aspectos válidos en cuanto a su comportamiento.

Seleccione una respuesta.

	a. Los dos autómatas son producto de una gramática libre de contexto GLC
	b. Los autómatas reconocen cadenas o palabras diferentes.
	c. La cadena {bb} solo es reconocida por un autómata.
	d. Corresponde a un proceso de conversión o transformación de un AFND a un AFD. Ambos autómatas reconocen el mismo lenguaje	Correcto: El primer autómata es un AFND y el segundo es el resultado de un proceso de conversión a AFD

Correcto

Puntos para este envío: 1/1.

Question14

Puntos: 1

Acerca del comportamiento de los estados en un autómata, indique que apreciaciones son válidas con respecto a su función y comportamiento:

Seleccione al menos una respuesta.

	a. Un estado de aceptación también puede ser inicial. Solo para autómatas finitos no
	b. Se define como el estado de un autómata es toda la información necesaria en un momento dado, para poder deducir, dado un símbolo de entrada en ese momento, cuál será el símbolo de salida.	Correcto
	c. Conocer el estado de un autómata, es lo mismo que conocer toda la historia de símbolos de entrada, así como el estado inicial. Estado en que se encontraba el autómata al recibir el primero de los símbolos de entrada.	Correcto
	d. Un estado de un autómata funciona de tal forma que cuando reciba a su entrada una determinada cadena de símbolos, indica si dicha cadena pertenece o no al lenguaje

Correcto

Puntos para este envío: 1/1.

Question15

Puntos: 1

Dada la siguiente gramática. (tenga en cuenta la ambigüedad).

S ---> Ac|Bd

A ---> aAb|ab

B ---> aBbb|abb

Esta genera el language:

Seleccione al menos una respuesta.

	a. A(potencia n)b(potencia n) c | n>=1	Correcto
	b. A (potencia n) b (potencia n) c (potencia n) | n>=1
	c. A (potencia n) b c | n>=1
	d. A (potencia n) b (potencia 2n) d | n>=1	Correcto

Correcto

Puntos para este envío: 1/1.