AUTOMATAS Y LENGUAJES FORMALES COMPLETO

1

Puntos: 1

En estos años, Turing trabajó en solitario descifrando el funcionamiento de todos los patrones alemanes que determinaba donde y cuando Iban a bombardear Inglaterra. Acortando así los tiempos de guerra.

Seleccione una respuesta.

	a. 1939 -1942	Correcto
	b. 1942 - 1945
	c. 1938 - 1939
	d. 1945 - 1947

Biografía de Alan Turing

Correcto

Puntos para este envío: 1/1.

Question2

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. 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.
	b. El Padre de Alan Mathison Turing: Julius Mathison Turing era de origen Polaco.
	c. 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.
	d. En el mismo año que nació Alan Mathison Turing, aconteció el hundimiento del trasatlántico Británico “El Titanic”

Biografía de Alan Turing

Incorrecto

Puntos para este envío: 0/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 y en principio una solución única para cualquier problema matemático.
	b. 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?	Correcto: Hace referencia al problema de decisión. El Entscheidungsproblem
	c. 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.
	d. Un problema matemático tiene “finitas soluciones”. Si son infinitas es porque el problema puede ser insoluble.

Biografía de Alan Turing

Correcto

Puntos para este envío: 1/1.

Question4

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

Biografía de Alan Turing

Correcto

Puntos para este envío: 1/1.

Question5

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

Biografía de Alan Turing

Parcialmente correcto

Puntos para este envío: 0.5/1.

Question6

Puntos: 1

Alan Turing tenía dentro de sus aficiones, el ejercicio físico. En Junio de 1948 tiene lugar la primera demostración práctica del principio de la computadora de Turing y ese mismo año estuvo entrenando, y a punto de participar por Inglaterra en los Juegos Olímpicos del 1948 en atletismo de larga distancia. Podría decirse que su gusto por el deporte se reafirmó dado un evento curioso:

Seleccione una respuesta.

	a. Por una huelga nacional en Inglaterra que lo obligó a desplazarse grandes distancias en bicicleta y a pie para llegar a la escuela,	Correcto: En 1926, con catorce años, ingresó en el internado de Eurobridge International College Sherborne School en Dorset Inglaterra. Su primer día de clase coincidió con una huelga general en Inglaterra, pero su determinación por asistir a clase en su primer día era tan grande que recorrió en solitario con su bicicleta las más de 60 millas que separaban Southampton de su escuela, pasando la noche en una posada. Tal hazaña fue recogida en la prensa local
	b. Por una beca obtenida en el Cambridge de Inglaterra por ser el mejor estudiante.
	c. Toda su familia fue reconocida en Inglaterra por participar en las competencias delas olimpiadas de 1948.
	d. En la segunda guerra mundial, como agente secreto del ejército Inglés, tenía que caminar grandes distancias entre los laboratorios donde se encontraban las máquinas que codificaban las posiciones de la artillería Alemana.

Biografía de Alan Turing

Correcto

Puntos para este envío: 1/1.

1

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. {ba, ab, b, a}
	c. {a, b, ab, ba, aab, bba, aaab}
	d. {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}

Correcto

Puntos para este envío: 1/1.

Question2

Puntos: 1

La definición formal de un Lenguaje Regular (ele) L, se da solo si cumple ciertas condiciones. Siendo ∑ un alfabeto, el conjunto de los lenguajes regulares sobre ∑ = {a,b} puede estar formado por:

Seleccione al menos una respuesta.

	a. {a} y {b} son lenguajes regulares. {a,b} es regular pues resulta de la unión de {a} y {b}.	Correcto: Definición formal de Lenguaje Regular. Por la definición anterior, el conjunto de los lenguajes regulares formado por el lenguaje vacío, los lenguajes unitarios incluido lambda y todos los lenguajes obtenidos a partir de la unión, concatenación y cerradura o estrella de Kleene.. {ab} es regular pues resulta de la concatenación de {a} y {b}.
	b. La cadena vacía (lambda) es un lenguaje regular.	Correcto: Lambda es regular.
	c. La cadena vacía y el conjunto vacío no son lenguajes regulares.	Incorrecto: Lambda es un lenguaje regular
	d. {ab} no es regular.	Incorrecto: Es regular.

