CURSO COMPLETO AUTOMATAS

1

Puntos: 1

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

Seleccione una respuesta.

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

Biografía de Alan Turing

Correcto

Puntos para este envío: 1/1.

Question2

Puntos: 1

En 1952 Ala Turing escribió lo que hoy se conoce como el primer programa de ajedrez escrito para una máquina (ya sea computadora mecánica o como un set de instrucciones o algoritmo).

(En estas URLS puede ver el funcionamiento del programa):

http://www.chessgames.com/perl/chessgame?gid=1670503

http://en.chessbase.com/post/alan-turing-plays-garry-kasparov-at-che-58-years-after-his-death

http://www.chess.com/blog/tradechess/turing---chess-engine---alan-turing

La historia cuenta algunas pruebas que Turing hizo con este programa como: (seleccione las verdaderas).

Seleccione al menos una respuesta.

	a. El programa analizaba hasta dos jugadas previas o posibles combinaciones para determinar la más óptima
	b. A falta de un computador o máquina real lo suficiente potente para ejecutar el programa, el mismo Turing simulaba el funcionamiento del PC.
	c. En la figura se muestra una partida de ajedrez usando el programa de Turing. Si la máquina (algoritmo) fue derrotado, entonces la máquina jugaba de blanco y el humano con las negras.	Correcto
	d. El programa nunca perdió. No se pudo comprobar si era derrotado por la mente humana, Solo hasta los tiempos modernos, grandes jugadores de ajedrez lo derrotaron.	Incorrecto: Turing lo probó con varios de sus amigos y el programa fue derrotado.

iografía Alan Turing

Parcialmente correcto

Puntos para este envío: 0.3/1.

Question3

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.	Incorrecto: El Test de Turing nace como un método para determinar si una máquina puede pensar.
	b. Método para evaluar el rendimiento y capacidad de una maquia. “Poder de procesamiento”
	c. Prueba de error que determina cuando un problema tiene solución o no.
	d. “Método” para determinar si una máquina puede pensar.

Biografía de Alan Turing

Incorrecto

Puntos para este envío: 0/1.

Question4

Puntos: 1

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

Seleccione una respuesta.

	a. Univac
	b. Edvac	Incorrecto: Segunda computadora programable. También fue un prototipo de laboratorio, pero ya incluía en su diseño las ideas centrales que conforman las computadoras actuales. Incorporaba las ideas del doctor Alex Quimis.
	c.Manchester Mark I
	d. Eniac

Biografía de Alan Turing

Incorrecto

Puntos para este envío: 0/1.

Question5

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. En 1928, con dieciséis años, al descubrir e interpretar los trabajos de Albert Einstein
	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.	Incorrecto: Fue por la temprana muere de su amigo y también científico joven Christopher Morcom,
	c. 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.
	d. Dada la muerte de Christopher Morcom, quién fue el primer amor. Morcom murió repentinamente el 13 de febrero de 1930 .

Biografía de Alan Turing

Incorrecto

Puntos para este envío: 0/1.

Question6

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.

1

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.

Question2

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.	Incorrecto: Las palabras aceptadas pueden ser infinitas.
	c. 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.
	d. Por símbolo no se está haciendo referencia a un sólo carácter. Los símbolos pueden ser nombres.

Parcialmente correcto

Puntos para este envío: 0.5/1.

Question3

Puntos: 1

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

