AUTOMATAS Y LENGUAJES FORMALES CURSO COMPLETO

1

Puntos: 1

Luego de graduarse en matemáticas puras a sus 16 años en 1928, Turing descubrió los trabajos de Albert Einstein. Luego en 1933 inicia sus estudios e los “principios lógicos matemáticos” apoyado de:

Seleccione una respuesta.

	a. Godfrey y Church	Incorrecto: Recibió las enseñanzas de Godfrey Harold Hardy, un respetado matemático que lo encaminó al estudio de las ciencias exactas.
	b. Godel
	c. Bertrand Russell
	d. Neumann

Biografía de Alan Turing

Incorrecto

Puntos para este envío: 0/1.

Question2

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. Procedimientos para evaluar decisiones lógicas de una máquina.
	b. Prueba de error que determina cuando un problema tiene solución o no.
	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.

Question3

Puntos: 1

Grandes fueron sus aportes a la ciencia y la matemática y en muchas áreas de cocimiento ahondó. Pero el principal interrogante por el que se conoce Alan Turing fue:

Seleccione una respuesta.

	a. El hecho de que: debe existir al menos en principio algún método definido, o proceso mediante el cual toda cuestión matemática pueda ser demostrada?
	b. La demostración de toda cuestión matemática no debe obedecer a la lógica fundamental y no necesariamente debe comprobarse para que un problema tenga solución.
	c. El hecho de que: debe existir al menos y en principio una solución única para cualquier problema matemático.	Incorrecto: era el hecho de que: debe existir al menos en principio algún método definido, o proceso mediante el cual toda cuestión matemática pueda ser demostrada?
	d. Un problema matemático tiene “finitas soluciones”. Si son infinitas es porque el problema puede ser insoluble.

Biografía de Alan Turing

Incorrecto

Puntos para este envío: 0/1.

Question4

Puntos: 1

Turing era ateo. Reafirmó sus conceptos superficiales y concretos en los que todos los fenómenos incluyendo el funcionamiento del cerebro humano, deben ser materialistas. Pese a ello siguió creyendo en la supervivencia del espíritu después de la muerte. Estas posiciones fueron dadas a raíz de:

Seleccione una respuesta.

	a. A empezar estudios del cerebro humano y descubrir que podría asociarse al funcionamiento de una máquina mecánica y que no podría haber sido creación de Dios.
	b. Al ver el horror de la segunda erra mundial en la que participó como agente encubierto descifrando códigos e interceptando comunicaciones del ejército Alemán.
	c. Dada la muerte de Christopher Morcom, quién fue el primer amor. Morcom murió repentinamente el 13 de febrero de 1930 .	Correcto: Morcom murió muy joven de tuberculosis bovina al beber leche contaminada. Él fue quien a motivación para seguir con sus estudios, y entra en un vital periodo de riqueza intelectual.
	d. En 1928, con dieciséis años, al descubrir e interpretar los trabajos de Albert Einstein

Biografía de Alan Turing

Correcto

Puntos para este envío: 1/1.

Question5

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

Biografía de Alan Turing

Incorrecto

Puntos para este envío: 0/1.

Question6

Puntos: 1

Para comprender y empezar a dar respuesta al Entscheidungsproblem (en castellano: problema de decisión), Alan Turing analizó aspectos como:

Seleccione al menos una respuesta.

	a. Abordando la definición del concepto "método", y para ello analizó que era lo que hacía una persona para transformar un proceso metódico, y buscar una forma de hacer esto mecánicamente
	b. Asoció el proceso de forma mecánica en la que se podían transformar operaciones elementales previamente definidas en símbolos y estos posteriormente escribirlos en una cinta
	c. Asoció el problema llevándolo a definir un conjunto de instrucciones de forma metódica para ser ejecutadas de manera mecánica. Es decir abordó el concepto de “Máquina de Turing” en la que hay un conjunto de posibilidades infinitas en la que cada una se corresponde a un “método claro y definido” o a un “algoritmo”.	Parcialmente correcto: En Agosto de 1936 presenta el concepto final de la Maquina de Turing, y se convierte en el fundamento de las teorías modernas para la programación de máquinas electrónicas. Su trabajo aporta un concepto práctico de gran significancia: la idea de la Maquina de Turing Universal. El concepto de "LA MAQUINA DE TURING" se conoce también como "LA FORMULA" o "LA ECUACIÓN"
	d. Alan Turing lo que realmente analizó y logró definir fue un algoritmo.

