AUTOMATAS Y LENGUAJES FORMALES ACT4

1

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. La concatenación de lenguajes sobre un alfabeto es una operación cerrada, y tiene un elemento neutro que es el lenguaje {lambda}.	Correcto. Es parte de las propiedades de los lenguajes
	c. A ∙ (B U C) = (A ∙ B) U (A ∙ C)
	d. 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.

Parcialmente correcto

Puntos para este envío: 0.5/1.

Question2

Puntos: 1

Que representa la siguiente figura:

Seleccione una respuesta.

	a. Que representa la siguiente figura:
	b. No representa un autómata válido por que el mismo estado inicial es el mismo estado final.
	c. Un Autómata que acepta palabras o cadenas que contienen únicamente b´s o a´s
	d. Un Autómata de tipo AFND válido.	Correcto: Es un Autómata Finito No Determinístico (AFND) válido. Es una extensión válida de un AFD. Permite que de cada nodo del diagrama de estados salga un número de flechas mayor o menor que |∑|

Correcto

Puntos para este envío: 1/1.

Question3

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 ω = Ø entonces L (ω) = Ø	Correcto: Esta es una ER
	b. Si ω = a y a pertenece ∑ entonces L (ω) no pertenece ∑
	c. Si ω* es una ER entonces L (ω*) no es una ER
	d. Si ω = lambda entonces L (lambda) = { lambda}	Correcto: Esta es una ER

Correcto

Puntos para este envío: 1/1.

Question4

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. En una máquina de estados finitos, la función de transición almacena los datos de entrada del Autómata.
	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 limitada.
	d. Los AF son máquinas de memoria amplia por ser máquinas abstractas (no reales).	Incorrecto: Se asemejan a una Maquina Real y estas tienen memoria limitada, finita.

Parcialmente correcto

Puntos para este envío: 0.5/1.

Question5

Puntos: 1

Sea el Autómata Finito (AF) A= (∑, Q, f. q1, F) donde ∑ = {0,1} , Q = {q1, q2, q3, q4}, F= { q2}  y definimos la función de transición fpor la tabla siguiente:

Indique cuál es lenguaje generado por el autómata:

Seleccione una respuesta.

	a. 1(01) *	Correcto: La expresión regular genera las cadenas que inician con 1 y que luego pueden o no tener un 0 o un 1
	b. 1*(1)
	c. 1( 1) (0)*
	d. 0(010)*

Correcto

Puntos para este envío: 1/1.

Question6

Puntos: 1

Teniendo en cuenta las clases de lenguajes propuestos por la jerarquía de Chomsky, es común o aplica afirmar:

Seleccione una respuesta.

	a. La mayoría de los lenguajes de programación son “Lenguajes Libres de Contexto”.	Correcto: Los lenguajes libres de contexto incluyen a los lenguajes regulares. Los lenguajes regulares son la clase más pequeña dentro de la jerarquía de Chomsky. Los lenguajes recursivamente enumerables incluyen a los lenguajes libres de contexto.
	b. Los “Lenguajes Regulares” es la jerarquía más alta y compleja. Un ejemplo de lenguaje regular es el conjunto de todos los números binarios.
	c. Los “Lenguajes Recursivamente Enumerables” solo incluye a los “Lenguajes Regulares”.
	d. Los “Lenguajes Libres de Contexto” no incluyen a los “Lenguajes regulares”.

Correcto

Puntos para este envío: 1/1.

Question7

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 aceptan ambos el lenguaje a *
	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.	Incorrecto: Ambos rechazan el lenguaje “b”. Ambos aceptan exactamente el mismo lenguaje.
	d. Los Autómatas M1 y M2 son iguales pero no equivalentes	Incorrecto: No son iguales

Parcialmente correcto

Puntos para este envío: 0.5/1.

Question8

Puntos: 1

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

Seleccione una respuesta.

	a. Es un Autómata Finito Determinista (AFD).
	b. Es un Autómata Regular	Incorrecto: Es un AFD
	c. Es un Autómata Finito que acepta la palabra vacía
	d. Es un Autómata Finito No Determinístico (AFND)

Incorrecto

Puntos para este envío: 0/1.

Question9

Puntos: 1

Para el siguiente Autómata Finito denotado como: A2= (E. Q, f, q1, F) donde E = {0,1}, F = {q2} y Q = {q1, q2, q3, q4}, identifique correctamente el Lenguaje que genera y la expresión regular:

Seleccione una respuesta.

	a. L = (A2 ) = {0, 001, 01111, …} = { 1(10)n |n ≤ 0} La expresión regular es: 0(01) *
	b. L = (A2 ) = {0, 001, 00100, …} = { 1(01)n |n ≠ 0} La expresión regular es: 0(01) *
	c. L = (A2 ) = {0, 111, 11100, …} = { 1(10)n |n = 0} La expresión regular es: 1(01)+
	d. L = (A 2) = {1, 101, 10101, …} = { 1(01)n |n ≥ 0} La expresión regular es: 1(01) *	Correcto: El lenguaje generado se obtiene partiendo del estado inicial y recorriendo todos los caminos posibles para alcanzar el estado final

Correcto

Puntos para este envío: 1/1.

Question10

Puntos: 1

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

Seleccione una respuesta.

	a. xxxxzxzxzxzx
	b. xzzxzxzx
	c. xxxzxx	Incorrecto: Al recorrer la cadena no llega al estado final o halt
	d. xzxxxxzxzzx

Incorrecto

Puntos para este envío: 0/1.