Seleccione al menos una respuesta.

	a. { α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
	b. 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
	c. Los símbolos pueden ser nombres. Los alfabetos son finitos.
	d. Por símbolo, se está haciendo referencia a un solo carácter.

Parcialmente correcto

Puntos para este envío: 0.5/1.

Question4

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. {ab} no es regular.
	b. {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}.
	c. La cadena vacía y el conjunto vacío no son lenguajes regulares.
	d. La cadena vacía (lambda) es un lenguaje regular.	Correcto: Lambda es regular.

Correcto

Puntos para este envío: 1/1.

Question5

Puntos: 1

Cuando se trata de simplificar Autómatas, se deben tener en cuenta aspectos como: (Identifique cuál paso o concepto es válido en este proceso de Minimización).

Seleccione una respuesta.

	a. Para saber si dos estados q1 y q2 son equivalentes, se les pone a ambos como estado final de los autómatas M1 y M2, y se procede a comparar dichos autómatas. Si estos últimos son equivalentes, quiere decir que los estados q1 y q2 son equivalentes	Incorrecto
	b. Se entiende por minimización de autómatas finitos al proceso de obtención de un autómata con el menor número de transiciones posibles
	c. Dos estados son equivalentes si al intercambiar uno por otro en cualquier configuración no altera la aceptación o rechazo de toda la palabra.
	d. Dos estados son distinguibles si son compatibles (es decir, si ambos son finales o ambos son iníciales).

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 alfabeto de entrada
	b. El conjunto finito de estados.
	c. La función de transición.
	d. El estado inicial.	Incorrecto: El estado inicial no determina qué tipo de autómata es.

Incorrecto

Puntos para este envío: 0/1.

1

Puntos: 1

Algunas operaciones y propiedades sobre lenguajes y ER que se pueden realizar son:

Seleccione al menos una respuesta.

	a. (B U C) ∙ A = (B ∙ A) U (C ∙ A)	Correcto: Se está identificando o definiendo que la concatenación de lenguajes es distributiva con respecto a la unión.
	b. La concatenación de lenguajes sobre un alfabeto es una operación cerrada, y tiene un elemento neutro que es el lenguaje {lambda}.	Correcto. Es parte de las propiedades de los lenguajes
	c. A ∙ (B U C) = (A ∙ B) U (A ∙ C)
	d. El orden de prioridad de los operadores es, de mayor a menor: *, ∙, + Este orden puede alterarse mediante paréntesis, de forma análoga a como se hace con las expresiones aritméticas.

Parcialmente correcto

Puntos para este envío: 0.5/1.

Question2

Puntos: 1

Que representa la siguiente figura:

Seleccione una respuesta.

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

Correcto

Puntos para este envío: 1/1.

Question3

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 ω = Ø entonces L (ω) = Ø	Correcto: Esta es una ER
	b. Si ω = a y a pertenece ∑ entonces L (ω) no pertenece ∑
	c. Si ω* es una ER entonces L (ω*) no es una ER
	d. Si ω = lambda entonces L (lambda) = { lambda}	Correcto: Esta es una ER

Correcto

Puntos para este envío: 1/1.

Question4

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 estados son el único medio de que disponen los AF para recordar los eventos que ocurren (por ejemplo que caracteres se han leído hasta el momento).	Correcto: Los estados son el único medio de que disponen los AF para recordar los eventos que ocurren (por ejemplo, qué caracteres se han leído hasta el momento); esto quiere decir que son máquinas de memoria limitada.
	c. Los AF son máquinas de memoria limitada.
	d. Los AF son máquinas de memoria amplia por ser máquinas abstractas (no reales).	Incorrecto: Se asemejan a una Maquina Real y estas tienen memoria limitada, finita.

Parcialmente correcto

Puntos para este envío: 0.5/1.

Question5

Puntos: 1

Sea el Autómata Finito (AF) A= (∑, Q, f. q1, F) donde ∑ = {0,1} , Q = {q1, q2, q3, q4}, F= { q2}  y definimos la función de transición fpor la tabla siguiente:

Indique cuál es lenguaje generado por el autómata:

Seleccione una respuesta.

	a. 1(01) *	Correcto: La expresión regular genera las cadenas que inician con 1 y que luego pueden o no tener un 0 o un 1
	b. 1*(1)
	c. 1( 1) (0)*
	d. 0(010)*

Correcto

Puntos para este envío: 1/1.

Question6

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. 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.
	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. Los “Lenguajes Libres de Contexto” no incluyen a los “Lenguajes regulares”.

Correcto

Puntos para este envío: 1/1.

Question7

Puntos: 1

Dado los autómatas M1 y M2 siguientes, cuáles relaciones entre estas dos máquinas son válidas.

Seleccione al menos una respuesta.

	a. Los Autómatas M 1 y M2 son equivalentes: M1 ≈ M2 , por que aceptan exactamente el mismo lenguaje	Correcto: La equivalencia se da por la aceptación de lenguajes. Ambos aceptan el lenguaje a * y aceptan exactamente el mismo lenguaje
	b. Los Autómatas M1 y M2 aceptan ambos el lenguaje a *
	c. Los Autómatas M1 y M2 no son equivalentes porque ambos rechazan el lenguaje b*. La equivalencia se da en la aceptación de lenguajes.	Incorrecto: Ambos rechazan el lenguaje “b”. Ambos aceptan exactamente el mismo lenguaje.
	d. Los Autómatas M1 y M2 son iguales pero no equivalentes	Incorrecto: No son iguales

Parcialmente correcto

Puntos para este envío: 0.5/1.

Question8

Puntos: 1

Una característica que presenta el Autómata Finito siguiente es:

Seleccione una respuesta.

	a. Es un Autómata Finito Determinista (AFD).
	b. Es un Autómata Regular	Incorrecto: Es un AFD
	c. Es un Autómata Finito que acepta la palabra vacía
	d. Es un Autómata Finito No Determinístico (AFND)

Incorrecto

Puntos para este envío: 0/1.

Question9

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, 001, 01111, …} = { 1(10)n |n ≤ 0} La expresión regular es: 0(01) *
	b. L = (A2 ) = {0, 001, 00100, …} = { 1(01)n |n ≠ 0} La expresión regular es: 0(01) *
	c. L = (A2 ) = {0, 111, 11100, …} = { 1(10)n |n = 0} La expresión regular es: 1(01)+
	d. 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