Biografía de Ala Turing

Parcialmente correcto

Puntos para este envío: 0.3/1.

1

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. { α1 , α2 ,..... α n } Es un ejemplo de alfabeto
	b. 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
	c. Por símbolo, se está haciendo referencia a un solo carácter.	Incorrecto: Por símbolo no se está haciendo referencia a un sólo carácter. Los símbolos pueden ser nombres
	d. 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}.

Parcialmente correcto

Puntos para este envío: 0.5/1.

Question2

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. 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.	Correcto: La minimización se basa en el tratamiento de estados "obtener el menor número de ellos" de forma equivalente.
	b. Un autómata se puede minimizar siempre y cuando el autómata dado no acepte cadenas vacías.
	c. 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
	d. En la minimización de autómatas, el número de estados o de relaciones debe ser equivalente en cantidad inferior al dado.

Correcto

Puntos para este envío: 1/1.

Question3

Puntos: 1

Acerca de los autómatas finitos no deterministas (AFND), cuáles apreciaciones son verdaderas cuando se analiza su comportamiento para aceptar lenguajes:

Seleccione al menos una respuesta.

	a. Un autómata finito no determinista (AFND) se puede convertir a un AFD y solo será válido si aceptan el mismo lenguaje.	Correcto: Corresponde a la condición de determinismo.
	b. Un autómata finito no determinista (AFND) acepta una cadena cuando es posible que su análisis deje a la máquina en un estado de aceptación.
	c. Un autómata finito no determinista (AFND) solo puede utilizarse para aceptar lenguajes finitos.
	d. Nunca se puede afirmar con seguridad que un autómata finito no determinista (AFND) acepta una cadena.

Parcialmente correcto

Puntos para este envío: 0.5/1.

Question4

Puntos: 1

Sea el vocabulario {a,b} y la expresión regular aa*bb* Indique cuales cadenas que se relacionan a continuación son válidas para esa ER

Seleccione una respuesta.

	a. {ab, aab, aab, a, aa,bb}
	b. {a, b, ab, ba, aab, bba, aaab}
	c. {ab, aab, aaab, abbb, abb, aa,bb}	Correcto: El Lenguaje que se describe es L={cadenas que comienzan por una a y continuan con varias o ninguna a, y siguen con b y continuan con varias o ninguna b}
	d. {ba, ab, b, a}

Correcto

Puntos para este envío: 1/1.

Question5

Puntos: 1

Del tratado y temática de Autómatas, los principales objetivos de las ciencias de la computación es:

Seleccione al menos una respuesta.

	a. La solución de problemas por medio de un computador.
	b. Proporcionar mecanismos para analizar algoritmos, construir y expresar programas
	c. Reducir problemas en otros más pequeños.
	d. Traducir lenguajes de máquina a programas escritos en lenguajes de alto nivel.	Incorrecto: estas son tareas de máquina que surgen del análisis formulación de tratados como los de los algoritmos

Incorrecto

Puntos para este envío: 0/1.

Question6

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 conjunto finito de estados.
	b. El estado inicial.
	c. El alfabeto de entrada
	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.

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.

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.

1

Puntos: 1

Dado el alfabeto ∑= {a,b}, identifique cuál afirmación es falsa.

Seleccione una respuesta.

	a. La expresión regular b*a*b* representa al lenguaje de las cadenas que pueden o no tener “a”
	b. La expresión regular b*(ab*ab*)* representa al lenguaje de las cadenas con un número par de letras a
	c. La expresión regular b*ab* (ab*ab*)* representa al lenguaje de las cadenas con un número impar de letras a
	d. La expresión regular (b*ab*ab*a) * representa al lenguaje de las cadenas con un número múltiplo de 3 de letras “a”	Esta afirmación (ER) es errada para las cadenas que dice generar.

Correcto

Puntos para este envío: 1/1.