Correcto

Puntos para este envío: 1/1.

Question3

Puntos: 1

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

Seleccione al menos una respuesta.

	a. Por ser un alfabeto un conjunto finito de elementos, las posibles cadenas que se formen no pueden ser vacías
	b. Las cadenas que se forman a partir de un alfabeto finito, resultan ser infinitas.
	c. 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
	d. 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.

Correcto

Puntos para este envío: 1/1.

Question4

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.

Question5

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) solo puede utilizarse para aceptar lenguajes finitos.
	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.	Correcto: Independiente del determinismo o no.
	c. 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.
	d. Nunca se puede afirmar con seguridad que un autómata finito no determinista (AFND) acepta una cadena.

Correcto

Puntos para este envío: 1/1.

Question6

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}.	Incorrecto: la segunda cadena también es aceptada
	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. { α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
	d. 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

Correcto

Puntos para este envío: 1/1.

1

Puntos: 1

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

Seleccione una respuesta.

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

Incorrecto

Puntos para este envío: 0/1.

Question2

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. {22, 0,1,001122, 12, 012, 022}
	b. Solo acepta cadenas vacías (lambda).
	c. {101, 210, 20,110, 200}	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. Es un AFND y acepta cualquier cadena que inicie con cero (0)

Incorrecto

Puntos para este envío: 0/1.

Question3

Puntos: 1

Que representa la siguiente figura:

Seleccione una respuesta.

	a. Que representa la siguiente figura:
	b. Un Autómata de tipo AFND válido.	Correcto: Es un Autómata Finito No Determinístico (AFND) válido. Es una extensión válida de un AFD. Permite que de cada nodo del diagrama de estados salga un número de flechas mayor o menor que |∑|
	c. No representa un autómata válido por que el mismo estado inicial es el mismo estado final.
	d. Un Autómata que acepta palabras o cadenas que contienen únicamente b´s o a´s

Correcto

Puntos para este envío: 1/1.

Question4

Puntos: 1

Para el siguiente Autómata Finito denotado como: A2= (E. Q, f, q1, F) donde E = {0,1}, F = {q2} y Q = {q1, q2, q3, q4}, identifique correctamente el Lenguaje que genera y la expresión regular:

Seleccione una respuesta.

	a. L = (A2 ) = {0, 111, 11100, …} = { 1(10)n |n = 0} La expresión regular es: 1(01)+
	b. L = (A 2) = {1, 101, 10101, …} = { 1(01)n |n ≥ 0} La expresión regular es: 1(01) *	Correcto: El lenguaje generado se obtiene partiendo del estado inicial y recorriendo todos los caminos posibles para alcanzar el estado final
	c. L = (A2 ) = {0, 001, 01111, …} = { 1(10)n |n ≤ 0} La expresión regular es: 0(01) *
	d. L = (A2 ) = {0, 001, 00100, …} = { 1(01)n |n ≠ 0} La expresión regular es: 0(01) *

Correcto

Puntos para este envío: 1/1.

Question5

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 ω* es una ER entonces L (ω*) no es una ER
	b. Si ω = a y a pertenece ∑ entonces L (ω) no pertenece ∑
	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.

Question6

Puntos: 1

La expresión regular que se asocia la siguiente autómata es:

Seleccione una respuesta.

	a. r = (10) * + 1*
	b. r = (10 + 0) *	Correcto: Las cadenas que tengan varios unos consecutivos son rechazadas
	c. r = (1)* + (0) + lambda
	d. r = (1 + 0) + 1*

Correcto

Puntos para este envío: 1/1.

Question7

Puntos: 1

Dado los siguientes dos autómatas A y B, analice los enunciados dados e identifique cuales son verdaderos.

Seleccione al menos una respuesta.

	a. Los dos Autómatas reconocen el mismo Lenguaje.
	b. El Autómata A es un AFND y el Autómata B es un AFD	Correcto: El determinismo está dado por el tipo de transiciones que se evalúan en cada estado.
	c. Solo el Autómata A reconoce la cadena vacía lambda
	d. El Autómata B tiene un error de diseño. Un AF no puede tener dos estados de aceptación	Incorrecto

Parcialmente correcto

Puntos para este envío: 0.5/1.

Question8

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 amplia por ser máquinas abstractas (no reales).
	b. En una máquina de estados finitos, la función de transición almacena los datos de entrada del Autómata.
	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 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.

Correcto

Puntos para este envío: 1/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 Libres de Contexto” no incluyen a los “Lenguajes regulares”.
	b. 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.
	c. Los “Lenguajes Recursivamente Enumerables” solo incluye a los “Lenguajes Regulares”.
	d. 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.

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) = Conjunto de todas las cadenas sobre el alfabeto ∑ excepto la vacía.
	c. ∑ *= 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.
	d. ∑ (potencia 0) = {lambda} Conjunto cuyo único elemento es la palabra vacía.