Correcto

Puntos para este envío: 1/1.

Question10

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.

1

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

Correcto

Puntos para este envío: 1/1.

Question2

Puntos: 1

Para el siguiente autómata determine cuales afirmaciones son válidas cando se trata de evaluar que cadenas acepta el autómata.

Seleccione al menos una respuesta.

	a. Si una cadena tiene menos de 5 unos, entonces tiene un número par de unos.
	b. Si una cadena tiene 5 unos o más, entonces contiene un número impar de unos.	Correcto: Al recorrer el autómata, se confirma la relación de unos descrita
	c. Si una cadena tiene 5 unos o más, entonces contiene un número par de unos.
	d. Todas las cadenas que tengan igual número de unos y de ceros son aceptadas.	Incorrecto: No corresponden el número de unos descritos en la cadena

Parcialmente correcto

Puntos para este envío: 0.5/1.

Question3

Puntos: 1

Dado el siguiente autómata Finito, es válido afirmar:

Seleccione al menos una respuesta.

	a. La Er que lo representa es: (ab*a)*
	b. La ER que lo representa es: (b+ab*a)*	Incorrecto
	c. La ER que lo representa: (b+ab*a)*ab*
	d. La ER que lo representa es: (b*ab*a)*b*ab*

Incorrecto

Puntos para este envío: 0/1.

Question4

Puntos: 1

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

Seleccione una respuesta.

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

Correcto

Puntos para este envío: 1/1.

Question5

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. Operación cerrada
	b. Distributiva
	c. Asociativa	Correcto
	d. Conmutativa

Correcto

Puntos para este envío: 1/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
	b. Operación cerrada de dos lenguajes	Incorrecto: La operación de cierre dice: El lenguaje resultante está definido sobre el mismo alfabeto que L1 y L2.
	c. Unión de lenguajes
	d. Asociación de lenguajes

Incorrecto

Puntos para este envío: 0/1.

Question7

Puntos: 1

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

Seleccione una respuesta.

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

Correcto

Puntos para este envío: 1/1.

Question8

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.

Question9

Puntos: 1

Para el siguiente Autómata, asocie la expresión regular que lo identifica:

Seleccione una respuesta.

	a. (10 + 0)* 10
	b. (10 + 0)*	Correcto: La ER tiene en cuenta las transiciones vacías. Se tiene en cuenta la precedencia y jerarquía de símbolos.
	c. (0+1+0*)
	d. (10 + 0)

Correcto

Puntos para este envío: 1/1.

Question10

Puntos: 1

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

Seleccione al menos una respuesta.

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

Parcialmente correcto

Puntos para este envío: 0.5/1.

Question11

Puntos: 1

