AUTOMATAS CURSO COMPLETO

1

Puntos: 1

En Octubre de 1950, Alan Turing hizo estudios más abstractos y trató el tema de la Inteligencia artificial. Para ello propuso un experimento que hoy se conoce como el “test de Turig”. Que consiste básicamente en: (seleccione la verdadera).

Seleccione una respuesta.

	a. Prueba de error que determina cuando un problema tiene solución o no.
	b. Procedimientos para evaluar decisiones lógicas de una máquina.
	c. “Método” para determinar si una máquina puede pensar.	Correcto: El Test de Turing nace como un método para determinar si una máquina puede pensar.
	d. Método para evaluar el rendimiento y capacidad de una maquia. “Poder de procesamiento”

Biografía de Alan Turing

Correcto

Puntos para este envío: 1/1.

Question2

Puntos: 1

Hasta estas épocas recientes, la comunidad científica ha reconocido el trabajo del matemático inglés Alan Turing. Los logros más reconocidos son:

Seleccione al menos una respuesta.

	a. La máquina de computación universal
	b. Sus aportes al estudio de la inteligencia artificial.	Correcto
	c. Sus estudios en la teoría de la “morfogénesis”
	d. Su trabajo en criptografía	Correcto: Aplicado a descifrar códigos secretos en la segunda guerra mundial.

Biografía de Alan Turing

Parcialmente correcto

Puntos para este envío: 0.5/1.

Question3

Puntos: 1

Turing trabajo desde 1952 – 1954 en la Biología Matemática (Morfogénesis). Publicó un trabajo titulado “Fundamentos químicos de la morfogénesis”. Su principal interés era: (seleccione los verdaderos).

Seleccione al menos una respuesta.

	a. Comprender la existencia de números de Fibonacci en las estructuras vegetales.	Correcto
	b. Comprender la phyllotaxis de fibonacci.	Correcto: Utilizó ecuaciones de reacción-difusión actualmente usadas en el campo de la formación de patrones.
	c. Definir los números áureos y sus características.
	d. Comprender la secuencia de Fibonacci y determinar si es finta o infinita.

Biografía de Alan Turing

Correcto

Puntos para este envío: 1/1.

Question4

Puntos: 1

Ala Turing en 1948 trabajó en la construcción del software (lenguaje de programación) para una de las primeras máquinas reales. Esta máquina era llamada:

Seleccione una respuesta.

	a. Eniac
	b. Univac
	c. Manchester Mark I	Correcto: Fuente: http://es.wikipedia.org/wiki/Manchester_Mark_I
	d. Edvac

Biografía de Alan Turing

Correcto

Puntos para este envío: 1/1.

Question5

Puntos: 1

Identifique los acontecimientos que dentro del marco histórico sucedieron en torno a la vida del matemático Alan Turing.

Seleccione una respuesta.

	a. En el mismo año que nació Alan Mathison Turing, aconteció el hundimiento del trasatlántico Británico “El Titanic”
	b. El Padre de Alan Mathison Turing: Julius Mathison Turing era de origen Polaco.
	c. Alan Mathison Turing fue criado siempre al lado de sus padres. Por eso su cultura y legado que ha dejado a raíz de las enseñanzas y educación que ellos le dieron.
	d. Alan Mathison Turing murió a los 48 años de edad. Se cree que fue un suicidio aunque hay apartes de la historia que mienten esta versión.	Incorrecto: Alan Mathison Turing murió a los 42 años de edad.

Biografía de Alan Turing

Incorrecto

Puntos para este envío: 0/1.

Question6

Puntos: 1

En 1936, Alonzo Churh fue director de tesis del trabajo de grado doctoral de Alan Turing quién le siguió sus pasos “estudios” en lógica y computabilidad. El nombre del trabajo doctoral fue “Sistemas de lógica basada en ordinales sobre números computables”. Este tema ya lo había tratado Davd Gilbert en 1928. Este trabajo es el que hoy en día ha llevado a:

Seleccione una respuesta.

	a. Establecer los principios de la criptografía.
	b. Definir los conceptos modernos de lógica
	c. Establecer las nociones de lo que hoy se conoce como la “Máquina de Turing”	Correcto
	d. Determinar las teorías de números ordinales y de algoritmos.

Biografía de Alan Turing

Correcto

Puntos para este envío: 1/1.

1

Puntos: 1

La precedencia (orden jerárquico a la hora de hacer operaciones y determinar lenguajes) de las operaciones en las Expresiones Regulares (ER) es:

Seleccione una respuesta.

	a. Concatenación (ab), Unión (a+b), Clausura (a)*
	b. Clausura (a)* , Concatenación (ab), Unión (a+b)
	c. Clausura (a)*. Unión (ab) , Concatenación (a ∙ b)	Incorrecto: La precedencia de las operaciones es Clausura, Conctenación , Unión. Los paréntesis se pueden eliminar siempre que no haya duda.
	d. Concatenación (a ∙ b), Unión (ab), Clausura (a)*

Incorrecto

Puntos para este envío: 0/1.

Question2

Puntos: 1

Los Autómatas finitos no determinísticos (AFND) es una quíntupla donde todos los componentes son como en los AFDs, estos autómatas aceptan exactamente los mismos lenguajes que los autómatas determinísticos, pero cuentan con una diferencia con relación a los AFD como es.

Seleccione una respuesta.

	a. El alfabeto de entrada
	b. El conjunto finito de estados.
	c. El estado inicial.
	d. La función de transición.	Correcto: Solo la función de transición puede diferenciar los AFD de los AFND. Las demás opciones pueden ser comunes a ambos tipos de autómatas y válidas.

Correcto

Puntos para este envío: 1/1.

Question3

Puntos: 1

La “Teoría de Lenguajes”, define bloques constructores de lenguaje. El bloque más sencillo es el alfabeto. De las siguientes afirmaciones cuales definen o son verdaderas con respecto a un “alfabeto”:

Seleccione al menos una respuesta.

	a. Los alfabetos están compuestos por cadenas. Ya sean aceptadas o no. Ejemplo el alfabeto del español latino: Una cadena válida es {sistemas}. Una cadena no aceptada es {temas}.
	b. { α1 , α2 ,..... α n } Es un ejemplo de alfabeto	Correcto: Lenguaje Formal: Un alfabeto es un conjunto finito de símbolos. De esta definición se debe resaltar lo siguiente. (1) Los alfabetos son finitos. (2) Por símbolo no se está haciendo referencia a un sólo carácter. Los símbolos pueden ser nombres
	c. Por símbolo, se está haciendo referencia a un solo carácter.
	d. Los símbolos pueden ser nombres. Los alfabetos son finitos.	Correcto: Lenguaje Formal: Un alfabeto es un conjunto finito de símbolos. De esta definición se debe resaltar lo siguiente. (1) Los alfabetos son finitos. (2) Por símbolo no se está haciendo referencia a un sólo carácter. Los símbolos pueden ser nombres