Parcialmente correcto

Puntos para este envío: 0.5/1.

1

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. Un AF es una máquina sin memoria externa; son los estados los que resumen de alguna forma la información procesada	Correcto
	d. La memoria de un Autómata Finito (AF), está dada por sus estados

Parcialmente correcto

Puntos para este envío: 0.8/1.

Question2

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)*	Incorrecto
	c. (ab + aba)*
	d. a +(ab)*

Incorrecto

Puntos para este envío: 0/1.

Question3

Puntos: 1

Dadas las siguientes gramáticas, asócielas a los enunciados que se presentan de forma correcta. Tenga en cuenta que como Símbolo inicial se toma a “S” que son los estados iniciales y como símbolos no terminales los estados en el orden de su nombramiento. El conjunto finito de símbolos terminales son los símbolos del alfabeto ∑ del autómata.

Seleccione al menos una respuesta.

	a. La Gramática D corresponde a una representación válida del lenguaje que acepta el Autómata “C”.
	b. La Gramática A corresponde a una representación válida del lenguaje que acepta los Autómatas “A” y “B”.	ncorrecto. La gramática no le corresponde a los autómatas dados.
	c. La Gramática B corresponde a una representación válida del lenguaje que acepta el Autómata ”D”.
	d. La Gramática C corresponde a una representación válida del lenguaje que acepta el Autómata con lambda transiciones del Autómata “E”	Correcto: La gramática C es la de un AFND con landa transiciones.

Parcialmente correcto

Puntos para este envío: 0.5/1.

Question4

Puntos: 1

Acerca de la clasificación de los lenguajes, identifique las afirmaciones válidas con referencia a la jerarquía y comportamiento de los mismos:

Seleccione al menos una respuesta.

	a. Se llama “clase de lenguajes” a conjuntos de lenguajes que comparten cierta propiedad dada.	Correcto
	b. Según la clasificación de lenguajes definida por Chomsky y que la llamó “jerarquía de lenguajes”, los “Lenguajes Regulares” es la clase más pequeña en la jerarquía, e incluye a los lenguajes más simples. Estos se llaman así porque sus palabras contienen “regularidades” o repeticiones de los mismos componentes.	Correcto
	c. Al clasificar lenguajes, no se están clasificando máquinas que los reconozcan, Se clasifican gramáticas que los generan.
	d. Los lenguajes son en sí conjuntos de secuencias de símbolos y las clases de lenguajes son conjuntos de conjuntos de secuencias de símbolos.

Parcialmente correcto

Puntos para este envío: 0.7/1.

Question5

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 ) *	Incorrecto
	b. ( a | b)*
	c. (a.b)*
	d. (a,b)*

Incorrecto

Puntos para este envío: 0/1.

Question6

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

Correcto

Puntos para este envío: 1/1.

Question7

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 alfabeto.	Correcto: Un autómata puede describirse dando el alfabeto.
	b. 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.
	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.

Question8

Puntos: 1

En la teoría de lenguajes se presentan operaciones que aplican también al tratado de conjuntos. Estas operaciones se pueden realizar con palabras que hacen pare de un determinado lenguaje. Si “x” es una palabra y “y” otra palabra; la siguiente operación: 

(xy)z =x(yz)

corresponde a la propiedad:

Seleccione una respuesta.

	a. Distributiva
	b. Operación cerrada
	c. Asociativa
	d. Conmutativa	Incorrecto:

Incorrecto

Puntos para este envío: 0/1.

Question9

Puntos: 1

Cuáles afirmaciones son válidas y que surgen de un análisis de las ER (Expresiones Regulares):

Analice los autómatas dados:

Seleccione al menos una respuesta.

	a. La ER (0+1)*01 genera las mismas cadenas para el Autómata “B” y del autómata “A”
	b. La ER (0+1)*11(01)* genera cadenas válidas para el autómata “B” pero no para las del autómata “A”.	Incorrecto
	c. La ER (0+1)*01 genera cadenas válidas para el autómata “A”, pero no para las del autómata “B”.
	d. La ER (1*00*1(00*1)*1)*1*00*1(00*1)* genera las mismas cadenas para el Autómata “A” el autómata “B”.	Correcto: Ambas ER son equivalentes y aplican para el autómata. Se debe aplicar la propiedad de la operación matemática de la estrella de Kleene.

Parcialmente correcto

Puntos para este envío: 0.5/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. Es un Autómata Finito Determinístico con lambda transiciones
	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 (AFD)

Correcto

Puntos para este envío: 1/1.

Question11

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.

Question12

Puntos: 1

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

Seleccione al menos una respuesta.

	a. Es una aplicación de los autómatas. Un interruptor de luz
	b. No es un autómata válido en diseño	Incorrecto
	c. Es un AF.
	d. No tiene alfabeto definido	Incorrecto: se puede asociar a estados de 1 y 0 (encendido, apagado) como impulsos eléctricos

Incorrecto

Puntos para este envío: 0/1.

Question13

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 AFD pero no reconoce el mismo lenguaje que el autómata A
	b. Ambos son AFD y reconocen el mismo lenguaje
	c. 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.
	d. 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

Parcialmente correcto

Puntos para este envío: 0.5/1.

Question14

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 AFND que acepta el lenguaje (ab U aba)*
	c. Es una autómata AFND cuya ER es: (ababa)*	Incorrecto
	d. Es un autómata finito no determinista que acepta la cadena {ababaab}

Incorrecto

Puntos para este envío: 0/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 c | n>=1
	b. A(potencia n)b(potencia n) c | n>=1	Correcto
	c. A (potencia n) b (potencia n) c (potencia n) | n>=1
	d. A (potencia n) b (potencia 2n) d | n>=1	Correcto

Correcto

Puntos para este envío: 1/1.

1

Puntos: 1

Una palabra nos puede ayudar a determinar si una cadena pertenece a un determinado lenguaje, pero también a algo más: a determinar la estructura sintáctica de la misma. Esta viene dada por los árbol de derivación.
Cuando hay recursividad por la Izquierda, los árboles de derivación se expanden por la Derecha.

Este principio se debe entre otras cosa a que:

Seleccione una respuesta.

	a. Los símbolos se añaden hacia abajo pero no pueden ser repetitivos. Por eso su derivación
	b. Si no hay más símbolos que agregar, en un determinado nodo, no se evalúan más ramificaciones.
	c. Los símbolos de entrada se añaden a los nodos en orden de izquierda a derecha	Correcto: Esta es la respuesta correcta: Si a este nodo se le aplica una determinada regla S --> a , entonces para cada símbolo que aparezca en a se añade un hijo con el símbolo correspondiente, situados en el orden de izquierda a derecha
	d. En un árbol de derivación, pueden haber nodos en la izquierda vacíos (sin símbolos), por eso se pasa a la derecha en busca de otros nodos válidos.

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 “arbol de derivación” o “árbol de análisis”. Para una derivación dada, el símbolo inical “S” etiqueta la raíz del árbol. El nodo raíz tienen unos nodos hijos para cada símbolo que aparezca en el lado dereho de la producción, usada para reemplazar el símbolo inicial. De igual forma, cada símbolo no terminal tienen 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.

Question2

Puntos: 1

Dada la siguiente gramática: 

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

Compuesta por los estados S, A, B y en la que los tres son estados finales o de aceptación, analice cual afirmación es verdadera:

Seleccione una respuesta.

	a. La gramática no genera la cadena vacía	Correcto: La gramática es válida y representa el autómata, pero no genera la cadena vacía. Tendría que en cada nodo terminal tener un bucle y ser representado en la gramática
	b. La gramática no genera ningún lenguaje porque presenta más de un estado de aceptación o final.
	c. La gramática solo genera cadenas de un símbolo y la cadena vacía
	d. La gramática genera la cadena vacía

Correcto

Puntos para este envío: 1/1.

Question3

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. Los caracteres a la mitad de la pila no son accesibles sin quitar antes los que están encima de ellos.	Correcto
	c. En un AP podemos modificar su “tope”, que es el extremo por donde entran o salen los caracteres	Correcto
	d. Sin importar si la pila está vacía o no, este siempre hará un movimiento.

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 no vacío de símbolos terminales	Correcto
	b. Un alfabeto infinito y no vacío de símbolos terminales
	c. Un alfabeto regular (o sea de tipo 3 según Chomsky)
	d. Un alfabeto inicializado con lambda como cadena válida

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

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 puede tener un número ilimitado de transiciones distintas
	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 de q estados y n símbolos puede tener a lo sumo n × q2 transiciones

Correcto

Puntos para este envío: 1/1.

Question6

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. 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”.	Es cierto que: 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.
	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.
	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. 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	Esta afirmación es cierta en el contexto. Pero la pregunta está solicitando cuáles apreciaciones son falsas.

Parcialmente correcto

Puntos para este envío: 0.5/1.

1

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 al igual que una Máquina de Turing o un Autómata Finito, su definición básica es de naturaleza no determinista
	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 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. 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.

Question2

Puntos: 1

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

Seleccione al menos una respuesta.

	a. Combinar gramáticas
	b. Que “sobren palabras”
	c. 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.
	d. Reutilizar gramáticas y modificarlas para ajustarlas al lenguaje generado	Incorrecto: Es posible hacerlo pero no son errores comunes

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.

Parcialmente correcto

Puntos para este envío: 0.5/1.

Question3

Puntos: 1

Dado el siguiente autómata finito (AF), reconoce el lenguaje generado por la gramática:

Seleccione una respuesta.

	a. G= {S -->0B | 0A , A ---> 1B | lambda , B ---> lambda
	b. G={S ---> 0A| lambda,, A ---> 0A | 1B, B ---> 1B|lambda}	Correcto
	c. G = { S --->A |lambda , A ---> 0B | lambda,, B ---> lambda}
	d. G = { S --->B |lambda , A ---> 1B | lambda,, B ---> lambda}

Correcto

Puntos para este envío: 1/1.

Question4

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

Correcto

Puntos para este envío: 1/1.

Question5

Puntos: 1

Dada la siguiente gramática regular G , identifique el conjunto de cadenas o palabras válidas que puede generar el Autómata Finito que lo representa: (Para el desarrollo del ejercicio se sugiere graficar o recrear el autómata)

S → aA | bA

A → aB | bB | a

B → aA | bA

Seleccione una respuesta.

	a. El conjunto de cadenas que pueda generar la ER = a*b*a
	b. {aa, aaaa, bbba, ba, bba, baaa, baba}	Correcto: Son cadenas válidas. Se debe generar un Autómata finto y evaluar esas cadenas.
	c. {a,b}
	d. {baaaa, aaaaa, bba}

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 LIC
	b. Producciones de tipo GIC con un solo nodo terminal
	c. Formas canónicas que restrinjan los tipos de producciones que pueden utilizarse.	Correcto
	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.

Question7

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 estado	Correcto
	b. A cada símbolo de entrada (Incluyendo la cadena vacía)	Correcto
	c. A cada movimiento de la pila	Correcto
	d. A cada símbolo topo de la pila	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.

Correcto

Puntos para este envío: 1/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. ∑0 = {lambda} Conjunto cuyo único elemento es la palabra vacía.	Correcto
	c. ∑0 = Conjunto de todas las cadenas sobre el alfabeto ∑ excepto la vacía.
	d. ∑+ = Conjunto de todas las cadenas positivas 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

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

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.

Question10

Puntos: 1

Indique cuál de las siguientes afirmaciones es verdadera:

Seleccione al menos una respuesta.

	a. Con un autómata de pila no puede reconocerse un lenguaje regular
	b. 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.
	c. Para reconocer un lenguaje regular mediante un autómata de pila el alfabeto de la pila debe contener al menos un símbolo
	d. 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.

Parcialmente correcto

Puntos para este envío: 0.5/1.

1

Puntos: 1

Indique cuál de las siguientes afirmaciones es falsa:

Seleccione una respuesta.

	a. La intersección de dos lenguajes estructurados por frases es un lenguaje estructurado por frases
	b. La unión de un número finito de lenguajes estructurados por frases es un lenguaje estructurado por frases
	c. Todo lenguaje cuyo complementario sea un lenguaje finito es independiente del contexto
	d. La intersección de un lenguaje regular con un lenguaje independiente del contexto es siempre un lenguaje regular.	Correcto: La intersección del lenguaje regular xn ym y el lenguaje independiente del contexto xn yn es el lenguaje independiente del contexto no regular xn yn

Correcto

Puntos para este envío: 1/1.

Question2

Puntos: 1

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

Seleccione una respuesta.

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

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

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

Correcto

Puntos para este envío: 1/1.

Question4

Puntos: 1

Que apreciaciones son ciertas con referencia a lo que describe el siguiente árbol de derivación:

Seleccione al menos una respuesta.

	a. Acepta el lenguaje de las palabras que empiezan por “a”, terinan por “c” y además en medio de estas dos letras pueden haber una “b” o muchas “b”s	Correcto
	b. La ER que representa el lenguaje que acepta ese árbol de derivación es ab*c	Correcto
	c. Acepta el lenguaje de las palabras que empiezan por S y terminan en una o muchas A”s. La ER que lo representa es SA*	Incorrecto
	d. Este árbol de derivación es producto de la gramática lineal por la derecha: S –>aA | A ---> bA | c	Correcto

Correcto

Puntos para este envío: 1/1.

Question5

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. w = xc | x ∈ (a∪ b)*	Esta afirmación es falsa y es la respuesta correcta: Por ejemplo la cadena w = ac no es generada por la gramática
	b. El número de letras a es igual al de letras b en w
	c. 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.
	d. Las cadenas {abc, c} son aceptadas

Correcto

Puntos para este envío: 1/1.

Question6

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 lenguajes regulares y el conjunto de los LIC son conjuntos independientes.
	c. El conjunto de los lenguajes regulares contiene al conjunto de las GIC.
	d. 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).

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.

Question7

Puntos: 1

Que significan las reglas de la forma A → lambda

Seleccione al menos una respuesta.

	a. Generan lenguajes que contienen la palabra vacía	Incorrecto: El hecho que gramática GLC contenga reglas de la forma A → lambda no significa que el lenguaje contenga forzosamente a la palabra vacía
	b. Que estén en una gramática, deben permitir que el lenguaje no se cambie o altere
	c. No se pueden eliminar en una gramática ya que si se hiciere, modifican el lenguaje	Incorrecto
	d. Se le llaman producciones nulas

Incorrecto

Puntos para este envío: 0/1.

Question8

Puntos: 1

La relación entre un AP y un LLC (Lenguaje Libre de contexto) permite que dada una Gramática G, existe entonces un AP que acepta exactamente el lenguaje generado por G.

Dado el siguiente autómata de pila (AP) cuyo funcionamiento se representa en la siguiente tabla, identifique la gramática correcta y sus reglas que aceptan el LLC dado por el AP.

Seleccione una respuesta.

	a. S –> 0A0 | 1S0 | 2 | 0
	b. S –> 0A0 | 1S1 | 2
	c. S –> 0A0 | 1S2 | 1 | 0	Incorrecto: En la pila lo que falta por leer viene siendo la cadena que se evalúa .Esta gramática no es la que recorre el árbol que permite esa salida.
	d. S –> 0A0 | 1S2 | 10

Incorrecto

Puntos para este envío: 0/1.

Question9

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. Los lenguajes generados por una Gramática Independiente del Contexto son llamados Lenguajes Regulares
	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. En un árbol de derivación cada nodo solamente puede tener otro hijo nodo
	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.

Question10

Puntos: 1

