AUTOMATAS Y LENGUAJES FORMALES ACT4

1

Puntos: 1

Analice el siguiente Autómata y determine cuáles apreciaciones son válidas en su análisis:

Seleccione al menos una respuesta.

	a. La función de transición define para cada posible combinación (0,1) un estado nuevo.	Incorrecto
	b. La función de transición puede no estar definida para alguna combinación (0,1) y, por el contrario, puede definir para otras combinaciones (0,1) más de un estado.
	c. Es un autómata no determinístico (AFND), con un conjunto finito de estados y símbolos de entrada, un estado inicial, un conjunto de estados finales, y una función de transición de estados.
	d. Es un autómata determinístico (AFD), con un conjunto finito de estados y símbolos de entrada, un estado inicial, un conjunto de estados finales, y una función de transición de estados.	Incorrecto. Es un AFND

Incorrecto

Puntos para este envío: 0/1.

Question2

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 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.
	c. 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.
	d. Los AF son máquinas de memoria amplia por ser máquinas abstractas (no reales).

Correcto

Puntos para este envío: 1/1.

Question3

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, bb, bbb, bbbb, …}
	b. El conjunto de cadenas que es capaz de reconocer este autómata es. {b, bb, bbb, bbbb, …}	Incorrecto: “bbbb” no es aceptada, ni tampoco el símbolo vacío.
	c. El conjunto de cadenas que es capaz de reconocer este autómata es {b, bb, bbb}
	d. El conjunto de cadenas que es capaz de reconocer este autómata es. {b}

Incorrecto

Puntos para este envío: 0/1.

Question4

Puntos: 1

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

Seleccione una respuesta.

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

Incorrecto

Puntos para este envío: 0/1.

Question5

Puntos: 1

Dado el siguiente autómata, las apreciaciones verdaderas en expresiones regulares (ER) y cadenas aceptadas son:

Seleccione al menos una respuesta.

	a. (x + y)*(x+y) acepta la cadena {xy}.	Correcto: Se parte que la ER de la izquierda para todas las opciones es válida y expresa el lenguaje que representa el autómata. Acepta la cadena xy y rechaza la cadena vacía.
	b. (x + y)*(x+y) rechaza la cadena vacía	Correcto: Rechaza la cadena vacía.
	c. (x + y)*(x+y) acepta la cadena vacía y el autómata es determinista
	d. (x + y)*(x+y) es igual a (x* x U y y*)	Incorrecto: Esta asociación no es válida para la ER que representa el autómata.

Correcto

Puntos para este envío: 1/1.

Question6

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. 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.
	c. {101, 210, 20,110, 200}
	d. {22, 0,1,001122, 12, 012, 022}

Incorrecto

Puntos para este envío: 0/1.

Question7

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 + 0) *	Correcto: Las cadenas que tengan varios unos consecutivos son rechazadas
	c. r = (10) * + 1*
	d. r = (1 + 0) + 1*

Correcto

Puntos para este envío: 1/1.

Question8

Puntos: 1

Si se considera un autómata finito M con transiciones lambda que reconoce el lenguaje L: De la relación entre determinista y no determinista de los autómatas, y el comportamiento de las cadenas vacías (lambda), es válido afirmar

Seleccione al menos una respuesta.

	a. Un autómata finito con transiciones lambda es un autómata no determinista.	Correcto: Las cadenas vacías lambda son aceptadas y suelen presentarse en AFND.
	b. Las transiciones lambda solo son aceptadas en la descripción de las gramáticas.
	c. Siempre existe un autómata finito determinista que reconoce un lenguaje reconocido por un autómata finito no determinista.
	d. No existe un autómata finito sin transiciones (lambda) que reconozca L.

Parcialmente correcto

Puntos para este envío: 0.5/1.

Question9

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. 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.
	b. 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.
	c. Los “Lenguajes Libres de Contexto” no incluyen a los “Lenguajes regulares”.
	d. Los “Lenguajes Recursivamente Enumerables” solo incluye a los “Lenguajes Regulares”.

Correcto

Puntos para este envío: 1/1.

Question10

Puntos: 1

Si ∑ es un alfabeto, se le llama ∑ (potencia n) al conjunto de todas las palabras de longitud n sobre ∑.

Identifique las notaciones de conjuntos válidas para la creación de palabras sobre el alfabeto ∑

Seleccione al menos una respuesta.

	a. ∑ (potencia +) = Conjunto de todas las cadenas positivas excepto la vacía	Incorrecto: Conjunto de todas las cadenas excepto la vacía
	b. ∑ (potencia 0) = {lambda} Conjunto cuyo único elemento es la palabra vacía.	Correcto: La longitud de una cadena ω que se denota como |ω| es el número de letras que aparecen en ω. A la cadena que no tiene símbolos o que es lo mismo decir que tiene longitud cero, se le llama palabra vacía. Si ∑ es un alfabeto, se le llama ∑ n al conjunto de todas las palabras de longitud n sobre ∑. la estrella * genera el conjunto de todas las cadena de cualquier longitud sobre ∑. Si se analiza ∑ + esta representa al conjunto de todas las cadenas sobre el alfabeto ∑ excepto la vacía.
	c. ∑ (potencia 0) = Conjunto de todas las cadenas sobre el alfabeto ∑ excepto la vacía.
	d. ∑ *= Conjunto de todas las cadenas de cualquier longitud sobre ∑	Correcto: La longitud de una cadena ω que se denota como |ω| es el número de letras que aparecen en ω. A la cadena que no tiene símbolos o que es lo mismo decir que tiene longitud cero, se le llama palabra vacía. Si ∑ es un alfabeto, se le llama ∑ n al conjunto de todas las palabras de longitud n sobre ∑. la estrella * genera el conjunto de todas las cadena de cualquier longitud sobre ∑. Si se analiza ∑ + esta representa al conjunto de todas las cadenas sobre el alfabeto ∑ excepto la vacía.

Correcto

Puntos para este envío: 1/1.