Question2

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. 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.
	c. 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”.
	d. 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	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.

Correcto

Puntos para este envío: 1/1.

Question3

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. Los autómatas de pila aceptan exactamente los LLC (Lenguajes Libres de Contexto).	Correcto
	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. Las producciones son de la forma: A - aa Dado que hay un carácter de lectura y uno de escritura

Correcto

Puntos para este envío: 1/1.

Question4

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 no vacío de símbolos terminales	Correcto
	d. Un alfabeto regular (o sea de tipo 3 según Chomsky)

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.

Question5

Puntos: 1

Que aspectos son válidos cuando se analiza el funcionamiento de los autómatas de pila (AP).

Seleccione al menos una respuesta.

	a. Los APND y los APD no aceptan los mismos lenguajes.
	b. Los autómatas de pilas no tienen metodología tan generalmente aplicable, solo se debe tener una estrategia clara para el manejo de la pila.
	c. Para verificar el funcionamiento del autómata, podemos simular su ejecución listando las situaciones sucesivas en que se encuentran mediante una tabla que llamaremos traza de ejecución.	Correcto
	d. Cuando desarrollamos un autómata de pilas tenemos que repetir lo que quiere ser recordado entre los estados y las pilas.	Correcto

Parcialmente correcto

Puntos para este envío: 0.5/1.

Question6

Puntos: 1

Para u AP, la función de transición también se puede representar mediante un diagrama donde los nodos representan los estados y los arcos transiciones, Dada la siguiente transición como se muestra en la figura, identifique las acciones correctas que haría el movimiento de la pila.

Seleccione una respuesta.

	a. El estado actual es q0. La cabeza lectora apunta al símbolo “lambda”. El recorrido de la pila es de izquierda a derecha. El tope de la pila es X que no se modifica al cambiar al nuevo estado q1 y avanzar la cabeza lectora.
	b. El estado actual es q0. La cabeza lectora apunta al símbolo “a”. El tope de la pila es “a” como primer símbolo a leer que se va a sustituir por lambda al cambiar al nuevo estado q1 y avanzar la cabeza lectora.
	c. El estado actual es q0. La cabeza lectora apunta al símbolo “a”. El tope de la pila es X que se va a sustituir por lambda al cambiar al nuevo estado q1 y avanzar la cabeza lectora.	Correcto
	d. El estado actual es q0. La cabeza lectora apunta al tope X que es donde inicia la lectura del símbolo “a” que entra al pasar al estado q1 y sustituir lambda por X.

Correcto

Puntos para este envío: 1/1.

1

Puntos: 1

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

Seleccione una respuesta.

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

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.

Question2

Puntos: 1

Para que una palabra de entrada sea aceptada en un AP se deben cumplir las condiciones siguientes:

Seleccione al menos una respuesta.

	a. La palabra de entrada se debe haber agotado (consumido totalmente).	Correcto; para que una palabra de entrada sea aceptada en un AP se deben cumplir todas las condiciones siguientes: 1. La palabra de entrada se debe haber agotado (consumido totalmente). 2. El AP se debe encontrar en un estado final. 3. La pila debe estar vacía.
	b. El AP se debe encontrar en un estado final.	Correcto: para que una palabra de entrada sea aceptada en un AP se deben cumplir todas las condiciones siguientes: 1. La palabra de entrada se debe haber agotado (consumido totalmente). 2. El AP se debe encontrar en un estado final. 3. La pila debe estar vacía.
	c. La pila debe estar vacía.	Correcto: la pila debe estar vacía.
	d. La pila debe tener lambda como elemento final.

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 qué recuerda cada cual.

Correcto

Puntos para este envío: 1/1.

Question3

Puntos: 1

Los errores más comunes al diseñar gramáticas (GLC) son:

Seleccione al menos una respuesta.

	a. Que “sobren palabras”	Correcto: esto es, que la gramática genere algunas palabras que no debería generar. En este caso, la gramática seria incorrecta.
	b. Que “falten palabras”,	Correcto esto es, que haya palabras en el lenguaje considerado para lasque no hay ninguna derivación. En este caso, la gramática seria incompleta.
	c. Reutilizar gramáticas y modificarlas para ajustarlas al lenguaje generado	Incorrecto: Es posible hacerlo pero no son errores comunes
	d. Combinar gramáticas