Con los símbolos del alfabeto ∑ se forman cadenas, frases o palabras que se denotan por la letra ω. Algunas operaciones entre palabras son la concatenación y la inversa.

Que afirmaciones son válidas para estas propiedades y en algunas particularidades para el comportamiento de las cadenas o palabras (que se forman con los símbolos de un alfabeto) y que harían parte de un lenguaje.

Seleccione al menos una respuesta.

	a. En general (ω1 ω2 ) potencia R ≠ ω1 potencia R ω1 potencia R pero (ω1 ω2) potencia R = ω2 potencia R ω 1 potencia R	Correcto
	b. La Inversión (ω potencia R) consiste en una operación sobre palabras o cadenas que escribe al revés una palabra. La palabra resultante se denomina inversa.	Correcto
	c. La concatenación por ejemplo no tiene la propiedad conmutativa, es decir: ω1 ω2 ≠ ω2 ω 1 .
	d. El Palíndromo se puede definir como: (ω = ω potencia R ).

Parcialmente correcto

Puntos para este envío: 0.5/1.

Question12

Puntos: 1

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

Seleccione al menos una respuesta.

	a. Los AF (Autómatas Finitos) pueden considerarse como mecanismos aceptadores o reconocedores de palabras	Correcto
	b. Un AF es una máquina sin memoria externa; son los estados los que resumen de alguna forma la información procesada	Correcto
	c. La memoria de un Autómata Finito (AF), está dada por sus estados
	d. 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

Parcialmente correcto

Puntos para este envío: 0.8/1.

Question13

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 B corresponde a una representación válida del lenguaje que acepta el Autómata ”D”.	Incorrecto. La gramática no le corresponde a los autómatas dados
	b. 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.
	c. La Gramática D corresponde a una representación válida del lenguaje que acepta el Autómata “C”.
	d. La Gramática A corresponde a una representación válida del lenguaje que acepta los Autómatas “A” y “B”.

Parcialmente correcto

Puntos para este envío: 0.5/1.

Question14

Puntos: 1

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

Seleccione al menos una respuesta.

	a. Ambos son AFD y reconocen el mismo lenguaje	Incorrecto: Ambos autómatas son AFD y o reconocen el mismo lenguaje.
	b. 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.
	c. 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
	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.

Question15

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. 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
	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. ω = lambda ó cadena vacía y ω = 0 ; Son palíndromos
	d. Los símbolos de un alfabeto, definen el tipo de lenguaje a que pertenece.

Parcialmente correcto

Puntos para este envío: 0.5/1.

1

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 genera la cadena vacía
	b. 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
	c. La gramática solo genera cadenas de un símbolo y la cadena vacía
	d. La gramática no genera ningún lenguaje porque presenta más de un estado de aceptación o final.

Correcto

Puntos para este envío: 1/1.

Question2

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. 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.
	b. Los símbolos se añaden hacia abajo pero no pueden ser repetitivos. Por eso su derivación	Respuesta Incorrecta: Se adicionan de izquierda a derecha en un ciclo repetitivo.
	c. Los símbolos de entrada se añaden a los nodos en orden de izquierda a derecha
	d. Si no hay más símbolos que agregar, en un determinado nodo, no se evalúan más ramificaciones.

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.

Incorrecto

Puntos para este envío: 0/1.

Question3

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 a. Además el lenguaje generado por la gramática es estructurado por frases
	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”.	Incorrecto
	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	Incorrecto

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

Parcialmente correcto

Puntos para este envío: 0.5/1.

Question4

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. Sin importar si la pila está vacía o no, este siempre hará un movimiento.	Incorrecto: Se recuerda que un AP no puede realizar ningún movimiento si la pila está vacía.
	b. Una cadena en un AP será aceptada cuando llegue al estado final.	Incorrecto: La cadena será aceptada por vaciado de pila si después de leerse toda la cadena se llega a un estado con la pila vacía, independientemente del tipo de estado en el que se encuentre el AP
	c. Los caracteres a la mitad de la pila no son accesibles sin quitar antes los que están encima de ellos.	Correcto
	d. En un AP podemos modificar su “tope”, que es el extremo por donde entran o salen los caracteres

Parcialmente correcto