Correcto

Puntos para este envío: 1/1.

Question4

Puntos: 1

Sea el vocabulario {a,b,c}, la expresión regular (a|b)*c  indica el conjunto de todas las cadenas formadas con los símbolos a, b y c . Cuáles sentencias o cadenas son válidas:

Seleccione al menos una respuesta.

	a. acbbaa
	b.ababaabbc	Correcto: Es una combinación válida. Pueden formarse cadenas con los símbolos a y b, sucediéndose cualquier número de veces ( y en cualquier orden) y siempre terminando la cadena en el símbolo c
	c. bbaccaa
	d. bbaaac	Correcto: Es una combinación válida. Pueden formarse cadenas con los símbolos a y b, sucediéndose cualquier número de veces ( y en cualquier orden) y siempre terminando la cadena en el símbolo c

Correcto

Puntos para este envío: 1/1.

Question5

Puntos: 1

La minimización de Autómatas, es un ejercicio común en Automatización. Identifique su concepto básico y aplicabilidad:

Seleccione una respuesta.

	a. Un autómata se puede minimizar siempre y cuando el autómata dado no acepte cadenas vacías.
	b. La minimización se aplica a los AFND y consiste en obtener un autómata equivalente que tenga el menor número de transiciones posibles
	c. La minimización se aplica a los AFD y consiste en obtener un AFD equivalente a uno dado que tenga el menor número de estados posibles.
	d. En la minimización de autómatas, el número de estados o de relaciones debe ser equivalente en cantidad inferior al dado.	Incorrecto: No necesariamente si se reducen n estados, se deben reducir esa misma n transiciones.

Incorrecto

Puntos para este envío: 0/1.

Question6

Puntos: 1

Un alfabeto es un conjunto finito de símbolos. De esta definición podemos afirmar correctamente:

Seleccione al menos una respuesta.

	a. Dado un alfabeto, podemos formar palabras o cadenas con los símbolos del alfabeto	Correcto: Es el principio básico para empezar a tratar con lenguajes.
	b. Por ser un alfabeto un conjunto finito de elementos, las posibles cadenas que se formen no pueden ser vacías
	c. Las cadenas que se forman a partir de un alfabeto finito, resultan ser infinitas.
	d. Por símbolo no se está haciendo referencia a un sólo carácter. Los símbolos pueden ser nombres.	Correcto: Lenguaje Formal: Un alfabeto es un conjunto finito de símbolos. De esta definición se debe resaltar lo siguiente. (1) Los alfabetos son finitos. (2) Por símbolo no se está haciendo referencia a un sólo carácter. Los símbolos pueden ser nombres

Correcto

Puntos para este envío: 1/1.

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.

1

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

Correcto

Puntos para este envío: 1/1.

Question2

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

Correcto

Puntos para este envío: 1/1.

Question3

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

Correcto

Puntos para este envío: 1/1.

Question4

Puntos: 1

Dados los siguientes autómatas determine que características aplican en cuanto a su comportamiento y diseño.

Seleccione al menos una respuesta.

	a. El autómata A NO es “equivalente” al autómata B.	Incorrecto
	b. La cadena bababbaabb la reconocen los dos autómatas.	Correcto: esta cadena es aceptada por ambos autómatas. Además amas máquinas son equivalentes
	c. El autómata A es “equivalente” al autómata B
	d. El autómata A es un AFND y reconoce el mismo lenguaje que el autómata B

Parcialmente correcto

Puntos para este envío: 0.3/1.

Question5

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

Correcto

Puntos para este envío: 1/1.

Question6

Puntos: 1

Cual expresión regular (ER) representa el lenguaje que contiene una subcadena 11

Seleccione una respuesta.

	a. 10*0+1(0,1)*
	b. (1,0)*+(0,1)*01
	c. ((0+1))*,1,1 . ((0+1))*	Correcto: esta ER acepta la subcadena 11
	d. (((01)*+(01)*0)+((10)*+(10)*1))

Correcto

Puntos para este envío: 1/1.

Question7

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

Parcialmente correcto

Puntos para este envío: 0.3/1.

Question8

Puntos: 1

Analice el siguiente diagrama de Moore e identifique las apreciaciones válidas:

Seleccione al menos una respuesta.

	a. Es un AF.	Correcto
	b. No tiene alfabeto definido
	c. No es un autómata válido en diseño
	d. Es una aplicación de los autómatas. Un interruptor de luz	Correcto

Correcto

Puntos para este envío: 1/1.

Question9

Puntos: 1

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

Seleccione al menos una respuesta.

	a. 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.
	b. 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
	c. Ambos son AFD y reconocen el mismo lenguaje
	d. 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.

Correcto

Puntos para este envío: 1/1.

Question10

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

Correcto

Puntos para este envío: 1/1.

Question11

Puntos: 1

Dado los siguientes dos autómatas: identifique las apreciaciones verdaderas con respecto al comportamiento de los dos autómatas:

Seleccione una respuesta.

	a. Ambos autómatas son AFD	Correcto
	b. Solo un autómata es una máquina de estados que representa un lenguaje regular
	c. Ambos autómatas aceptan las mismas cadenas, como por ejemplo: {012,011,11,2222,1122,001122}
	d. Un autómata es AFD y el otro es AFND

Correcto

Puntos para este envío: 1/1.

Question12

Puntos: 1

Delos autómatas finitos (AF) es válido afirmar:

Seleccione al menos una respuesta.

	a. De manera informal se puede decir que un Autómata Finito aceptará una palabra de entrada si, comenzando por un estado especial llamado estado inicial y estando la cabeza de lectura apuntando al primer símbolo de la cadena, la máquina alcanza un estado final o de aceptación después de leer el último símbolo de la cadena	Correcto
	b. Los AF (Autómatas Finitos) pueden considerarse como mecanismos aceptadores o reconocedores de palabras	Correcto
	c. La memoria de un Autómata Finito (AF), está dada por sus estados	Correcto
	d. Un AF es una máquina sin memoria externa; son los estados los que resumen de alguna forma la información procesada	Correcto

Correcto

Puntos para este envío: 1/1.

Question13

Puntos: 1

Dados los siguientes dos autómatas finitos, identifique los aspectos válidos en cuanto a su comportamiento.