El problema del diseño de GLC consiste en proponer, dado un lenguaje L, una GLC G tal que su lenguaje generado es exactamente L.

Correcto

Puntos para este envío: 1/1.

Question4

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. 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.
	b. 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
	c. 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.	Correcto
	d. 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.

Parcialmente correcto

Puntos para este envío: 0.5/1.

Question5

Puntos: 1

Los AP tienen ciertos comportamientos y asociaciones con los AF.

Seleccione las afirmaciones válidas:

Seleccione al menos una respuesta.

	a. Si se quiere meter cadenas a una pila, puede hacerse con una operación tipo “pop”
	b. 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
	c. Los AP son una extensión de los AF	Correcto
	d. Los AP son una extensión de los AF	Correcto

Correcto

Puntos para este envío: 1/1.

Question6

Puntos: 1

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

Seleccione una respuesta.

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

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.

Question7

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

Correcto

Puntos para este envío: 1/1.

Question8

Puntos: 1

Indique cuál de las siguientes afirmaciones es verdadera:

Seleccione al menos una respuesta.

	a. Cuando se dice que un AFPD (autómata de pila determinista) es más sencillo , se refiere a que es menos potente y no se refiere ala sencillez de su diseño.	Correcto:
	b. Para reconocer un lenguaje regular mediante un autómata de pila el alfabeto de la pila debe contener al menos un símbolo
	c. Para reconocer un lenguaje regular mediante un autómata de pila no es necesario que el alfabeto de la pila contenga ningún símbolo	Correcto: Cualquier lenguaje independiente del contexto puede ser aceptado por un autómata de pila, y todos lenguajes regulares son independientes del contexto.
	d. Con un autómata de pila no puede reconocerse un lenguaje regular

Correcto

Puntos para este envío: 1/1.

Question9

Puntos: 1

En un autómata de pila (AP), la función de transición aplica o interviene a:

Seleccione al menos una respuesta.

	a. A cada símbolo topo de la pila	Correcto
	b. A cada estado	Correcto
	c. A cada movimiento de la pila
	d. A cada símbolo de entrada (Incluyendo la cadena vacía)	Correcto

La función de transición aplica cada estado, cada símbolo de entrada (incluyendo la cadena vacía) y cada símbolo tope de la pila en un conjunto de posibles movimientos. Cada movimiento parte de un estado, un símbolo de la cinta de entrada y un símbolo tope de la pila. El movimiento en sí consiste en un cambio de estado, en la lectura del símbolo de entrada y en la substitución del símbolo tope de la pila por una cadena de símbolos.

Parcialmente correcto

Puntos para este envío: 0.8/1.

Question10

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. 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.
	b. La pila no tiene límite en sus extremos. A diferencia de las MT que son cerradas por la izquierda.
	c. Al igual que los AF, los AP tienen estados finales, que permiten distinguir cuando una palabra de entrada es aceptada
	d. Una de las condiciones para que una palabra de entrada sea aceptada en un AP la pila debe estar vacía.

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.

1

Puntos: 1

Considere la gramática G1 = {S→ aS/ aA/ a, A→ aB/ bS, B→ aB/ bB, C→ aA/ bC}

y G2 = {S→ aS/ aA/ a, A→ bS}. Sean L1 y L2 los lenguajes generados respectivamente por G1 y G2; entonces: (Nota: el símbolo ⊂denota la relación de inclusión estricta):

Seleccione una respuesta.

	a. L1 ⊂ L2
	b. L2 ⊂ L1
	c. L1 = L2	Correcto: Las reglas que implican a los no terminales B y C no generan ninguna cadena.
	d. L1 ≠ L2

Correcto

Puntos para este envío: 1/1.

Question2

Puntos: 1

Desarrolle la siguiente gramática cuyos símbolos terminales son {a,b}

S ---> aAA, A ---> bS, A ---> lambda

Identifique las apreciaciones válidas. Se recomienda desarrollar el árbol de derivación

