AUTOMATAS ACT5 QUIZ1

1

Puntos: 1

Dadas las siguientes expresiones regulares, analice la veracidad del cumplimiento de las igualdades e indique cuales son válidas:

Seleccione al menos una respuesta.

	a. 0* = (0*)*	Correcto: Son propiedades que cumplen las ER
	b. 0 . (1 . 0) = 0 . (1 + 0 ) *	Incorrecto:
	c. 0 . (1 . 0)* = (0 . 1)* . 0	Correcto: Son propiedades que cumplen las ER
	d. (0+1)*=(0*+1*)*	Correcto: Son propiedades que cumplen las ER

Correcto

Puntos para este envío: 1/1.

Question2

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 es “equivalente” al autómata B	Correcto: aceptan el mismo lenguaje.
	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 un AFND y reconoce el mismo lenguaje que el autómata B	Correcto. Además el autómata B resúltate de un proceso de equivalencia es un AFD.
	d. El autómata A NO es “equivalente” al autómata B.	Incorrecto

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. a +(ab)*
	b. (ab + aba)*	Correcto: Aceptará cadenas que empiecen por una a seguida de una b incluyendo la cadena vacía.
	c. (ab+ba) + a
	d. ab +(ab)*

Correcto

Puntos para este envío: 1/1.

Question4

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. 253
	b. 205	Incorrecto: equivale a la cadena 11001101 y esta no es reconocida
	c. 73
	d. 182

Incorrecto

Puntos para este envío: 0/1.

Question5

Puntos: 1

Para el siguiente Autómata, asocie la expresión regular que lo identifica:

Seleccione una respuesta.

	a. (0+1+0*)
	b. (10 + 0)*
	c. (10 + 0)* 10	Incorrecto: Se debe recorrer el autómata desde el estado inicial hasta algún estado de aceptación.
	d. (10 + 0)

Incorrecto

Puntos para este envío: 0/1.

Question6

Puntos: 1

Cuáles afirmaciones son válidas y que surgen de un análisis de las ER (Expresiones Regulares):

Analice los autómatas dados:

Seleccione al menos una respuesta.

	a. La ER (0+1)*01 genera las mismas cadenas para el Autómata “B” y del autómata “A”	Correcto: Ambas ER son equivalentes y aplican para el autómata. Se debe aplicar la propiedad de la operación matemática de la estrella de Kleene.
	b. La ER (0+1)*01 genera cadenas válidas para el autómata “A”, pero no para las del autómata “B”.	Incorrecto
	c. La ER (0+1)*11(01)* genera cadenas válidas para el autómata “B” pero no para las del autómata “A”.	Incorrecto
	d. La ER (1*00*1(00*1)*1)*1*00*1(00*1)* genera las mismas cadenas para el Autómata “A” el autómata “B”.	Correcto: Ambas ER son equivalentes y aplican para el autómata. Se debe aplicar la propiedad de la operación matemática de la estrella de Kleene.

Correcto

Puntos para este envío: 1/1.

Question7

Puntos: 1

Sean dos lenguajes L1 y L2 definidos sbre el mismo alfabeto ∑, la operación que se representa a continuación es:

L = L1L2 = {xy / x pertenece L1 Ʌ y pertenece L2}

Seleccione una respuesta.

	a. Unión de lenguajes
	b. Asociación de lenguajes
	c. Operación cerrada de dos lenguajes
	d. Concatenación de lenguajes	Correcto: La concatenación de ambos lenguajes estará formada por todas las palabras obtenidas al concatenar una palabra cualquiera de L1 con otra de L2.

Correcto

Puntos para este envío: 1/1.

Question8

Puntos: 1

Acerca de la clasificación de los lenguajes, identifique las afirmaciones válidas con referencia a la jerarquía y comportamiento de los mismos:

Seleccione al menos una respuesta.

	a. Se llama “clase de lenguajes” a conjuntos de lenguajes que comparten cierta propiedad dada.	Correcto
	b. Al clasificar lenguajes, no se están clasificando máquinas que los reconozcan, Se clasifican gramáticas que los generan.	Incorrecto: Tabla 6. Asociación de lenguajes, gramáticas y máquinas.
	c. Los lenguajes son en sí conjuntos de secuencias de símbolos y las clases de lenguajes son conjuntos de conjuntos de secuencias de símbolos.	Correcto
	d. Según la clasificación de lenguajes definida por Chomsky y que la llamó “jerarquía de lenguajes”, los “Lenguajes Regulares” es la clase más pequeña en la jerarquía, e incluye a los lenguajes más simples. Estos se llaman así porque sus palabras contienen “regularidades” o repeticiones de los mismos componentes.	Correcto

Correcto

Puntos para este envío: 1/1.

Question9

Puntos: 1

Dado el siguiente autómata, analice sus características verdaderas en comportamiento, diseño y lenguajes de aceptación:

Seleccione al menos una respuesta.

	a. Es Regular y cualquier cadena contiene al menos un cero.	Incorrecto: Es regular pero las cadenas no poseen esas características.
	b. Es Regular.	Correcto: Es un AFD y Regular.
	c. Es Regular e independiente del contexto por lo que contiene más de un estado Halt.	Incorrecto: La cantidad de estados de aceptación no determina si es independiente de contexto
	d. Es un autómata finito determinista (AFD).	Correcto: Es un AFD y Regular.

Correcto

Puntos para este envío: 1/1.

Question10

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	Incorrecto
	b. 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
	c. 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
	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	Incorrecto: Un autómata es reconocedor de lenguajes si tiene esa función. Pero un solo estado no puede determinar si reconoce o no una cadena. Depende de otros estados y más aún si no es de aceptación

Correcto

Puntos para este envío: 1/1.

Question11

Puntos: 1

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

Seleccione al menos una respuesta.

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

Correcto

Puntos para este envío: 1/1.

Question12

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 c | n>=1	Incorrecto
	b. A (potencia n) b (potencia n) c (potencia n) | n>=1	Incorrecto
	c. A(potencia n)b(potencia n) c | n>=1	Correcto
	d. A (potencia n) b (potencia 2n) d | n>=1	Correcto

Correcto

Puntos para este envío: 1/1.

Question13

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. Es un Autómata Finito Determinístico con lambda transiciones
	c. Es un Autómata Finito Determinístico (AFD)
	d. 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

Correcto

Puntos para este envío: 1/1.

Question14

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)	Correcto: esta afirmación es errada ya que las gramáticas generan lenguajes. Las máquinas o autómatas reconocen es lenguajes.
	b. Los lenguajes regulares pueden ser pueden ser descritos mediante expresiones regulares (ER)
	c. Los lenguajes que no poseen restricciones o de tipo 0, son reconocidos mediante Autómatas Finitos No Deterministas (AFND)
	d. Los lenguajes libres de contexto o de tipo 2, pueden ser generados por los autómatas de pila (AP)	Correcto: esta afirmación es errada ya que un lenguaje es descrito por una máquina y no generado por la máquina.

Parcialmente correcto

Puntos para este envío: 0.7/1.

Question15

Puntos: 1

Con los símbolos del alfabeto ∑ se forman cadenas, frases o palabras que se denotan por la letra ω. Algunas operaciones entre palabras son la concatenación y la inversa.

Que afirmaciones son válidas para estas propiedades y en algunas particularidades para el comportamiento de las cadenas o palabras (que se forman con los símbolos de un alfabeto) y que harían parte de un lenguaje.

Seleccione al menos una respuesta.

	a. La Inversión (ω potencia R) consiste en una operación sobre palabras o cadenas que escribe al revés una palabra. La palabra resultante se denomina inversa.	Correcto
	b. La concatenación por ejemplo no tiene la propiedad conmutativa, es decir: ω1 ω2 ≠ ω2 ω 1 .	Correcto
	c. En general (ω1 ω2 ) potencia R ≠ ω1 potencia R ω1 potencia R pero (ω1 ω2) potencia R = ω2 potencia R ω 1 potencia R	Correcto
	d. El Palíndromo se puede definir como: (ω = ω potencia R ).	Correcto: Ejemplo: ω = reconocer

Correcto

Puntos para este envío: 1/1.