Seleccione una respuesta.

	a. Los dos autómatas son producto de una gramática libre de contexto GLC
	b. Los autómatas reconocen cadenas o palabras diferentes.
	c. La cadena {bb} solo es reconocida por un autómata.
	d. Corresponde a un proceso de conversión o transformación de un AFND a un AFD. Ambos autómatas reconocen el mismo lenguaje	Correcto: El primer autómata es un AFND y el segundo es el resultado de un proceso de conversión a AFD

Correcto

Puntos para este envío: 1/1.

Question14

Puntos: 1

Acerca del comportamiento de los estados en un autómata, indique que apreciaciones son válidas con respecto a su función y comportamiento:

Seleccione al menos una respuesta.

	a. Un estado de aceptación también puede ser inicial. Solo para autómatas finitos no
	b. Se define como el estado de un autómata es toda la información necesaria en un momento dado, para poder deducir, dado un símbolo de entrada en ese momento, cuál será el símbolo de salida.	Correcto
	c. Conocer el estado de un autómata, es lo mismo que conocer toda la historia de símbolos de entrada, así como el estado inicial. Estado en que se encontraba el autómata al recibir el primero de los símbolos de entrada.	Correcto
	d. Un estado de un autómata funciona de tal forma que cuando reciba a su entrada una determinada cadena de símbolos, indica si dicha cadena pertenece o no al lenguaje

Correcto

Puntos para este envío: 1/1.

Question15

Puntos: 1

Dada la siguiente gramática. (tenga en cuenta la ambigüedad).

S ---> Ac|Bd

A ---> aAb|ab

B ---> aBbb|abb

Esta genera el language:

Seleccione al menos una respuesta.

	a. A(potencia n)b(potencia n) c | n>=1	Correcto
	b. A (potencia n) b (potencia n) c (potencia n) | n>=1
	c. A (potencia n) b c | n>=1
	d. A (potencia n) b (potencia 2n) d | n>=1	Correcto

Correcto

Puntos para este envío: 1/1.

1

Puntos: 1

Los Autómatas de Pila (AP) funcionan de manera que el ultimo carácter que se almacena en ella es el primero en salir (“LIFO” por las siglas en inglés), como si se apilaran platos uno encima de otro, y naturalmente el primero que quitaremos es el último que hemos Colocado. Otros aspectos válidos de su funcionamiento son:

Seleccione al menos una respuesta.

	a. Una cadena en un AP será aceptada cuando llegue al estado final.
	b. En un AP podemos modificar su “tope”, que es el extremo por donde entran o salen los caracteres	Correcto
	c. Sin importar si la pila está vacía o no, este siempre hará un movimiento.
	d. Los caracteres a la mitad de la pila no son accesibles sin quitar antes los que están encima de ellos.	Correcto

Correcto

Puntos para este envío: 1/1.

Question2

Puntos: 1

Con referencia las gramáticas de Tipo 2, que aspectos válidos hacen referencia a la forma de generar lenguajes de tipo 2 y su comportamiento y descripción:

Seleccione al menos una respuesta.

	a. Las producciones son de la forma: A - aa Dado que hay un carácter de lectura y uno de escritura
	b. Si M es un AP, entonces L(M) es un LLC	Correcto
	c. Si L es un LLC, entonces hay un AP M tal que L(M) = L	Correcto
	d. Los autómatas de pila aceptan exactamente los LLC (Lenguajes Libres de Contexto).

Parcialmente correcto

Puntos para este envío: 0.7/1.

Question3

Puntos: 1

Indique cuál de las siguientes afirmaciones es falsa teniendo en cuenta el determinismo de los autómatas finitos. (AF).

Seleccione una respuesta.

	a. Un autómata finito no determinista de q estados y n símbolos puede tener a lo sumo n × q2 transiciones	Esta afirmación es válida
	b. El número máximo de transiciones de un autómata finito determinista depende del número de estados y del número de símbolos del alfabeto del autómata
	c. Un autómata finito determinista de q estados y n símbolos tiene n × q transiciones
	d. Un autómata finito no determinista puede tener un número ilimitado de transiciones distintas

Incorrecto

Puntos para este envío: 0/1.

Question4

Puntos: 1

Analice la relación que tiene el siguiente autómata con la gramática.

S → xS  / S → yA  /  S → zB  / A → yA  /  A → yB  / B → zB / B → Lambda 

Seleccione la opción que sea verdadera.

Seleccione una respuesta.

	a. Es un autómata finito determinístico (AFD)
	b. La gramática y el autómata no generan ningún lenguaje
	c. La gramática y el autómata son equivalentes.	Incorrecto: Generan lenguajes diferentes
	d. La gramática y el autómata no son equivalentes.

Incorrecto

Puntos para este envío: 0/1.

Question5

Puntos: 1

Dada la Gramática S→aS; S→aSbS; S→lambda .

Indique cuáles de las siguientes afirmaciones no corresponden al desarrollo de la misma o al tipo de cadenas o palabras ω que pueda generar.

Seleccione al menos una respuesta.

	a. Para cualquier prefijo de una cadena generada por la gramática se verifica que el número de letras a es mayor o igual al número de letras b. Prefijo de una cadena ω es toda cadena no vacía x para la que existe una cadena u tal que ω=xu
	b. Las cadenas que acepta la gramática siempre van a empezar por b. Además el lenguaje generado por la gramática es “no es estructurado por frases”.	Incorrecto
	c. Las cadenas ω que acepta la gramática siempre van a empezar por a. Además el lenguaje generado por la gramática es estructurado por frases
	d. Cualquier cadena ω generada por la gramática contiene una subcadena no vacía donde algunas veces el número de letras a es igual al número de letras b.	Correcto: Correcto: Las cadenas ω van a empezar por a. El lenguaje generado por la gramática es estructurado por frases. Solo algunas cadenas generadas contiene igual número de a´s que de b´s.

Las gramáticas cuyas reglas son de la forma A ---> aB o bien A ---> a, donde A y B son variables, y a es un caracter terminal. A estas gramáticas se les llama regulares.

Parcialmente correcto

Puntos para este envío: 0.5/1.

Question6

Puntos: 1

En una Gramática Regular, un componente de la Cuadrupla que la compone, es el Alfabeto. Este esta caracterizado como:

Seleccione una respuesta.

	a. Un alfabeto infinito y no vacío de símbolos terminales
	b. Un alfabeto inicializado con lambda como cadena válida
	c. Un alfabeto regular (o sea de tipo 3 según Chomsky)
	d. Un alfabeto no vacío de símbolos terminales	Correcto