Seleccione al menos una respuesta.

	a. El autómata más sencillo que Acepta L(G) es un autómata de pila (AP). Una cadena válida sería {abab}
	b. La cadena más sencilla que genera el L(G) es: {aba}
	c. El autómata más sencillo que Acepta L(G) es un autómata finito	Correcto
	d. El lenguaje que genera la gramática es L(G) = a(ba)*	Correcto

Correcto

Puntos para este envío: 1/1.

Question3

Puntos: 1

Dada la siguiente gramática G= (VN= {S, A}, VT= {0,1}, S, P) donde P son las producciones:

Seleccione al menos una respuesta.

	a. S –> 0A –> 0A –> 00A –> 000
	b. S –> 0A –> 00A –> 001S –> 0010 A –> 00100	Correcto: Ambas producciones aplican a la gramática con cadenas válidas como 0100 y 00100
	c. S –> 0A –> 01S –> 010 A –> 0100	Correcto: Ambas producciones aplican a la gramática con cadenas válidas como 0100 y 00100
	d. S –> 0A –> 00A –> 001 A –> 0010

Correcto

Puntos para este envío: 1/1.

Question4

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. Regular	Correcto
	b. Estructurado por frases y no independiente del contexto
	c. Decidible
	d. Independiente del contexto no regular

Correcto

Puntos para este envío: 1/1.

Question5

Puntos: 1

Cual de las siguientes afirmaciones se asocia correctamente al diseño y funcionamiento de los árboles de derivación.

Seleccione una respuesta.

	a. En un árbol de derivación cada nodo solamente puede tener otro hijo nodo
	b. 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.	Respuesta Correcta: Una gramática es “ambigüa” cuando hay dos o más árboles de derivación distintos para una misma cadena
	c. Los lenguajes generados por una Gramática Independiente del Contexto son llamados Lenguajes Regulares
	d. En los árboles de derivación, no es necesario usar nodo raíz

Al derivar una cadena a través de una GIC, el símbolo inicial se sustituye por alguna cadena. Los no terminales se van sustituyendo uno tras otro por otras cadenas hasta que ya no quedan símbolos no terminales, queda una cadena con sólo símbolos terminales. A veces es útil realizar un gráfico de la derivación. Tales gráficos tienen forma de árbol y se llaman “árbol de derivación” o “árbol de análisis”. Para una derivación dada, el símbolo inicial “S” etiqueta la raíz del árbol. El nodo raíz tiene unos nodos hijos para cada símbolo que aparezca en el lado derecho de la producción, usados para reemplazar el símbolo inicial. De igual forma, cada símbolo no terminal tiene unos nodos hijos etiquetados con símbolos del lado derecho de la producción usada para sustituir ese no terminal.

Correcto

Puntos para este envío: 1/1.

Question6

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 un árbol de derivación cada nodo solamente puede tener otro hijo nodo. De lo contrario se formaría otro nodo.
	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 los arboles de derivación, los nodos raíces siempre derivan en dos ramas.

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.

Question7

Puntos: 1

La combinación de autómatas se demostró en los Autómatas Finitos de la Unidad 1 en as que era viable combinar dos Autómatas que generaban el miso lenguaje y obtener otro que genera las mismas cadenas que los autómatas combinados.
Con referencia a los Autómatas de Pila (AP), este tema de combinación tiene aspectos a analizar. identifique cuál es válido para estas operaciones:

Seleccione una respuesta.

	a. Se pueden obtener AP que acepten operaciones de Unión y Concatenación de los lenguajes aceptados por los Autónomas de Pila dados.	Correcto
	b. Solo la operación de Unión de los lenguajes de dos AP es permitida.
	c. Las operaciones de combinar AP solo es viable cuando los dos Autónomas leen el mismo alfabeto.
	d. Un AP se puede combinar con una MT siempre y cuando lean y acepten el mismo lenguaje.

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.

Question8

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 → b (Palíndromos con símbolos pares)
	b. S → a (Palíndromos con símbolos pares)
	c. 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).
	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.

Question9

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 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
	c. El árbol representa las cadenas que inician en dos a”s seguida de una o más a”s de un lenguaje regular
	d. 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.

Correcto

Puntos para este envío: 1/1.