Dada la siguiente gramática con las siguientes producciones: Determine que opciones son verdaderas y aplican al diseño y análisis de la misma.

Seleccione al menos una respuesta.

	a. Es una gramática independiente de contexto	Correcto
	b. La gramática debe aplicar las reglas 2n veces para que genere el lenguaje L = {x (potencia m) y (potencia n) | 0 <= n <= m }	Incorrecto: la cadena se genera aplicando 2n–m veces la primera regla y m–n veces la segunda; si 2n ≤ m ≤ 3n hay que aplicar 3n–m veces la segunda regla y m–2n veces la segunda.)
	c. Genera le lenguaje : L = {x (potencia m) y (potencia n) | 0 <= n <= m <= 3n }	Correcto
	d. Reconoce las cadenas {xx, yy}	Correcto

Correcto

Puntos para este envío: 1/1.

Question11

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 determinista (en sentido estricto)	Correcto: hay que construir el autómata, teniendo en cuenta que sea determinista
	b. Independiente del contexto no determinista (en sentido estricto)
	c. Regular
	d. Estructurado por frases (en sentido estricto).

Correcto

Puntos para este envío: 1/1.

Question12

Puntos: 1

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

Seleccione una respuesta.

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

Correcto

Puntos para este envío: 1/1.

Question13

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

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.

Incorrecto

Puntos para este envío: 0/1.

Question14

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 –> 00A –> 001S –> 0010 A –> 00100	Correcto: Ambas producciones aplican a la gramática con cadenas válidas como 0100 y 00100
	b. S –> 0A –> 01S –> 010 A –> 0100	Correcto: Ambas producciones aplican a la gramática con cadenas válidas como 0100 y 00100
	c. S –> 0A –> 00A –> 001 A –> 0010	Incorrecto: las producciones no aplican a la gramática.
	d. S –> 0A –> 0A –> 00A –> 000

Correcto

Puntos para este envío: 1/1.

Question15

Puntos: 1

Dado el alfabeto Σ={x, y, z}, indique cuál de las siguientes afirmaciones es verdadera:

Seleccione una respuesta.

	a. La expresión regular y*(xy*x)*y* representa el lenguaje formado por todas las cadenas que contienen un número par de x’s
	b. La gramática S→ SS, S→ xy, S→ yx genera el lenguaje formado por las cadenas que contienen tantas x’s como y’s;
	c. El lenguaje formado por las cadenas que contienen la secuencia xyxz es regular	Correcto
	d. El lenguaje x (potencia n) y (potencia n) z (potencia n) no es decidible

Correcto

Puntos para este envío: 1/1.

1

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, entonces es probable que solo se solucione usando una Máquina de Turing (MT).
	b. Si se reduce de forma efectiva un problema sin solución efectiva a otro problema, entonces este nuevo problema tampoco tendrá solución efectiva.	Correcto: El reducir estos problemas implica que lo que se obtenga es evaluable en términos de equivalencia. Si la reducción da como resultado otro problema indecidible, entonces seguirá sin tener solución.
	c. 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
	d. 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)

Correcto

Puntos para este envío: 1/1.

Question2

Puntos: 1

Una de las técnicas usadas que permite determinar la indecibilidad en algunos problemas computacionales es:

Seleccione una respuesta.

	a. Usando el método de “Halting”
	b. Usando el método de las “Funciones computables”
	c. Usando el método de Reducción “Reducibilidad de Turing”	Correcto: La reducibilidad ha permitido llegar a determinar la indecibilidad en algunos problemas computacionales
	d. Usando el método de “ Decibilidad de Teorías Lógicas”

Correcto

Puntos para este envío: 1/1.

Question3

Puntos: 1

La Máquina de Turing puede tener varios movimientos dependiendo de diferentes factores (posición inicial, estado, símbolos de entrada). Un movimiento en la Máquina de Turing depende del símbolo explorado con la cabeza y del estado actual con el que se encuentre la máquina, el resultado puede ser:

Seleccione al menos una respuesta.

	a. Todo movimiento del cabezal vacía la cinta y la inicializa en cero.	Correcto
	b. Imprime un símbolo en la cinta reemplazando el símbolo leído.	Correcto
	c. Estado no cambia.	Incorrecto
	d. Se mueve la cabeza de la cinta a la izquierda, a la derecha o se para.	Correcto: En una MT de Turing no es cierto que el movimiento del cabezal, implique vaciar la cinta o inicializar los símbolos iniciales.