Una gramática regular G es una cuádrupla G = (E, N, S, P), donde:

E : alfabeto (no vacío) de símbolos terminales

Correcto

Puntos para este envío: 1/1.

1

Puntos: 1

Respecto a la relación entre un AF y un AP cuál afirmación es cierta:

Seleccione una respuesta.

	a. Los AF y los AP tienen la misma capacidad de memoria
	b. Un AP es infinito por su capacidad de memoria. Un AF es finito por su número de estados.
	c. Todo lenguaje aceptado por un AF es también aceptado por un AP	Correcto: Este resultado debe quedar intuitivamente claro, puesto que los AP son una extensión de los AF.
	d. Las gramáticas que generan los lenguajes que pueden representar estos autómatas o máquinas, son las GLC

En los AP también es posible aplicar métodos de combinación modular de autómatas, como se hizo con los autómatas finitos. En particular, es posible obtener AP que acepten la unión y concatenación de los lenguajes aceptados por dos AP dados.

Correcto

Puntos para este envío: 1/1.

Question2

Puntos: 1

Los AP tienen ciertos comportamientos y asociaciones con los AF.

Seleccione las afirmaciones válidas:

Seleccione al menos una respuesta.

	a. Los AP son una extensión de los AF	Correcto
	b. Si se quiere meter cadenas a una pila, puede hacerse con una operación tipo “pop”
	c. Los autómatas de pila aceptan exactamente los LLC. Por lo que: Si M es un AP, entonces L(M) es un LLC	Correcto: Si L es un LLC, entonces hay un AP M tal que L(M) = L
	d. Los AP son una extensión de los AF	Correcto

Correcto

Puntos para este envío: 1/1.

Question3

Puntos: 1

Cuando las gramáticas son demasiado extensas y generan árboles de derivación grandes, se suele usar:

Seleccione una respuesta.

	a. Producciones de tipo GIC con un solo nodo terminal
	b. Formas canónicas que restrinjan los tipos de producciones que pueden utilizarse.	Correcto
	c. Formas de LIC
	d. Formas de Greibach

La definición de una gramática independiente del contexto es demasiado amplia, y por lo tanto, es deseable establecer una forma canónica que restrinja los tipos de producciones que pueden utilizarse.

Correcto

Puntos para este envío: 1/1.

Question4

Puntos: 1

Del diseño y naturaleza de los autómatas de pila (PDA), es válido afirmar:

Seleccione una respuesta.

	a. Un autómata de pila no puede hacer las funciones de "contador" ya que sus recorridos varían en la cinta y lo que le importa a esta automatización es el estado final y la salida del dato.
	b. Para poder simular un autómata de Pila se debe tener en cuenta: Las columnas de una traza de ejecución para un AP son: el estado en que se encuentra el autómata, lo que ha leido hasta el momento o estado actual al inicio de la simulación, y el contenido de la memoria al final del recorrido.
	c. Un Autómata de Pila al igual que una Máquina de Turing o un Autómata Finito, su definición básica es de naturaleza no determinista
	d. A la hora de diseñar un AP tenemos que repartir lo que requiere ser “recordado” entre los estados y la pila. Distintos diseños para un mismo problema pueden tomar decisiones diferentes en cuanto a que recuerda cada cual	Respuesta Correcta: Aunque en el caso de los AP no hay metodologías tan generalmente aplicables como era el caso de los autómatas finitos, siguen siendo válidas las ideas básicas del diseño sistemático, en particular establecer claramente qué es lo que “recuerda” cada estado del AP antes de ponerse a trazar transiciones a diestra y siniestra.

A la hora de diseñar un AP tenemos que repartir lo que requiere ser “recordado” entre los estados y la pila. Distintos diseños para un mismo problema pueden tomar decisiones diferentes en cuanto a que recuerda cada cual.

Correcto

Puntos para este envío: 1/1.

Question5

Puntos: 1

Acerca del funcionamiento de un Autómata de Pila, cuál de las siguientes operaciones o comportamientosNO las hace este autómata.

Seleccione una respuesta.

	a. La pila no tiene límite en sus extremos. A diferencia de las MT que son cerradas por la izquierda.
	b. Una de las condiciones para que una palabra de entrada sea aceptada en un AP la pila debe estar vacía.
	c. Al igual que los AF, los AP tienen estados finales, que permiten distinguir cuando una palabra de entrada es aceptada
	d. En la Pila una transición de un estado a otro Arroja la información de lo que sale de la pila (tope), no de lo que entra ya que el avance es progresivo hacia adelante y no hacia atrás.	Correcto: Esta afirmación es falsa ya que en los AP las transiciones de un estado a otro indican, además de los caracteres que se consumen de la entrada, también lo que se saca del tope de la pila, así como también lo que se mete a la pila.

Para verificar el funcionamiento del autómata, podemos simular su ejecución, listando las situaciones sucesivas en que se encuentra, mediante una tabla que llamaremos “traza de ejecución”. Las columnas de una traza de ejecución para un AP son: el estado en que se encuentra el autómata, lo que falta por leer de la palabra de entrada, y el contenido de la pila

Correcto

Puntos para este envío: 1/1.

Question6

Puntos: 1

Para eL siguiente árbol de derivación identifique las operaciones correctas sobre el mismo:

Seleccione al menos una respuesta.

	a. La gramática que lo genera es: S --> SbS | ScS | a	Correcto
	b. La gramática que lo genera es: S -->SaS | SbS | Sc | a
	c. La derivación de la cadena {abaca} es: S --> SbS --> SbScS ---> SbSca ---> Sbaca ---> abaca	Correcto
	d. La derivación de la cadena {abaca} es: S ---> ScS ---> SbScS ---> abScS ---> abacS ---> abaca

Correcto

Puntos para este envío: 1/1.

Question7

Puntos: 1

Identifique los aspectos que se deben tener para garantizar el determinismo en un Autómata de pila finito determinista (AFPD).

Tenga en cuenta además de los componentes (tupla) de la pila que::

f: es la función de transición:

e: es una transición dada espontanea.

Seleccione al menos una respuesta.

	a. Las transiciones lambda en un AFPD permiten que el autómata cambie el contenido de la pila, sin procesar (o consumir) símbolos sobre la cinta de entrada.	Correcto
	b. El determinismo se da cuando no hay alternativas de movimiento para el mismo estado, usando la misma entrada y el mismo símbolo de pila.	Correcto
	c. Las operaciones: f(q,a,s)y f(q,e,s) con a ∑ ,, q Q y s (pertenecen) al alfabeto de la pila y no pueden estar simultáneamente definidos o declarados.
	d. La definición de la función de transición (f) requiere que haya por lo menos un símbolo en la pila. No se permiten operaciones con la pila vacía.

