AUTOMATAS Y LENGUAJES FORMALES ACT5

1

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 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)
	c. Los lenguajes libres de contexto o de tipo 2, pueden ser generados por los autómatas de pila (AP)
	d. 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).

Parcialmente correcto

Puntos para este envío: 0.3/1.

Question2

Puntos: 1

Las condiciones mínimas para poder describir un Autómata Finito Determinístico (DFA) son:

Seleccione al menos una respuesta.

	a.Identificando el estado inicial y los estados finales.	Correcto: Un autómata puede describirse dando la lista de sus estados, el alfabeto, el estado inicial, los estados finales, y la función transición.
	b.Identificando el alfabeto.	Correcto: Un autómata puede describirse dando el alfabeto.
	c.Identificando la función de transición.	Correcto: Un autómata puede describirse dando la lista de sus estados, el alfabeto, el estado inicial, los estados finales, y la función transición.
	d. Dando la lista de sus estados.	Correcto: Un autómata puede describirse dando la lista de sus estados, el alfabeto, el estado inicial, los estados finales, y la función transición. Esta función se puede describir usando notación usual para definir funciones o usando una matriz, con una fila por cada estado y una columna por cada símbolo del alfabeto. Todas las condiciones son necesarias para describir el autómata.

Correcto

Puntos para este envío: 1/1.

Question3

Puntos: 1

Las siguientes cadenas:

{Lambda,aaa, bb, bbb, aabb, aba, abaaa, abbaa}

son generadas expresadas por la ER

Seleccione una respuesta.

	a. (a + b ) *
	b. (a.b)*
	c. (a,b)*	Incorrecto
	d. ( a | b)*

Incorrecto

Puntos para este envío: 0/1.

Question4

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

Correcto

Puntos para este envío: 1/1.

Question5

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 un autómata finito determinista (AFD).
	c. Es Regular e independiente del contexto por lo que contiene más de un estado Halt.
	d. Es Regular.

Incorrecto

Puntos para este envío: 0/1.

Question6

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	Incorrecto
	b. S ---> aSb | ab
	c. S ---> Sab | aSb
	d. S ---> Sa| Sb

Incorrecto

Puntos para este envío: 0/1.

Question7

Puntos: 1

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

Seleccione al menos una respuesta.

	a. 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
	b. Ambos son AFD y reconocen el mismo lenguaje
	c. 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.
	d. 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.	Incorrecto: Ambos autómatas son AFD y o reconocen el mismo lenguaje.

Correcto

Puntos para este envío: 1/1.

Question8

Puntos: 1

Dada la siguiente gramática con las siguientes producciones,

S --> ab

S ---> aSb

que derivaciones son válidas al usar sus reglas:

Seleccione al menos una respuesta.

	a. Bbaa
	b. aabb	Correcto
	c. ab
	d. Ba

Parcialmente correcto

Puntos para este envío: 0.5/1.

Question9

Puntos: 1

Analice e identifique cuáles afirmaciones son válidas con referencia al diseño del siguiente autómata:

Seleccione una respuesta.

	a. Es un autómata AFND que acepta el lenguaje (ab)* U (aba)* U a*b*
	b. Es un autómata finito no determinista que acepta la cadena {ababaab}
	c. Es un AFND que acepta el lenguaje (ab U aba)*	Correcto
	d. Es una autómata AFND cuya ER es: (ababa)*

Correcto

Puntos para este envío: 1/1.

Question10

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. 205
	b. 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”)
	c. 253
	d. 73

Correcto

Puntos para este envío: 1/1.

Question11

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
	d. (10 + 0)*	Correcto: La ER tiene en cuenta las transiciones vacías. Se tiene en cuenta la precedencia y jerarquía de símbolos.

Correcto

Puntos para este envío: 1/1.

Question12

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

Correcto

Puntos para este envío: 1/1.

Question13

Puntos: 1

Se pueden generar palíndromos (cadenas ω) sobre el alfabeto ∑ = {0,1}. Evidentemente este lenguaje tiene infinitas cadenas

Selecciones las afirmaciones válidas con referencia al anterior postulado.

Seleccione al menos una respuesta.

	a. Los símbolos de un alfabeto, definen el tipo de lenguaje a que pertenece.
	b. Los palíndromos son una excepción de los lenguajes regulares y no hacen parte de la jerarquía de Chomsky	Incorrecto: Los palíndromos tienen regularidades. Son lenguajes de tipo 3
	c. Existe un lenguaje denominado el lenguaje vacío que es un conjunto vacío y se denota por {Ø}. El lenguaje vacío no debe confundirse con un lenguaje que contenga una sola cadena.	Correcto
	d. ω = lambda ó cadena vacía y ω = 0 ; Son palíndromos

Parcialmente correcto

Puntos para este envío: 0.5/1.

Question14

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: (b+ab*a)*ab*	Correcto
	c. La ER que lo representa es: (b+ab*a)*
	d. La ER que lo representa es: (b*ab*a)*b*ab*

Parcialmente correcto

Puntos para este envío: 0.5/1.

Question15

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. Operación cerrada de dos lenguajes
	b. 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.
	c. Unión de lenguajes
	d. Asociación de lenguajes

Correcto

Puntos para este envío: 1/1.