Question10

Puntos: 1

Sea L el lenguaje de alfabeto Σ = {a,b,c} y cadenas de forma wcv, donde w y v son cadenas de a’s y b’s y w y v tienen la misma longitud pero v no es la cadena inversa de w. Dicho lenguaje coincide con el generado por la gramática:

Seleccione una respuesta.

	a. S → aSa, S→bSb, S→aRb, S→bRa, R→aRa, R→bRb, R→c.
	b. S → aSa, S→bSb, S→aRb, S→bRa, R→aRa, R→bRb, R→aRb, R→bRa, R→c.	Correcto: Como w y v no pueden ser cadenas inversas, al menos debe existir un par de caracteres de w y v que ocupen posiciones simétricas con respecto al centro de la cadena y sean diferentes . Por tanto, toda cadena de L puede ser generada por la gramática, y toda cadena generada por la gramática pertenece a L
	c. S → aSa, S→bSb, S→aRb, S→bRa, R→aRb, R→bRa, R→c.
	d. S → aSa, S→bSb, S→aRb, S→bRa, R→bRb, R→aRa, R→bRa, R→c.

Correcto

Puntos para este envío: 1/1.

Question11

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. 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.
	b. El número de letras a es igual al de letras b en w	Esto es verdadero
	c. Las cadenas {abc, c} son aceptadas
	d. w = xc | x ∈ (a∪ b)*

Incorrecto

Puntos para este envío: 0/1.

Question12

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 | aAc | bBc ; B ---> bBc | bc
	d. S --->aAc ; A--->aAc | bBc ; B ---> bBc | bc	Correcto

Correcto

Puntos para este envío: 1/1.

Question13

Puntos: 1

En la descripción de las gramáticas, las producciones unitarias tienen la forma:

Seleccione una respuesta.

	a. A --> B	Correcto
	b. S-->a
	c. S-->ABs
	d. A -->sB

Las producciones unitarias son las que tienen la forma A → B

Correcto

Puntos para este envío: 1/1.

Question14

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. Los autómatas de pila reconocen lenguajes generados por gramáticas de tipo 3
	d. Las máquinas de Turing y los autómatas de pila son autómatas finitos

Correcto

Puntos para este envío: 1/1.

Question15

Puntos: 1

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

Seleccione una respuesta.

	a. La cadena {b} es rechazada
	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. 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
	d. El lenguaje generado por la gramática es estructurado por frases

Correcto

Puntos para este envío: 1/1.

1

Puntos: 1

A las computadoras reales y las MT se les asocian muchas similitudes y diferencias: Cuáles diferencias entre una computadora Real y una máquina de Turing (MT) son verdaderas:

Seleccione al menos una respuesta.

	a. En una MT el Número de estados depende de la cadena, palabra o dato que lea.	Incorrecto: la palabra o cadena de lectura no determina la cantidad de estados que deba tener una MT. Puede determinar pro que estados recorre la máquina.
	b. En una MT el orden de ejecución de las instrucciones no necesariamente debe estar definido.
	c. En una computadora, el número de estados viene representado por el contenido de la memoria.
	d. 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: Diferencias entre las computadoras y las máquinas de Turing. 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.

Parcialmente correcto

Puntos para este envío: 0.5/1.

Question2

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

Correcto

Puntos para este envío: 1/1.

Question3

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. 0101
	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. 0110

Correcto

Puntos para este envío: 1/1.

Question4

Puntos: 1

Dentro de las tesis que plasmaron Church y Turing, está una de las más aplicadas y demostradas hoy en día, enfocada al funcionamiento de las máquinas reales (coputadoras). Esta es:

Seleccione una respuesta.

	a. Las máquinas reales tienen mayor poder de cómputo que las Máquinas de Turing, aunque resuelvan los mismos problemas.	Incorrecto
	b. Toda función computable tiene un algoritmo decidible pro una MT
	c. La máquina de Turing, tiene mayor poder de cómputo que las reales, aunque resuelvan los mismos problemas.
	d. Una MUT es funcional y eficiente tanto como una máquina real.

Incorrecto

Puntos para este envío: 0/1.

Question5

Puntos: 1

