AUTOMATAS ACT4 LECCION

1

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”.
	c. Los “Lenguajes Recursivamente Enumerables” solo incluye a los “Lenguajes Regulares”.	Incorrecto: La jerarquía de chomsky es estricta en la inclusión jerárquica de lenguajes.
	d. Los “Lenguajes Libres de Contexto” no incluyen a los “Lenguajes regulares”.

Incorrecto

Puntos para este envío: 0/1.

Question2

Puntos: 1

Dado el siguiente Autómata Finito (AF).

La Expresión Regular (ER) que denota el Lenguaje que representa es.

Seleccione una respuesta.

	a. xx*zx((zx+x*z)x)*
	b. xz(xz)*((x*+xx*z)x)*
	c. xxzx((zx)*z)*	Incorrecto: La ER no expresa as cadenas
	d. xx*zx((z+xx*z)x)*

Incorrecto

Puntos para este envío: 0/1.

Question3

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. ∑ *= 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.
	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 +) = Conjunto de todas las cadenas positivas excepto la vacía	Incorrecto: Conjunto de todas las cadenas excepto la vacía
	d. ∑ (potencia 0) = Conjunto de todas las cadenas sobre el alfabeto ∑ excepto la vacía.

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

Correcto

Puntos para este envío: 1/1.

Question5

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. Las transiciones lambda solo son aceptadas en la descripción de las gramáticas.	Incorrecto: Estas transiciones son aceptadas en AF.
	b. 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.
	c. No existe un autómata finito sin transiciones (lambda) que reconozca L.	Incorrecto: Si es posible este tipo de autómatas.
	d. Siempre existe un autómata finito determinista que reconoce un lenguaje reconocido por un autómata finito no determinista.	Correcto: Las cadenas vacías lambda son aceptadas y suelen presentarse en AFND.

Correcto

Puntos para este envío: 1/1.

Question6

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 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.
	b. 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
	c. 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
	d. Los Autómatas M1 y M2 son iguales pero no equivalentes

Correcto

Puntos para este envío: 1/1.

Question7

Puntos: 1

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

Seleccione una respuesta.

	a. xxxzxx
	b.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
	c. xzzxzxzx
	d. xzxxxxzxzzx

Correcto

Puntos para este envío: 1/1.

Question8

Puntos: 1

Que representa la siguiente figura:

Seleccione una respuesta.

	a. Un Autómata que acepta palabras o cadenas que contienen únicamente b´s o a´s
	b. 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 |∑|
	c. No representa un autómata válido por que el mismo estado inicial es el mismo estado final.
	d. Que representa la siguiente figura:

Correcto

Puntos para este envío: 1/1.

Question9

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.

Question10

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.