AUTOMATAS Y LENGUAJES FORMALES ACT4

1

Puntos: 1

Dado un alfabeto ∑, los símbolos Ø, lambda y los operadores + (unión), ∙ (punto) (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 ω* es una ER entonces L (ω*) no es una ER
	c. Si ω = Ø entonces L (ω) = Ø	Correcto: Esta es una ER
	d. Si ω = lambda entonces L (lambda) = { lambda}	Correcto: Esta es una ER

Correcto

Puntos para este envío: 1/1.

Question2

Puntos: 1

Algunas operaciones y propiedades sobre lenguajes y ER que se pueden realizar son:

Seleccione al menos una respuesta.

	a. (B U C) ∙ A = (B ∙ A) U (C ∙ A)	Correcto: Se está identificando o definiendo que la concatenación de lenguajes es distributiva con respecto a la unión.
	b. A ∙ (B U C) = (A ∙ B) U (A ∙ C)	Correcto: Se está identificando o definiendo que la concatenación de lenguajes es distributiva con respecto a la unión
	c. El orden de prioridad de los operadores es, de mayor a menor: *, ∙, + Este orden puede alterarse mediante paréntesis, de forma análoga a como se hace con las expresiones aritméticas.	Correcto
	d. La concatenación de lenguajes sobre un alfabeto es una operación cerrada, y tiene un elemento neutro que es el lenguaje {lambda}.

Parcialmente correcto

Puntos para este envío: 0.8/1.

Question3

Puntos: 1

Cuáles afirmaciones son válidas cuando se trata de analizar el funcionamiento de los Autómatas Finitos (AF):

Seleccione al menos una respuesta.

	a. Los AF son máquinas de memoria limitada.	Correcto: Los estados son el único medio de que disponen los AF para recordar los eventos que ocurren (por ejemplo, qué caracteres se han leído hasta el momento); esto quiere decir que son máquinas de memoria limitada.
	b. Los estados son el único medio de que disponen los AF para recordar los eventos que ocurren (por ejemplo que caracteres se han leído hasta el momento).	Correcto: Los estados son el único medio de que disponen los AF para recordar los eventos que ocurren (por ejemplo, qué caracteres se han leído hasta el momento); esto quiere decir que son máquinas de memoria limitada.
	c. Los AF son máquinas de memoria amplia por ser máquinas abstractas (no reales).
	d. En una máquina de estados finitos, la función de transición almacena los datos de entrada del Autómata.

Correcto

Puntos para este envío: 1/1.

Question4

Puntos: 1

La expresión regular que se asocia la siguiente autómata es:

Seleccione una respuesta.

	a. r = (1)* + (0) + lambda
	b. r = (10) * + 1*
	c. r = (1 + 0) + 1*
	d. r = (10 + 0) *	Correcto: Las cadenas que tengan varios unos consecutivos son rechazadas

Correcto

Puntos para este envío: 1/1.

Question5

Puntos: 1

Una característica que presenta el Autómata Finito siguiente es:

Seleccione una respuesta.

	a. Es un Autómata Finito No Determinístico (AFND)
	b. Es un Autómata Finito Determinista (AFD).	Correcto: Es determinista porque de sus nodos no se repiten salida pro interacciones con el mismo símbolo. Se acepta la condición teórico de determinismo.
	c. Es un Autómata Finito que acepta la palabra vacía
	d. Es un Autómata Regular

Correcto

Puntos para este envío: 1/1.

Question6

Puntos: 1

Una cadena válida para el Autómata siguiente es:

Seleccione una respuesta.

	a. xxxzxx
	b. xzxxxxzxzzx
	c.xxxxzxzxzxzx	Correcto: Toda cadena para ese autómata empezará con x y terminará en una sola x. Se recorre el autómata con la cadena xxxxzxzxzxzx
	d. xzzxzxzx

Correcto

Puntos para este envío: 1/1.

Question7

Puntos: 1

Se diseña el siguiente Autómata Finito Deterministico (AFD) para el lenguaje de palabras del alfabeto {a,b} que no tiene varias a´s seguidas. Esta solución es defectuosa porque.

Seleccione al menos una respuesta.

	a. Tiene dos finales o de aceptación q1 y q2
	b. Hay palabras como “baa”, que tiene a´s seguidas y sin embargo son aceptadas por el AFD.	Correcto: El "problema de diseño" de un AFD es considerar demasiadas posibilidades. El hecho que tenga dos estados finales o de aceptación no es problema y es válido en el diseño. La palabra "baba" No es aceptada por el autómata aunque sus elementos o símbolos si hacen parte del alfabeto que las compone.
	c. Hay palabras como “ba”, que no tienen a´s seguidas y sin embargo no son aceptadas por el AFD.	Correcto: El "problema de diseño" de un AFD es considerar demasiadas posibilidades. El hecho que tenga dos estados finales o de aceptación no es problema y es válido en el diseño. La palabra "baba" No es aceptada por el autómata aunque sus elementos o símbolos si hacen parte del alfabeto que las compone.
	d. Hay palabras como “baba” que no tienen a´s seguidas y sin embargo son aceptadas por el AFD pero que no pertenecen al alfabeto dado.

Correcto

Puntos para este envío: 1/1.

Question8

Puntos: 1

Dado los autómatas M1 y M2 siguientes, cuáles relaciones entre estas dos máquinas son válidas.

Seleccione al menos una respuesta.

	a. Los Autómatas M 1 y M2 son equivalentes: M1 ≈ M2 , por que aceptan exactamente el mismo lenguaje	Correcto: La equivalencia se da por la aceptación de lenguajes. Ambos aceptan el lenguaje a * y aceptan exactamente el mismo lenguaje
	b. Los Autómatas M1 y M2 son iguales pero no equivalentes
	c. Los Autómatas M1 y M2 no son equivalentes porque ambos rechazan el lenguaje b*. La equivalencia se da en la aceptación de lenguajes.
	d. Los Autómatas M1 y M2 aceptan ambos el lenguaje a *	Correcto: La equivalencia se da por la aceptación de lenguajes. Ambos aceptan el lenguaje a * y aceptan exactamente el mismo lenguaje

Correcto

Puntos para este envío: 1/1.

Question9

Puntos: 1

Dado el Autómata con la siguiente tabla de transición, identifique las cadenas que son válidas para el lenguaje que acepta

Seleccione una respuesta.

	a. Es un AFND y acepta cualquier cadena que inicie con cero (0)
	b. {101, 210, 20,110, 200}
	c. Solo acepta cadenas vacías (lambda).	Incorrecto: Es un AND de landa transiciones. Aceptará las cadenas que inicien con un orden jerárquico de números (es decir de menor a mayor, siendo válida la repetición de los mismos), Ej 012, 12 pero nunca 210, 20 entre otros.
	d. {22, 0,1,001122, 12, 012, 022}

Incorrecto

Puntos para este envío: 0/1.

Question10

Puntos: 1

Dado el siguiente “Autómata Finito” cuyo diagrama de transición corresponde al de la siguiente figura, determine cual afirmación es válida cuando se analiza la ejecución del autómata.

Seleccione una respuesta.

	a. El conjunto de cadenas que es capaz de reconocer este autómata es. {b}
	b. El conjunto de cadenas que es capaz de reconocer este autómata es. {Ø, Øb, bb, bbb, bbbb, …}
	c. El conjunto de cadenas que es capaz de reconocer este autómata es. {b, bb, bbb, bbbb, …}
	d. El conjunto de cadenas que es capaz de reconocer este autómata es {b, bb, bbb}	Correcto: Se evalúa la cadena hasta llegar al estado de aceptación o final q5. El conjunto de cadenas que es capaz de aceptar este autómata es {b,bb.bbb}

Correcto

Puntos para este envío: 1/1.