La codificación redundante tiene como objetivo introducir símbolos para asegurar la veracidad en la trasmisión. Esto se logra por medio de algoritmos que aseguran la veracidad de la información transmitida procurando no perder velocidad en la trasmisión. Los algoritmos para la veracidad son:

Seleccione una respuesta.

	a. Los de codificación AWGN
	b. Los de codificación de fuente:
	c. Los de codificación de canal	Correcto: Esto se logra por medio de algoritmos que adapten la información teniendo en cuenta las características estadísticas del ruido que presenta el canal.
	d. Los de codificación de ruido

Correcto

Puntos para este envío: 1/1.

Question6

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 MT el orden de ejecución de las instrucciones no está definido.
	b. 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.
	c. En una computadora, el número de estados viene representado por el contenido de la memoria.	Correcto
	d. En una MT el nº de estados depende del algoritmo.	Correcto

Correcto

Puntos para este envío: 1/1.

1

Puntos: 1

Los PROBLEMAS DE HALTING hacen referencia a: (Seleccione las opciones verdaderas).

Seleccione al menos una respuesta.

	a. El problema de tipo "insoluble" define que hay un algoritmo que lo soluciona pero que no se puede llevar a una MT o una máquina abstracta.	Incorrecto
	b. El problema de “Halting” es el primer problema indecidible mediante maquinas de Turing	Correcto
	c. Equivale a construir un programa que te diga si un problema de ordenador finaliza alguna vez o no (entrando a un bucle infinito, por ejemplo)	Correcto
	d. El problema de la parada o problema de la detención es de hecho soluble y la Teoría de la Computación lo definió como tal	Incorrecto

El problema de “Halting” es el primer problema indecidible mediante máquinas de Turing. Equivale a construir un programa que te diga si un problema de ordenador finaliza alguna vez o no (entrando a un bucle infinito, por ejemplo)

Correcto

Puntos para este envío: 1/1.

Question2

Puntos: 1

La Máquina de Turing, y un autómata finito, tienen similitudes como:

Seleccione al menos una respuesta.

	a. Una cabeza lectora	Correcto
	b. Un control finito	Correcto
	c. Un alfabeto para la cinta y un alfabeto de entrada	Incorrecto
	d. Un cabezal de lectura y otro para escritura	Incorrecto

Máquina de Turing (abreviado MT) tiene, como los autómatas que hemos visto antes, un control finito, una cabeza lectora y una cinta donde puede haber caracteres, y donde eventualmente viene la palabra de entrada

Correcto

Puntos para este envío: 1/1.

Question3

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. 01	Correcto
	b. 10
	c. 00
	d. 11

Correcto

Puntos para este envío: 1/1.

Question4

Puntos: 1

Cuando se tratan los PROBLEMAS INSOLUBLES PARA LA TEORIA DE LENGUAJES, se presentan los “Problemas de decisión” (PD).

Que aspectos en análisis son válidos para apoyar esta teoría

Seleccione al menos una respuesta.

	a. Se puede decir que un lenguaje es decidible por que existe una MT que los puede reconocer.	Correcto
	b. Si se presenta un lenguaje decidible, es por que hay un algoritmo que la MT reconoce.	Correcto
	c. Un PD podría ser aquél formulado por una pregunta (referida a alguna propiedad) que requiere una respuesta de tipo “si/no”. Hay problemas de decisión de tipo “soluble”, “parcialmente soluble” e “insoluble	Correcto
	d. Mientras que los lenguajes computables son una infinidad numerable, los lenguajes no computables son una infinidad no numerable.	Correcto

Correcto

Puntos para este envío: 1/1.

Question5

Puntos: 1

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

Seleccione una respuesta.

	a. Los modelos propuestos por Hilbert, solucionan cualquier problema "No soluble"
	b. Las funciones computables hacen referencia o son iguales a afirmar que son modelos computables.
	c. La MT no es un modelo Computable ya que solo se basa en simulación.
	d. 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

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.

Question6

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 y determine el valor de “m” los bits que quedan en la memoria del código de longitud restringida:

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. 010
	b. 100
	c. 001	Incorrecto
	d. 110

Incorrecto