Puntos para este envío: 0.5/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. Un autómata finito no determinista de q estados y n símbolos puede tener a lo sumo n × q2 transiciones
	c. Un autómata finito determinista de q estados y n símbolos tiene n × q transiciones
	d. 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	Esta afirmación es válida

Incorrecto

Puntos para este envío: 0/1.

Question6

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

Parcialmente correcto

Puntos para este envío: 0.7/1.

1

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

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.

Question2

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

Incorrecto

Puntos para este envío: 0/1.

Question3

Puntos: 1

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

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

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

e: es una transición dada espontanea.

Seleccione al menos una respuesta.

	a. Las 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.
	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. 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.

Parcialmente correcto

Puntos para este envío: 0.5/1.

Question4

Puntos: 1

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

Seleccione una respuesta.

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

Incorrecto

Puntos para este envío: 0/1.

Question5

Puntos: 1

Las Gramáticas regulares pueden ser de dos formas: Lineales por la derecha y Lineales por la izquierda. También pueden ser ambiguas si existen dos árboles de derivación distintos para una misma palabra. Dada la Gramática G = {S, A}, T= {0,1} representada en los dos árboles de derivación siguiente, identifique el tipo de producciones y el lenguaje que generan:

Seleccione al menos una respuesta.

	a. El Árbol de Derivación A representa una gramática lineal por la izquierda y genera el lenguaje 0(10)*	Incorrecto: El Árbol de Derivación A representa una gramática lineal por la derecha
	b. El Árbol de Derivación A no es lineal, es ambigua (puede tener producciones por la izquierda y la derecha) y genera el lenguaje (10)*	Incorrecto: El Árbol de Derivación A representa una gramática lineal por la derecha
	c. El Árbol de Derivación B representa una gramática lineal por la izquierda y genera el lenguaje 0(10)*
	d. El Árbol de Derivación A representa una gramática lineal por la derecha.

Incorrecto

Puntos para este envío: 0/1.

Question6

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

Parcialmente correcto

Puntos para este envío: 0.5/1.

Question7

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. {a,b}	Incorrecto: Las cadenas no son aceptadas cuando se recorre la gramática.
	c. {aa, aaaa, bbba, ba, bba, baaa, baba}
	d. {baaaa, aaaaa, bba}

Incorrecto

Puntos para este envío: 0/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 → a | S → b (Palíndromos con símbolos impares)
	b. S → b (Palíndromos con símbolos pares)	Incorrecto
	c. S → lambda ( Palíndromos con símbolos pares )
	d. S → a (Palíndromos con símbolos pares)	Incorrecto

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 → alanda produce la cadena ω = baab (par).

Incorrecto

Puntos para este envío: 0/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. La pila no tiene límite en sus extremos. A diferencia de las MT que son cerradas por la izquierda.
	c. 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.
	d. Al igual que los AF, los AP tienen estados finales, que permiten distinguir cuando una palabra de entrada es aceptada

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

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 movimiento de la pila	Correcto
	b. A cada símbolo topo de la pila	Correcto
	c. A cada estado
	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.

1

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	Respuesta Incorrecta: Los lenguajes generados por una GIC son llamados Lenguajes Independientes del Contexto (LIC).
	b. En los árboles de derivación, no es necesario usar nodo raíz
	c. En un árbol de derivación cada nodo solamente puede tener otro hijo nodo
	d. 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.

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.

Incorrecto

Puntos para este envío: 0/1.

Question2

Puntos: 1

Indique cuál de las siguientes afirmaciones es verdadera

Seleccione una respuesta.

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

Incorrecto

Puntos para este envío: 0/1.

Question3

Puntos: 1

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

Seleccione al menos una respuesta.

	a. La ER que representa el lenguaje que acepta ese árbol de derivación es ab*c	Correcto
	b. 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
	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

Parcialmente correcto

Puntos para este envío: 0.7/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. Independiente del contexto no regular
	b. Regular	Correcto
	c. Decidible
	d. Estructurado por frases y no independiente del contexto

Correcto

Puntos para este envío: 1/1.