Correcto

Puntos para este envío: 1/1.

Question4

Puntos: 1

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

Seleccione al menos una respuesta.

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

Correcto

Puntos para este envío: 1/1.

Question5

Puntos: 1

Las transiciones de una Máquina de Turing de varias cintas (MT), tienen las siguientes características:

Seleccione al menos una respuesta.

	a. La transición solo afecta a una cinta (escribir o desplazar).	Correcto: Hace referencia al funcionamiento de una MT. Las transiciones solo afectan a una cinta a la vez cuando la MT es multicinta.
	b. La transición le asigna el carácter de entrada a las demás cintas
	c. La transición depende de los símbolos actuales de todas las cintas.	Correcto: Hace referencia al funcionamiento de una MT.
	d. Las transiciones se pueden hacer en varias cintas simultáneamente

Correcto

Puntos para este envío: 1/1.

Question6

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 computadora, el número de estados viene representado por el contenido de la memoria.	Correcto: es la asociación entre una MR y una MT.
	b. En una MT el orden de ejecución de las instrucciones no necesariamente debe estar definido.	Incorrecto: Si debe definirse el orden de ejecución de instrucciones.
	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: 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.
	d. 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.

Correcto

Puntos para este envío: 1/1.

1

Puntos: 1

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

Seleccione una respuesta.

	a. No es un problema soluble. Es un problema de decisión
	b. Mediante un autómata de pila, pero no mediante un autómata finito
	c. 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).
	d. Mediante una máquina de Turing, pero no mediante un autómata de pila

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.

Question2

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 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).
	d. 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.

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 una MT es procedimentalmente sencillo para programar lenguajes de máquinas reales.	Incorrecto: Por ser tan de demasiado de “Bajo Nivel” no resultan prácticas para programar
	c. Cualquier lenguaje puede ser reconocido por una máquina de Turing	Incorrecto
	d. 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.	Correcto: Básicamente se trata del diseño de un Autómata con mayor poder de reconocimiento y proceso de lenguajes, que tomas y fusiona aspectos de un AF y de un PDA.

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. 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
	b. Se puede decir que un lenguaje es decidible por que existe una MT que los puede reconocer.	Correcto
	c. Mientras que los lenguajes computables son una infinidad numerable, los lenguajes no computables son una infinidad no numerable.	Correcto
	d. Si se presenta un lenguaje decidible, es por que hay un algoritmo que la MT reconoce.	Correcto

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

Correcto

Puntos para este envío: 1/1.

Question6

Puntos: 1

La tesis de Turing implica ciertas consideraciones: identifique la que es verdadera:

Seleccione una respuesta.

	a. La tesis de Turing implica que para todo lenguaje existe una máquina de Turing que lo acepta, ya sea el alfabeto finito o infinito.
	b. No todo proceso mecánico puede ser simulado ya sea en una máquina real o en una a MT.
	c. La tesis de Turing implica que los lenguajes más generales que existen son los lenguajes estructurados por frases.
	d. Todas las opciones para esta pregunta son falsas	Esta es la respuesta correcta: Existen lenguajes no computables, que no son estructurados por frases y que ninguna máquina de Turing acepta.

Correcto

Puntos para este envío: 1/1.

Question7

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. 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
	b. Cinta Infinita hacia la izquierda	Incorrecto: La cinta no es infinita hacia la izquierda, por lo que hay un cuadro de la cinta que es el extremo izquierdo
	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. Cinta Finita hacia la derecha, por que al extremo izquierdo siempre esta un topeo carácter blanco.	Incorrecto: La cinta no es infinita hacia la izquierda, por lo que hay un cuadro de la cinta que es el extremo izquierdo

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.

Question8

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. 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.
	c. No está permitido realizar ningún movimiento hacia la izquierda a partir de la celda del extremo izquierdo.	Correcto
	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.

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

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

Seleccione al menos una respuesta.

	a. Un control finito	Correcto
	b. Una cabeza lectora	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.