Puntos para este envío: 0/1.

Question7

Puntos: 1

Una Máquina de Turing (MT) se puede comportar como un aceptador de lenguaje, de la misma forma que lo hace un Autómata finito (AF) o un Autómata de Pila (AP) así: Colocando una cadena ω en la cinta, situando la cabeza de lectura/escritura sobre el símbolo del extremo izquierdo de la cadena ω y al poner en marcha la máquina a partir de su estado inicial. Entonces ω es aceptada si, después de una secuencia de movimientos, la MT llega a un estado final y para.

Que aspectos son válidos para el comportamiento de una MT..?

Seleccione al menos una respuesta.

	a. Se pueden combinar dos Máquinas de Turing (MT) permitiendo que compartan la misma cinta y, que cuando una termine su ejecución, la otra empiece.	Correcto
	b. Es válido empezar el diseño de una MT por el diseño de un AF. Ambos son aceptadores de lenguajes.	Correcto: 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 (acepta cadenas válidas).
	c. La MT es un mecanismo abstracto avanzado que tiene el mismo poder computacional que las máquinas reales.	Incorrecto: La Máquina de Turing es un mecanismo de computación notoriamente primitivo, y sin embargo permite llevar a cabo cualquier cómputo que podamos hacer en nuestro PC
	d. Para rechazar una cadena que no es aceptable, lo único que hay que hacer es evitar que se llegue a un estado final.	Correcto

Correcto

Puntos para este envío: 1/1.

Question8

Puntos: 1

Con referencia a una Máquina de Turing (MT) de dos direcciones: Una Máquina de Turing con una cinta infinita en un sentido puede simular una Máquina de Turing con la cinta infinita en los dos sentidos. Sea M una Máquina de Turing con una cinta infinita en los dos sentidos, entonces:

Para que se logre o se dé esta máquina se debe cumplir:

Seleccione al menos una respuesta.

	a. La pista inferior y superior leen los datos simultáneamente en ambos sentidos. Luego y dependiendo de los estado repetitivos, se detiene una pista y continúa la que menos celdas tenga ocupada.	Incorrecto
	b. La cinta superior contiene información correspondiente a la parte derecha de la cinta M a partir de un punto de referencia dado.	Correcto: La cinta superior por orden contiene la información de la parte derecha.
	c. La pista inferior contiene tanto la parte izquierda como la derecha de la cinta M (en orden inverso).	Incorrecto: La cinta superior por orden contiene la información de la parte derecha.
	d. La Máquina de Turing M que tiene una Cinta Infinita en un sentido, puede simular a M si tiene una cinta con dos pistas.	Correcto: La pista superior maneja un sentido y la inferior maneja otro sentido (dirección).

Correcto

Puntos para este envío: 1/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. 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
	b. 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
	c. 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”
	d. 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.

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

Indique que características asocian particularidades o semejanzas válidas entre las MT y las computadoras reales.

Seleccione al menos una respuesta.

	a. En las máquinas reales están definidos procesos de manera jerárquica. En las MT estos procesos están definidos por el número de estados.	Incorrecto: En una MT el nº de estados depende del algoritmo. En una computadora, un estado viene representado por el contenido de la memoria, y una situación por un estado y un puntero a una dirección (la que contiene a la instrucción que va a ejecutarse).
	b. Las MUT son de un solo propósito. Las máquinas reales interpretan muchos programas escritos en diferentes lenguajes (multipropósito).	Incorrecto: Esta máquina Universal no debe ser diseñada para realizar un cálculo específico, sino para procesar cualquier información (realizar cualquier cálculo específico -MT particular- sobre cualquier configuración inicial de entrada correcta para esa MT particular).
	c. Los computadores electrónicos, basados en la arquitectura Von Neumann así como las máquinas cuánticas tendrían exactamente el mismo poder de expresión que el de una Máquina de Turing (MT) si dispusieran de recursos ilimitados de tiempo y espacio.	Correcto
	d. Los lenguajes de programación, tienen a lo sumo el mismo poder de expresión que el de los programas para una Máquina de Turing (MT) y en la práctica no todos lo alcanzan.	Correcto

Correcto

Puntos para este envío: 1/1.