Question5

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 y el conjunto de los LIC son conjuntos independientes.
	b. El conjunto de los lenguajes regulares contiene al conjunto de los LIC.	Incorrecto: Los lenguajes generados por una GIC son llamados Lenguajes Independientes del Contexto (LIC).
	c. El conjunto de los LIC contiene al conjunto de los lenguajes regulares.
	d. El conjunto de los lenguajes regulares contiene al conjunto de las GIC.

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

Incorrecto

Puntos para este envío: 0/1.

Question6

Puntos: 1

Cual de las siguientes afirmaciones es VERDADERA

Seleccione una respuesta.

	a. En los arboles de derivación, los nodos raíces siempre derivan en dos ramas.
	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.	Correcto. En este caso es ambigua por cuanto puede tener varias soluciones
	c. Los lenguajes generados por una Gramática Independiente del Contexto son llamados Lenguajes Regulares
	d. En un árbol de derivación cada nodo solamente puede tener otro hijo nodo. De lo contrario se formaría otro nodo.

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

Correcto

Puntos para este envío: 1/1.

Question7

Puntos: 1

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

Seleccione una respuesta.

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

Incorrecto

Puntos para este envío: 0/1.

Question8

Puntos: 1

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

Seleccione una respuesta.

	a. Σ∗×Σ∗	Incorrecto
	b. (Σ*)*
	c. Σ×Σ
	d. Σ∪Σ

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

Incorrecto

Puntos para este envío: 0/1.

Question9

Puntos: 1

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

Seleccione una respuesta.

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

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

Incorrecto

Puntos para este envío: 0/1.

Question10

Puntos: 1

Dado el lenguaje L = {a, abb, ba, bbba, b} indique cuántas cadenas de longitud estrictamente menor que 3 hay en L*:

Seleccione una respuesta.

	a. 6
	b. 7	Correcto: L* ∩ {w ∈ L* | |w| < 3}= { λ, a,b,aa,ab,ba,bb}
	c. 4
	d. 5

Correcto

Puntos para este envío: 1/1.

Question11

Puntos: 1

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

siguientes afirmaciones son verdaderas

Seleccione al menos una respuesta.

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

Correcto

Puntos para este envío: 1/1.

Question12

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. Estructurado por frases (en sentido estricto).	Incorrecto
	b. Regular
	c. Independiente del contexto no determinista (en sentido estricto)
	d. Independiente del contexto determinista (en sentido estricto)

Incorrecto

Puntos para este envío: 0/1.

Question13

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→aRb, R→bRa, R→c.
	b. S → aSa, S→bSb, S→aRb, S→bRa, R→aRa, R→bRb, R→c.
	c. S → aSa, S→bSb, S→aRb, S→bRa, R→bRb, R→aRa, R→bRa, R→c.	Incorrecto: No genera cadenas wcv
	d. S → aSa, S→bSb, S→aRb, S→bRa, R→aRa, R→bRb, R→aRb, R→bRa, R→c.

Incorrecto

Puntos para este envío: 0/1.

Question14

Puntos: 1

Para simular el funcionamiento de un Autómata de Pila lo más recomendable es hacer primero:

Seleccione una respuesta.

	a. Simular su ejecución, listando las situaciones sucesivas en que se encuentra, mediante una tabla llamada “traza de ejecución	Correcto
	b. Simular su ejecución en una MT que se comporta de igual forma
	c. Simularlo en JFLAP con la cadena vacía Lambda para determinar si la pila inicia o no.
	d. Simular su ejecución en un software (podría ser como Visual Autómata Simulator) iniciando con una cadena no válida para determinar si el ciclo de la cinta inicia o no.

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.

Question15

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 –> 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 –> 00A –> 001S –> 0010 A –> 00100	Correcto: Ambas producciones aplican a la gramática con cadenas válidas como 0100 y 00100

Correcto

Puntos para este envío: 1/1.

1

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 representa con un diagrama de Moore el problema
	b. Si no existe un algoritmo total para determinar si la propiedad y objetivo del problema es verdadera.	Correcto: Los diagramas de Moore y de Transición o la forma como se representen los problemas, no tienen nada que ver con la determinación si es insoluble o no
	c. Si no existe un procedimiento efectivo para determinar si la propiedad es verdadera (no existe una Máquina de Turing MT).	Correcto: Los diagramas de Moore y de Transición o la forma como se representen los problemas, no tienen nada que ver con la determinación si es insoluble o no
	d. Si no se representa con una Tabla de transiciones el problema.	Incorrecto: Los problemas pueden formularse y representarse de muchas formas. Que tengan o no solución no tienen nada que ver con la forma como se representen. Va es en el sentido del análisis y la formulación del algoritmo