Parcialmente correcto

Puntos para este envío: 0.5/1.

Question8

Puntos: 1

Si ∑ es un alfabeto, se le llama ∑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
	b. ∑+ = Conjunto de todas las cadenas positivas excepto la vacía
	c. ∑0 = {lambda} Conjunto cuyo único elemento es la palabra vacía.	Correcto
	d. ∑0 = Conjunto de todas las cadenas sobre el alfabeto ∑ excepto la vacía.

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.

Question9

Puntos: 1

Sea un autómata (finito o de pila) M y una cadena x ∈ L(M). Si el autómata lee la cadena x, ¿llegará necesariamente a un estado de aceptación?

Seleccione una respuesta.

	a. Si, si M es un autómata finito.
	b. No todas las veces, dado que puede tratarse de un autómata no determinista.	Correcto
	c. Sí, siempre.
	d. Nunca, Queda en un bucle ya que solo recorre un símbolo.

Correcto

Puntos para este envío: 1/1.

Question10

Puntos: 1

Considere la gramática G = {S → aS | aA | a , A → aA | bS } ¿Cuál es la longitud de las cadenas que puede generar y cuáles son esas cadenas, identifíquelas?

Seleccione una respuesta.

	a. 5 y son {Ø, a, aa, ab, ba }
	b. 7 y son {a,aa,aaa,aaaa, abaa, aaba, abab}	Correcto: Son 7 cadenas: {a,aa,aaa,aaaa, abaa, aaba, abab}
	c. 6 y son {a, aa, ab, ba, bb, aba }
	d. 10 y son {Ø, a, aa, ab, ba, bb, aba, abab, bbb, b }

Correcto

Puntos para este envío: 1/1.

1

Puntos: 1

Considere la gramática: S→ 0S, S→ 1S, S→ S0, S→ λ. Indique cuáles de las

siguientes afirmaciones son verdaderas

Seleccione al menos una respuesta.

	a. Las cadenas {0101, 1001] no son parte del lenguaje que genera
	b. La regla S→ S0 es innecesaria	Correcto
	c. La gramática es equivalente a S→0S, S→ 1S, S→ λ	Correcto
	d. Existen derivaciones distintas que generan cadenas idénticas

Parcialmente correcto

Puntos para este envío: 0.7/1.

Question2

Puntos: 1

Si a un Autómata se le adiciona un almacenamiento auxiliar, se está construyendo entonces:

Seleccione una respuesta.

	a. Una Turing Machine (TM)
	b. Un Autómata No determinístico pero Finito
	c. Un Pushdown Automaton (PA)	Correcto
	d. Un Autómata Determinístico Finito.

Añadir al AF un almacenamiento auxiliar, que llamaremos pila, donde se podrían ir depositando caracter por caracter cadenas arbitrariamente grandes, es el primer paso a la construcción de un AP a partir de un simple AF.

Correcto

Puntos para este envío: 1/1.

Question3

Puntos: 1

Se propone la siguiente GLC (Gramática Libre de Contexto) para que genere el lenguaje de los palíndromos en el alfabeto ∑ = {a,b}

G = S → aSa | bSb | a | b | lambda

Dada esa gramática, determine cuáles reglas corresponden a los palíndromos generados.

Seleccione al menos una respuesta.

	a. S → a (Palíndromos con símbolos pares)	Incorrecto: No se generan esos palíndromos.
	b. S → a | S → b (Palíndromos con símbolos impares)	Correcto: Al realizar el árbol de derivación y el desarrollo de la gramática, las reglas que llevan a crear palíndromos impares son: S → a produce la cadena ω = baaab (impar) y S → b produce la cadena ω = babab (impar) y S → lambda produce la cadena ω = baab (par).
	c. S → b (Palíndromos con símbolos pares)	Incorrecto: No se generan esos palíndromos
	d. S → lambda ( Palíndromos con símbolos pares )	Correcto: Al realizar el árbol de derivación y el desarrollo de la gramática, las reglas que llevan a crear palíndromos impares son: S → a produce la cadena ω = baaab (impar) y S → b produce la cadena ω = babab (impar) y S → lambda produce la cadena ω = baab (par).

Correcto

Puntos para este envío: 1/1.

Question4

Puntos: 1

Dada la siguiente gramática.

Genera le lenguaje {aibjci+j | i+j>0}.

S ---> aAc |ac | bBc | bc ; A ---> aAc | ac |bBc | bc; B ---> bBc | bc

Identifique que producciones fueron necesarias para generar la cadena válida {aabbbccccc}

Seleccione una respuesta.

	a. S --->aAc ; A--->bBc ; B ---> bc
	b. S --->aAc ; A--->aAc | bBc ; B ---> bc
	c. S --->aAc ; A--->aAc | bBc ; B ---> bBc | bc	Correcto
	d. S --->aAc ; A--->aAc | aAc | bBc ; B ---> bBc | bc

Correcto

Puntos para este envío: 1/1.

Question5

Puntos: 1

Dado el siguiente árbol de derivación, identifique las apreciaciones válidas cuando se analiza su comportamiento y diseño:

Seleccione al menos una respuesta.

	a. La gramática está representada como G = { S --->lambda | aS}
	b. El árbol representa las cadenas que inician en dos a”s seguida de una o más a”s de un lenguaje regular
	c. La gramática está representada como: G = { S -lambda | Sa} y el lenguaje generado puede representarse con la expresión regular a*	Correcto: Es una Gramática lineal por la izquierda. La ER es la que representa el lenguaje descrito.
	d. El árbol representa una gramática lineal por la izquierda, que genera el lenguaje L ={lambda, a,aa,aaa,…}	Correcto: Es una Gramática lineal por la izquierda. La ER es la que representa el lenguaje descrito

Correcto

Puntos para este envío: 1/1.

Question6

Puntos: 1

El lenguaje x (potencia m) y (potencia n) z (potencia p), donde m, n y p son enteros no negativos tales que m+n=p, es:

Seleccione una respuesta.

	a. Independiente del contexto no determinista (en sentido estricto)
	b. Estructurado por frases (en sentido estricto).
	c. Independiente del contexto determinista (en sentido estricto)	Correcto: hay que construir el autómata, teniendo en cuenta que sea determinista
	d. Regular

Correcto

Puntos para este envío: 1/1.

Question7

Puntos: 1

La concatenación de dos lenguajes del alfabeto Σ es un subconjunto de:

Seleccione una respuesta.

	a. Σ∪Σ
	b. Σ×Σ
	c. Σ∗×Σ∗
	d. (Σ*)*	Correcto: (Σ*)*=Σ*

La concatenación de dos lenguajes es el lenguaje que resulta al concatenar las respectivas cadenas (la concatenación de dos cadenas es una nueva cadena) y por tanto pertenece a Σ*. Σ∪Σ=Σ ; Σ×Σ es el conjunto de pares ordenados formados por dos símbolos de Σ, y Σ*×Σ* es el conjunto de pares ordenados formados por dos cadenas de Σ*.

Correcto

Puntos para este envío: 1/1.

Question8

Puntos: 1

Dada la gramática S → aS; S→ aSbS; S→ λ. Indique cuál de las siguientes afirmaciones es falsa:

Seleccione una respuesta.

	a. Para cualquier prefijo de una cadena generada por la gramática se verifica que el número de letras a es mayor o igual al número de letras b. Prefijo de una cadena w es toda cadena no vacía x para la que existe una cadena u tal que w = xu
	b. Cualquier cadena generada por la gramática contiene una subcadena no vacía donde el número de letras a es igual al número de letras b	Esta es la opción falsa. La cadena a que en efecto es aceptada , generada por la gramática, no cumple esta condición
	c. El lenguaje generado por la gramática es estructurado por frases
	d. La cadena {b} es rechazada

Correcto

Puntos para este envío: 1/1.

Question9

Puntos: 1

Una gramática independiente del contexto (GIC) genera un lenguaje independiente del contexto (LIC), lo que indica que hay LIC que no son lenguajes regulares y por lo tanto:

Seleccione una respuesta.

	a. El conjunto de los lenguajes regulares contiene al conjunto de los LIC.
	b. El conjunto de los LIC contiene al conjunto de los lenguajes regulares.	Correcto: Los lenguajes generados por una GIC son llamados Lenguajes Independientes del Contexto (LIC).
	c. El conjunto de los lenguajes regulares y el conjunto de los LIC son conjuntos independientes.
	d. El conjunto de los lenguajes regulares contiene al conjunto de las GIC.

Una gramática independiente del contexto (GIC) es una cuádrupla G=(N, Σ, S, P), donde: N: es una colección finita (no vacía) de símbolos no terminales. Σ: es un alfabeto. S: es un no terminal llamado símbolo inicial. P: un conjunto de producciones tal que P⊆ N (N∪ Σ)*. Los lenguajes generados por una GIC son llamados Lenguajes Independientes del Contexto (LIC)

Correcto

Puntos para este envío: 1/1.

Question10

Puntos: 1

Dado un alfabeto, el número máximo de estados de un autómata finito determinista:

Seleccione una respuesta.

	a. Depende del alfabeto sobre el que está definido
	b. No hay número máximo	Correcto
	c. Puede ser infinito
	d. Es directamente proporcional al número de cadenas del lenguaje que reconoce

Correcto

Puntos para este envío: 1/1.

Question11

Puntos: 1

Indique cuál de las siguientes afirmaciones es verdadera

Seleccione una respuesta.

	a. Los autómatas finitos tienen un número finito de estados	Correcto
	b. Los autómatas finitos sólo pueden aceptar lenguajes finitos
	c. Las máquinas de Turing y los autómatas de pila son autómatas finitos
	d. Los autómatas de pila reconocen lenguajes generados por gramáticas de tipo 3

Correcto

Puntos para este envío: 1/1.

Question12

Puntos: 1

Si una gramática independiente del contexto tiene todas sus reglas de la forma: A → wB, o bien de la forma A → w, donde w es una cadena de uno o más terminales, y A y Bson símbolos no terminales, entonces el lenguaje generado por dicha gramática es:

Seleccione una respuesta.

	a. Decidible
	b. Estructurado por frases y no independiente del contexto
	c. Independiente del contexto no regular	Incorrecto
	d. Regular

Incorrecto

Puntos para este envío: 0/1.

Question13

Puntos: 1

Considere la gramática S →Rc, R → aRbR, R → λ. Siendo w una cadena cualquiera generada por dicha gramática, indique cuál de las siguientes afirmaciones es falsa:

Seleccione una respuesta.

	a. Las cadenas {abc, c} son aceptadas
	b. El número de letras a es mayor o igual al de letras b en todo prefijo de w. Prefijo de una cadena w es toda cadena no vacía x para la que existe una cadena u tal que w = xu.	Esto es verdadero
	c. w = xc | x ∈ (a∪ b)*
	d. El número de letras a es igual al de letras b en w

Incorrecto

Puntos para este envío: 0/1.

Question14

Puntos: 1

Sea M un autómata de pila. Indique cuál de las siguientes afirmaciones es falsa:

Seleccione una respuesta.

	a. Si M es un autómata de pila determinista que siempre llega a los estados de aceptación con pila vacía, entonces L(M) no puede ser aceptado por un autómata de pila no determinista	Esta afirmación es falsa ya que para todo lenguaje reconocido por un autómata de pila determinista existe un autómata de pila determinista que lo reconoce y acepta.
	b. Sea L={a, ba}. L puede ser aceptado por un autómata de pila determinista que siempre llegue a los estados de aceptación con pila vacía
	c. Sea L={a, ab}. L puede ser aceptado por un autómata de pila determinista que siempre llegue a los estados de aceptación con pila vacía
	d. Un autómata de Pila reconoce lenguajes que sean generados por gramáticas de tipo2.

Correcto

Puntos para este envío: 1/1.

Question15

Puntos: 1

Cual de las siguientes afirmaciones es VERDADERA

Seleccione una respuesta.

	a. Los lenguajes generados por una Gramática Independiente del Contexto son llamados Lenguajes Regulares
	b. En los arboles de derivación, los nodos raíces siempre derivan en dos ramas.
	c. En un árbol de derivación, una gramática es ambigua, cuando hay dos o más árboles de derivación distintos para una misma cadena.	Correcto. En este caso es ambigua por cuanto puede tener varias soluciones
	d. En un árbol de derivación cada nodo solamente puede tener otro hijo nodo. De lo contrario se formaría otro nodo.

Es posible probar que cualquier palabra que sea aceptada por el AFD M, puede ser generada por la gramática regular G. Esto significa que L(G) = L(M).

Correcto

Puntos para este envío: 1/1.

1

Puntos: 1

Cuando se transmite información, las variables a evaluar, medir, seguir y monitorear son:

Seleccione al menos una respuesta.

	a. Redundancia	Incorrecto
	b. Nivel de ruido	Incorrecto: o es variable de datos a transmitir
	c. La velocidad que se mantenga.	Correcto: Cuando se transmite información, las variables más importantes son: la velocidad y la veracidad (libre de errores).
	d. La veracidad de los datos en todo su sentido.	Correcto: Cuando se transmite información, las variables más importantes son: la velocidad y la veracidad (libre de errores).

Correcto

Puntos para este envío: 1/1.

Question2

Puntos: 1

En el campo de la complejidad algorítmica (problemas de algoritmos y de lógica) se presenta la “Decibilidad de teorías lógicas”. Una técnica para resolver problemas de este tipo es reducir un problema a otro para comprobar si tiene o no solución efectiva. Al hacer uso de esta estrategia en el caso que la respuesta sea negativa, se da:

Seleccione una respuesta.

	a. Si se reduce de forma efectiva un problema sin solución efectiva a otro problema, se determina la clase de complejidad siendo esta la solución
	b. Si se reduce de forma efectiva un problema sin solución efectiva a otro problema, se convierte en un problema parcialmente soluble (existe una Máquina de Turing que resuelve el problema, pero puede no parar)	Incorrecto: si se reduce de forma efectiva un problema sin solución efectiva a otro problema (mediante una función calculable), entonces este nuevo problema tampoco tendrá solución efectiva
	c. Si se reduce de forma efectiva un problema sin solución efectiva a otro problema, entonces es probable que solo se solucione usando una Máquina de Turing (MT).
	d. Si se reduce de forma efectiva un problema sin solución efectiva a otro problema, entonces este nuevo problema tampoco tendrá solución efectiva.

Incorrecto

Puntos para este envío: 0/1.

Question3

Puntos: 1

Cuáles diferencias entre una computadora Real y una máquina de Turing (MT) son verdaderas:

Seleccione al menos una respuesta.

	a. En una computadora, el número de estados viene representado por el contenido de la memoria.	Correcto
	b. En una MT el orden de ejecución de las instrucciones no está definido.
	c. En cuanto al orden de ejecución de las instrucciones, En la estructura Von Neumann el secuenciamiento lo marca el orden de colocación de las instrucciones en la memoria interna y viene asegurado por el contador de programa.	Correcto: En Una máquina de Turing, el orden de ejecución de las instrucciones si está definido, lo marca en todo instante el estado de la máquina y el carácter de la cinta apuntado, que son los dos datos que determinan la quíntupla que ha de ser ejecutada.
	d. En una MT el nº de estados depende del algoritmo.	Correcto

Correcto

Puntos para este envío: 1/1.

Question4

Puntos: 1

Un problema de decisión (PD) es aquel formulado por una pregunta (referida a alguna propiedad) que requiere una respuesta de tipo “si/no”. Para la Teoría de Lenguajes, un problema de decisión es “insoluble” cuando:

Seleccione al menos una respuesta.

	a. Si no existe un procedimiento efectivo para determinar si la propiedad es verdadera (no existe una Máquina de Turing MT).	Correcto
	b. Si no existe un algoritmo total para determinar si la propiedad y objetivo del problema es verdadera.	Correcto
	c. Si no se logra representar con un diagrama de Moore el problema.
	d. Existe un procedimiento definido que determina la ambigüedad del problema

Correcto

Puntos para este envío: 1/1.

Question5

Puntos: 1

De la teoría de la codificación se puede decir: (señale las apreciaciones verdaderas):

Seleccione al menos una respuesta.

	a. Los algoritmos matemáticos son métodos para lograr que la información se adapte mejor a las condiciones de las transmisiones.	Correcto
	b. La codificación es una parte de la teoría de información.	Correcto
	c. La codificación de canales con ruido se trata únicamente con la codificación de canal.
	d. La veracidad se consigue introduciendo una redundancia

Parcialmente correcto

Puntos para este envío: 0.7/1.

Question6

Puntos: 1

Analice la codificación de la siguiente Máquina: Si lee 0101 (de izquierda a derecha), la salida correspondiente es:

Seleccione una respuesta.

	a. 0110
	b. 0111	Correcto: La salida correspondiente es 0111 si se tiene en cuenta que en las transiciones, el primer carácter es el que lee y el segundo es el que escribe.
	c. 0011
	d. 0101

Correcto

Puntos para este envío: 1/1.

1

Puntos: 1

De las siguientes características marque dos de las que corresponden con la cinta de una Máquina de Turing

Seleccione al menos una respuesta.

	a. Cinta Infinita hacia la izquierda
	b. Cinta Finita hacia la derecha, por que al extremo izquierdo siempre esta un topeo carácter blanco.
	c. Se puede escribir en ella	Correcto: En la MT la cabeza lectora es de lectura y escritura, por lo que la cinta puede ser modificada en curso de ejecución. Además, en la MT la cabeza se mueve bidireccionalmente (izquierda y derecha), por lo que puede pasar repetidas veces sobre un mismo segmento de la cinta.
	d. Puede contener un caracter por celda	Correcto: En la MT la cabeza lectora es de lectura y escritura, por lo que la cinta puede ser modificada en curso de ejecución. Además, en la MT la cabeza se mueve bidireccionalmente (izquierda y derecha), por lo que puede pasar repetidas veces sobre un mismo segmento de la cinta

La máquina de Turing (abreviado MT) tiene, como los autómatas finitos, un control finito, una cabeza lectora y una cinta donde puede haber caracteres, y donde eventualmente viene la palabra de entrada. La cinta es de longitud infinita hacia la derecha, hacia donde se extiende indefinidamente, llenándose los espacios con el caracter blanco

Correcto

Puntos para este envío: 1/1.

Question2

Puntos: 1

Los problemas indecidibles, son también parte del estudio de Autómatas y lenguajes Formales. La indecibilidad de estos problemas lleva a ratificar afirmaciones que han sido demostradas mediante algoritmos complejos computables que concluyen en afirmaciones como:

Seleccione una respuesta.

	a. Hay infinitos problemas para los que no se va a tener una MT que los resuelva (ni siquiera los reconozca).	Correcto
	b. Las MT por ser la máquina abstracta más poderosa, soluciona cualquier problema que en teoría sea indecidible.
	c. Decidir si un lenguaje que se genera es vacío o no, es un problema que sí tiene solución por una MT.
	d. Con un computador real, se puede determinar con certeza cualquier problema en el sentido si es decidible o no.

Una MT que los resuelva (ni siquiera los reconozca). También se ha formulado la tesis de Church-Turing, que determina el límite de los computadores actuales