Correcto

Puntos para este envío: 1/1.

Question2

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. 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.
	b. Estado no cambia.	Incorrecto
	c. Todo movimiento del cabezal vacía la cinta y la inicializa en cero.	Correcto
	d. Imprime un símbolo en la cinta reemplazando el símbolo leído.

Parcialmente correcto

Puntos para este envío: 0.5/1.

Question3

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. Una MUT es funcional y eficiente tanto como una máquina real.
	d. La máquina de Turing, tiene mayor poder de cómputo que las reales, aunque resuelvan los mismos problemas.

Incorrecto

Puntos para este envío: 0/1.

Question4

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).
	b. La transición depende de los símbolos actuales de todas las cintas.	Correcto: Hace referencia al funcionamiento de una MT.
	c. Las transiciones se pueden hacer en varias cintas simultáneamente	Incorrecto
	d. La transición le asigna el carácter de entrada a las demás cintas	Incorrecto

Parcialmente correcto

Puntos para este envío: 0.5/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 de ruido
	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 AWGN

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

Parcialmente correcto

Puntos para este envío: 0.5/1.

1

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

Parcialmente correcto

Puntos para este envío: 0.8/1.

Question2

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

Question3

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 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.
	b. 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).
	c. 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
	d. La cinta superior contiene información correspondiente a la parte derecha de la cinta M a partir de un punto de referencia dado.

Parcialmente correcto

Puntos para este envío: 0.5/1.

Question4

Puntos: 1

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

Seleccione al menos una respuesta.

	a. El problema de “Halting” es el primer problema indecidible mediante maquinas de Turing	Correcto
	b. 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
	c. 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.
	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.

Question5

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.
	b. Para rechazar una cadena que no es aceptable, lo único que hay que hacer es evitar que se llegue a un estado final.	Correcto
	c. 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).
	d. 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

Parcialmente correcto

Puntos para este envío: 0.7/1.

Question6

Puntos: 1

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

Seleccione una respuesta.

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

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

Correcto

Puntos para este envío: 1/1.

Question7

Puntos: 1

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

Seleccione una respuesta.

	a. Una máquina de Turing cuyo estado inicial coincida con el estado de parada acepta toda cadena
	b. 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
	c. Es posible que un lenguaje sea estructurado por frases pero no exista ninguna máquina de Turing que se detenga exclusivamente cuando las cadenas escritas en su cinta pertenezcan al lenguaje	Incorrecto
	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.

Incorrecto

Puntos para este envío: 0/1.

Question8

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. 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
	b. Cualquier lenguaje puede ser reconocido por una máquina de Turing	Incorrecto
	c. Una máquina de Turing cuyo estado inicial coincida con el estado de parada acepta toda cadena
	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.

Parcialmente correcto

Puntos para este envío: 0.5/1.

Question9

Puntos: 1

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

Seleccione al menos una respuesta.

	a. No está permitido realizar ningún movimiento hacia la izquierda a partir de la celda del extremo izquierdo.	Correcto
	b. 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
	c. 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
	d. Una palabra de entrada a reconocer en una MT se escribe símbolo por símbolo en la cinta

Correcto

Puntos para este envío: 1/1.

Question10

Puntos: 1

Si iniciamos la máquina de Turing siguiente con la cadena yyxyxx

Seleccione una respuesta.

	a. La máquina acepta la cadena
	b. Hay una terminación anormal.
	c. La máquina solo acepta cadenas con números de símbolos pares	Incorrecto
	d. La máquina entra en un bucle y no termina nunca.

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”. Al llegar al halt, se detiene la operación de la MT, y se acepta la palabra de entrada. Así, en la MT no hay estados finales. En cierto sentido el halt sería entonces el único estado final, sólo que además detiene la ejecución.

Incorrecto

Puntos para este envío: 0/1.