Correcto

Puntos para este envío: 1/1.

Question3

Puntos: 1

Indique cuál de las siguientes afirmaciones es cierta con referencia a las Máquinas de Turing:

Seleccione al menos una respuesta.

	a. Una máquina de Turing cuyo estado inicial coincida con el estado de parada acepta toda cadena	Correcto
	b. El diseño de las MT básicamente es el de un autómata finito pero un Autómata con mayor poder de reconocimiento y proceso de lenguajes, que tomas y fusiona aspectos de un PDA.
	c. Cualquier lenguaje puede ser reconocido por una máquina de Turing
	d. El diseño de una MT es procedimentalmente sencillo para programar lenguajes de máquinas reales.

Parcialmente correcto

Puntos para este envío: 0.5/1.

Question4

Puntos: 1

Un código convolucional se diseña cuando a partir de registros de desplazamiento lineal.

Los códigos convolucionales, suelen describirse mediante:

Seleccione una respuesta.

	a. Árboles, Trellis y Diagrama de estados.	Correcto
	b. Autómatas finitos (grafos). Máquinas de estados
	c. Autómatas finitos (grafos). Máquinas de estados
	d. Árboles y diagramas de estados

Correcto

Puntos para este envío: 1/1.

Question5

Puntos: 1

Dado los siguientes tres codificadores convolucionales, diseñados para trabajar de forma lineal secuencial redundante:

Se da como entrada el bit “1” en el codificador 1. Haga el recorrido completo hasta llegar a la salida del codificador 3. Los bits de salida codificados finales son:

Tenga en cuenta que a partir del codificador 2, los bits de salida o entrada (según el caso) se deben sobrescribir o reemplazar.

Seleccione una respuesta.

	a. 00
	b. 10
	c. 11
	d. 01	Correcto

Correcto

Puntos para este envío: 1/1.

Question6

Puntos: 1

De los modelos creados para realizar cómputos y desarrollar problemas, es válido afirmar:

Seleccione una respuesta.

	a. Las funciones computables hacen referencia o son iguales a afirmar que son modelos computables.
	b. La MT no es un modelo Computable ya que solo se basa en simulación.
	c. Las llamadas máquinas de Turing no constituyen ni el primero ni el único formalismo para expresar cómputos, pero sí el que más ha perdurado	Correcto
	d. Los modelos propuestos por Hilbert, solucionan cualquier problema "No soluble"

Las llamadas máquinas de Turing no constituyen ni el primero ni el único formalismo para expresar cómputos, pero sí el que más ha perdurado.
Su creador, el matemático inglés Alan Turing (1912-1954) estaba convencido de que no existía un algoritmo para el problema de decisión planteado por Hilbert y su intención era demostrar dicha no existencia.

El modelo en el que se inspiró fue el de una persona real llevando a cabo un cálculo mecánico, por ejemplo una multiplicación de dos grandes números en el sistema decimal.

Correcto

Puntos para este envío: 1/1.

Question7

Puntos: 1

Señale los aspectos de diseño válidos de una Máquina de Turing (MT).

Seleccione al menos una respuesta.

	a. En una Máquina de Turing (MT) que usa una cinta que se extiende infinitamente en una única dirección, generalmente está extendida hacia la derecha.	Correcto
	b. No está permitido realizar ningún movimiento hacia la izquierda a partir de la celda del extremo izquierdo.	Correcto
	c. Una palabra de entrada a reconocer en una MT se escribe símbolo por símbolo en la cinta	Incorrecto: La palabra de entrada en la MT está escrita inicialmente en la cinta, como es habitual en nuestros autómatas, pero iniciando a partir de la segunda posición de la cinta, siendo el primer cuadro un caracter blanco.
	d. La Máquina Universal de Turing no debe ser diseñada para realizar un cálculo específico, sino para procesar cualquier información	Correcto

Correcto

Puntos para este envío: 1/1.

Question8

Puntos: 1

Con referencia alas (MT) Máquinas de Turing, indique cuál afirmación es cierta cuando de reconocer lenguajes se trata:

Seleccione una respuesta.

	a. Una Máquina de Turing (MT) acepta su entrada si, partiendo de la configuración inicial, durante el cómputo alcanza la configuración aceptadora.
	b. Una máquina de Turing (MT) cuyo estado inicial coincida con el estado de parada, acepta toda cadena.	Incorrecto
	c. Cualquier Lenguaje puede ser reconocido por una Máquina de Turing (MT)
	d. Una Máquina de Turing (MT) no puede aceptar el lenguaje de palíndromos, por que entraría en un ciclo repetitivo sin encontrar un estado “Halt”.

Incorrecto

Puntos para este envío: 0/1.

Question9

Puntos: 1

Acerca del tipo de cadenas que puede aceptar una Máquina de Turing, determine cuál afirmación es válida.

Seleccione una respuesta.

	a. Una máquina de Turing cuyo estado inicial coincida con el estado de parada acepta toda cadena	Correcto: Decimos que en la MT se llega al “final de un cálculo” cuando se alcanza un estado especial llamado halt en el control finito, como resultado de una transición. Representaremos al halt por “h”
	b. Cuando se desea que una MT no acepte una palabra, simplemente se debe configurar para que llegue a un estado halt de parada o stop.
	c. Es posible que un lenguaje sea estructurado por frases pero no exista ninguna máquina de Turing que se detenga exclusivamente cuando las cadenas escritas en su cinta pertenezcan al lenguaje
	d. Por ser una máquina tan simple pero a la vez tan potente, resulta fácil que cualquier lenguaje puede ser reconocido por una máquina de Turing

Al diseñar una MT que acepte un cierto lenguaje, en realidad diseñamos el autómata finito que controla la cabeza y la cinta, el cual es un autómata con salida.

Correcto

Puntos para este envío: 1/1.

Question10

Puntos: 1

Un ascensor sin memoria de un edificio de cuatro plantas puede describirse:

Seleccione una respuesta.

	a. Mediante un autómata de pila, pero no mediante un autómata finito
	b. Mediante una máquina de Turing, pero no mediante un autómata de pila
	c. No es un problema soluble. Es un problema de decisión
	d. Mediante un autómata finito	Correcto: Al no tener memoria, el ascensor es una máquina que experimenta una transición de estado como función exclusiva del estado en que se encuentra y el evento que recibe (botón pulsado por un usuario).

Al no tener memoria, el ascensor es una máquina que experimenta una transición de estado como función exclusiva del estado en que se encuentra y el evento que recibe (botón pulsado por un usuario).

Correcto

Puntos para este envío: 1/1.