AUTOMATAS Y LENGUAJES FORMALES CURSO COMPLETO 1
Puntos: 1
Luego de graduarse en matemáticas puras a sus 16 años en 1928, Turing descubrió los trabajos
de Albert Einstein. Luego en 1933 inicia sus estudios e los “principios lógicos matemáticos”
apoyado de:
Seleccione una respuesta.
a. Godfrey y Church Incorrecto: Recibió las enseñanzas de
Godfrey Harold Hardy, un respetado matemático que lo encaminó al estudio de las ciencias exactas.
b. Godel
c. Bertrand Russell
d. Neumann
Biografía de Alan Turing
Incorrecto
Puntos para este envío: 0/1.
Question2
Puntos: 1
En Octubre de 1950, Alan Turing hizo estudios más abstractos y trató el tema de la Inteligencia
artificial. Para ello propuso un experimento que hoy se conoce como el “test de Turig”. Que
consiste básicamente en: (seleccione la verdadera).
Seleccione una respuesta.
a. Procedimientos para evaluar decisiones lógicas de una
máquina.
b. Prueba de error que determina cuando un problema tiene solución o
no.
c. “Método” para determinar si una máquina puede pensar. Correcto: El Test de Turing nace como
un método para determinar si una máquina puede pensar.
d. Método para evaluar el rendimiento y capacidad de una maquia.
“Poder de procesamiento”
Biografía de Alan Turing
Correcto
Puntos para este envío: 1/1.
Question3
Puntos: 1
Grandes fueron sus aportes a la ciencia y la matemática y en muchas áreas de cocimiento
ahondó. Pero el principal interrogante por el que se conoce Alan Turing fue:
Seleccione una respuesta.
a. El hecho de que: debe existir al menos en principio algún método definido, o proceso mediante el cual toda cuestión
matemática pueda ser demostrada?
b. La demostración de toda cuestión matemática no debe obedecer a la lógica fundamental y no necesariamente debe
comprobarse para que un problema tenga solución.
c. El hecho de que: debe existir al menos y en principio una
solución única para cualquier problema matemático.
Incorrecto: era el hecho de que: debe existir al menos en principio algún método definido, o proceso mediante el cual toda cuestión matemática pueda ser demostrada?
d. Un problema matemático tiene “finitas soluciones”. Si son
infinitas es porque el problema puede ser insoluble.
Biografía de Alan Turing
Incorrecto
Puntos para este envío: 0/1.
Question4
Puntos: 1
Turing era ateo. Reafirmó sus conceptos superficiales y concretos en los que todos los fenómenos incluyendo
el funcionamiento del cerebro humano, deben ser materialistas. Pese a ello siguió creyendo en la
supervivencia del espíritu después de la muerte. Estas posiciones fueron dadas a raíz de:
Seleccione una respuesta.
a. A empezar estudios del cerebro humano y descubrir que podría asociarse al funcionamiento de una máquina mecánica y que no podría haber sido
creación de Dios.
b. Al ver el horror de la segunda erra mundial en la que participó como agente encubierto descifrando códigos e interceptando comunicaciones del ejército
Alemán.
c. Dada la muerte de Christopher Morcom, quién fue el primer amor. Morcom murió repentinamente el 13 de
febrero de 1930 .
Correcto: Morcom murió muy joven de tuberculosis bovina al beber leche contaminada. Él fue quien a motivación para seguir con sus estudios, y entra en un vital periodo de riqueza intelectual.
d. En 1928, con dieciséis años, al descubrir e
interpretar los trabajos de Albert Einstein
Biografía de Alan Turing
Correcto
Puntos para este envío: 1/1.
Question5
Puntos: 1
En 1936, Alonzo Churh fue director de tesis del trabajo de grado doctoral de Alan Turing quién le
siguió sus pasos “estudios” en lógica y computabilidad. El nombre del trabajo doctoral fue
“Sistemas de lógica basada en ordinales sobre números computables”. Este tema ya lo había
tratado Davd Gilbert en 1928. Este trabajo es el que hoy en día ha llevado a:
Seleccione una respuesta.
a. Definir los conceptos modernos de lógica
b. Determinar las teorías de números ordinales y de algoritmos.
Incorrecto
c. Establecer las nociones de lo que hoy se conoce como la
“Máquina de Turing”
d. Establecer los principios de la criptografía.
Biografía de Alan Turing
Incorrecto
Puntos para este envío: 0/1.
Question6
Puntos: 1
Para comprender y empezar a dar respuesta al Entscheidungsproblem (en castellano: problema
de decisión), Alan Turing analizó aspectos como:
Seleccione al menos una respuesta.
a. Abordando la definición del concepto "método", y para ello analizó que era lo que hacía una persona para transformar un proceso metódico, y buscar una forma de hacer esto
mecánicamente
b. Asoció el proceso de forma mecánica en la que se podían transformar operaciones elementales previamente definidas en
símbolos y estos posteriormente escribirlos en una cinta
c. Asoció el problema llevándolo a definir un conjunto de instrucciones de forma metódica para ser ejecutadas de manera mecánica. Es decir abordó el concepto de “Máquina de Turing”
Parcialmente correcto: En Agosto de 1936 presenta el concepto final de la Maquina de Turing, y se convierte en el fundamento de
en la que hay un conjunto de posibilidades infinitas en la que cada una se corresponde a un “método claro y definido” o a un
“algoritmo”.
las teorías modernas para la programación de máquinas electrónicas. Su trabajo aporta un concepto práctico de gran significancia: la idea de la Maquina de Turing Universal. El concepto de "LA MAQUINA DE TURING" se conoce también como "LA FORMULA" o "LA ECUACIÓN"
d. Alan Turing lo que realmente analizó y logró definir fue un
algoritmo.
Biografía de Ala Turing
Parcialmente correcto
Puntos para este envío: 0.3/1. 1
Puntos: 1
La “Teoría de Lenguajes”, define bloques constructores de lenguaje. El
bloque más sencillo es el alfabeto. De las siguientes afirmaciones cuales
definen o son verdaderas con respecto a un “alfabeto”:
Seleccione al menos una respuesta.
a. { α1 , α2 ,..... α n } Es un ejemplo de alfabeto
b. Los símbolos pueden ser nombres. Los alfabetos
son finitos.
Correcto: Lenguaje Formal: Un alfabeto es un conjunto finito de símbolos. De esta definición se debe resaltar lo siguiente. (1) Los alfabetos son finitos. (2) Por símbolo no se está haciendo referencia a un sólo carácter. Los símbolos pueden ser nombres
c. Por símbolo, se está haciendo referencia a un
solo carácter.
Incorrecto: Por símbolo no se está haciendo referencia a un sólo carácter. Los símbolos pueden ser nombres
d. Los alfabetos están compuestos por cadenas. Ya sean aceptadas o no. Ejemplo el alfabeto del español latino: Una cadena válida es {sistemas}.
Una cadena no aceptada es {temas}.
Parcialmente correcto
Puntos para este envío: 0.5/1.
Question2
Puntos: 1
La minimización de Autómatas, es un ejercicio común en Automatización.
Identifique su concepto básico y aplicabilidad:
Seleccione una respuesta.
a. La minimización se aplica a los AFD y consiste en obtener un AFD equivalente a uno dado que tenga el
menor número de estados posibles.
Correcto: La minimización se basa en el tratamiento de estados "obtener el menor número de ellos" de forma equivalente.
b. Un autómata se puede minimizar siempre y cuando el autómata dado no acepte cadenas
vacías.
c. La minimización se aplica a los AFND y consiste en obtener un autómata equivalente que tenga el
menor número de transiciones posibles
d. En la minimización de autómatas, el número de estados o de relaciones debe ser equivalente en
cantidad inferior al dado.
Correcto
Puntos para este envío: 1/1.
Question3
Puntos: 1
Acerca de los autómatas finitos no deterministas (AFND), cuáles apreciaciones
son verdaderas cuando se analiza su comportamiento para aceptar lenguajes:
Seleccione al menos una respuesta.
a. Un autómata finito no determinista (AFND) se puede convertir a un AFD y solo será válido si aceptan el
mismo lenguaje.
Correcto: Corresponde a la condición de determinismo.
b. Un autómata finito no determinista (AFND) acepta una cadena cuando es posible que su análisis deje a la
máquina en un estado de aceptación.
c. Un autómata finito no determinista (AFND) solo puede
utilizarse para aceptar lenguajes finitos.
d. Nunca se puede afirmar con seguridad que un autómata finito no determinista (AFND) acepta una
cadena.
Parcialmente correcto
Puntos para este envío: 0.5/1.
Question4
Puntos: 1
Sea el vocabulario {a,b} y la expresión regular aa*bb* Indique cuales
cadenas que se relacionan a continuación son válidas para esa ER
Seleccione una respuesta.
a. {ab, aab, aab, a, aa,bb}
b. {a, b, ab, ba, aab, bba, aaab}
c. {ab, aab, aaab, abbb, abb, aa,bb} Correcto: El Lenguaje que se describe es L={cadenas
que comienzan por una a y continuan con varias o ninguna a, y siguen con b y continuan con varias o ninguna b}
d. {ba, ab, b, a}
Correcto
Puntos para este envío: 1/1.
Question5
Puntos: 1
Del tratado y temática de Autómatas, los principales objetivos de las ciencias de la computación es:
Seleccione al menos una respuesta.
a. La solución de problemas por medio de un
computador.
b. Proporcionar mecanismos para analizar
algoritmos, construir y expresar programas
c. Reducir problemas en otros más pequeños.
d. Traducir lenguajes de máquina a programas
escritos en lenguajes de alto nivel.
Incorrecto: estas son tareas de máquina que surgen del análisis formulación de tratados como los de los algoritmos
Incorrecto
Puntos para este envío: 0/1.
Question6
Puntos: 1
Los Autómatas finitos no determinísticos (AFND) es una quíntupla donde todos los componentes son como
en los AFDs, estos autómatas aceptan exactamente los mismos lenguajes que los autómatas determinísticos,
pero cuentan con una diferencia con relación a los AFD como es.
Seleccione una respuesta.
a. El conjunto finito de estados.
b. El estado inicial.
c. El alfabeto de entrada
d. La función de transición. Correcto: Solo la función de transición puede
diferenciar los AFD de los AFND. Las demás opciones pueden ser comunes a ambos tipos de autómatas y válidas.
Correcto
Puntos para este envío: 1/1.
1
Puntos: 1
Analice el siguiente Autómata y determine cuáles apreciaciones son válidas en
su análisis:
Seleccione al menos una respuesta.
a. La función de transición define para cada posible
combinación (0,1) un estado nuevo.
Incorrecto
b. La función de transición puede no estar definida para alguna combinación (0,1) y, por el contrario, puede definir
para otras combinaciones (0,1) más de un estado.
c. Es un autómata no determinístico (AFND), con un conjunto finito de estados y símbolos de entrada, un estado inicial, un conjunto de estados finales, y una función de transición de
estados.
d. Es un autómata determinístico (AFD), con un conjunto finito de estados y símbolos de entrada, un estado inicial, un conjunto de estados finales, y una función de transición de
estados.
Incorrecto. Es un AFND
Incorrecto
Puntos para este envío: 0/1.
Question2
Puntos: 1
Cuáles afirmaciones son válidas cuando se trata de analizar el funcionamiento de los Autómatas Finitos (AF):
Seleccione al menos una respuesta.
a. En una máquina de estados finitos, la función de transición
almacena los datos de entrada del Autómata.
b. Los AF son máquinas de memoria limitada. Correcto: Los estados son el único medio de
que disponen los AF para recordar los eventos que ocurren (por ejemplo, qué caracteres se han leído hasta el momento); esto quiere decir que son máquinas de memoria limitada.
c. Los estados son el único medio de que disponen los AF para recordar los eventos que ocurren (por ejemplo que
caracteres se han leído hasta el momento).
Correcto: Los estados son el único medio de que disponen los AF para recordar los eventos que ocurren (por ejemplo, qué caracteres se han leído hasta el momento); esto quiere decir que son máquinas de memoria limitada.
d. Los AF son máquinas de memoria amplia por ser
máquinas abstractas (no reales).
Correcto
Puntos para este envío: 1/1.
Question3
Puntos: 1
Dado el siguiente “Autómata Finito” cuyo diagrama de transición corresponde al de la siguiente figura,
determine cual afirmación es válida cuando se analiza la ejecución del autómata.
Seleccione una respuesta.
a. El conjunto de cadenas que es capaz de reconocer este autómata es. {Ø, Øb, bb, bbb,
bbbb, …}
b. El conjunto de cadenas que es capaz de reconocer este autómata es. {b, bb, bbb, bbbb,
…}
Incorrecto: “bbbb” no es aceptada, ni tampoco el símbolo vacío.
c. El conjunto de cadenas que es capaz de
reconocer este autómata es {b, bb, bbb}
d. El conjunto de cadenas que es capaz de
reconocer este autómata es. {b}
Incorrecto
Puntos para este envío: 0/1.
Question4
Puntos: 1
Una cadena válida para el Autómata siguiente es:
Seleccione una respuesta.
a. xxxxzxzxzxzx
b. xzzxzxzx Incorrecto: Al recorrer la cadena no
llega al estado final o halt
c. xxxzxx
d. xzxxxxzxzzx
Incorrecto
Puntos para este envío: 0/1.
Question5
Puntos: 1
Dado el siguiente autómata, las apreciaciones verdaderas en expresiones
regulares (ER) y cadenas aceptadas son:
Seleccione al menos una respuesta.
a. (x + y)*(x+y) acepta la cadena {xy}. Correcto: Se parte que la ER de la
izquierda para todas las opciones es válida y expresa el lenguaje que representa el autómata. Acepta la cadena xy y rechaza la cadena vacía.
b. (x + y)*(x+y) rechaza la cadena vacía Correcto: Rechaza la cadena vacía.
c. (x + y)*(x+y) acepta la cadena vacía y el autómata es
determinista
d. (x + y)*(x+y) es igual a (x* x U y y*) Incorrecto: Esta asociación no es válida
para la ER que representa el autómata.
Correcto
Puntos para este envío: 1/1.
Question6
Puntos: 1
Dado el Autómata con la siguiente tabla de transición, identifique las cadenas
que son válidas para el lenguaje que acepta
Seleccione una respuesta.
a. Es un AFND y acepta cualquier cadena que inicie
con cero (0)
b. Solo acepta cadenas vacías (lambda). Incorrecto: Es un AND de landa transiciones.
Aceptará las cadenas que inicien con un orden jerárquico de números (es decir de menor a mayor, siendo válida la repetición de los mismos), Ej 012, 12 pero nunca 210, 20 entre otros.
c. {101, 210, 20,110, 200}
d. {22, 0,1,001122, 12, 012, 022}
Incorrecto
Puntos para este envío: 0/1.
Question7
Puntos: 1
La expresión regular que se asocia la siguiente autómata es:
Seleccione una respuesta.
a. r = (1)* + (0) + lambda
b. r = (10 + 0) * Correcto: Las cadenas que tengan varios unos
consecutivos son rechazadas
c. r = (10) * + 1*
d. r = (1 + 0) + 1*
Correcto
Puntos para este envío: 1/1.
Question8
Puntos: 1
Si se considera un autómata finito M con transiciones lambda que
reconoce el lenguaje L: De la relación entre determinista y no
determinista de los autómatas, y el comportamiento de las cadenas vacías (lambda), es válido afirmar
Seleccione al menos una respuesta.
a. Un autómata finito con transiciones lambda es un autómata
no determinista.
Correcto: Las cadenas vacías lambda son aceptadas y suelen presentarse en AFND.
b. Las transiciones lambda solo son aceptadas en la
descripción de las gramáticas.
c. Siempre existe un autómata finito determinista que reconoce un lenguaje reconocido por un autómata finito no
determinista.
d. No existe un autómata finito sin transiciones (lambda) que
reconozca L.
Parcialmente correcto
Puntos para este envío: 0.5/1.
Question9
Puntos: 1
Teniendo en cuenta las clases de lenguajes propuestos por la jerarquía de Chomsky, es común o aplica
afirmar:
Seleccione una respuesta.
a. Los “Lenguajes Regulares” es la jerarquía más alta y compleja. Un ejemplo de lenguaje regular es el conjunto
de todos los números binarios.
b. La mayoría de los lenguajes de programación son
“Lenguajes Libres de Contexto”.
Correcto: Los lenguajes libres de contexto incluyen a los lenguajes regulares. Los lenguajes regulares son la clase más pequeña dentro de la jerarquía de Chomsky. Los lenguajes recursivamente enumerables incluyen a los lenguajes libres de contexto.
c. Los “Lenguajes Libres de Contexto” no incluyen a los
“Lenguajes regulares”.
d. Los “Lenguajes Recursivamente Enumerables” solo
incluye a los “Lenguajes Regulares”.
Correcto
Puntos para este envío: 1/1.
Question10
Puntos: 1
Si ∑ es un alfabeto, se le llama ∑ (potencia n) al conjunto de todas las palabras de longitud n sobre ∑.
Identifique las notaciones de conjuntos válidas para la creación de palabras sobre el alfabeto ∑
Seleccione al menos una respuesta.
a. ∑ (potencia +) = Conjunto de todas las cadenas positivas
excepto la vacía
Incorrecto: Conjunto de todas las cadenas excepto la vacía
b. ∑ (potencia 0) = {lambda} Conjunto cuyo único elemento es
la palabra vacía.
Correcto: La longitud de una cadena ω que se denota como |ω| es el número de letras que aparecen en ω. A la cadena que no tiene símbolos o que es lo mismo decir que tiene longitud cero, se le llama palabra vacía. Si ∑ es un alfabeto, se le llama ∑ n al conjunto de todas las palabras de longitud n sobre ∑. la estrella * genera el conjunto de todas las cadena de cualquier longitud sobre ∑. Si se analiza ∑ + esta representa al conjunto de todas las cadenas sobre el alfabeto ∑ excepto la vacía.
c. ∑ (potencia 0) = Conjunto de todas las cadenas sobre el
alfabeto ∑ excepto la vacía.
d. ∑ *= Conjunto de todas las cadenas de cualquier longitud
sobre ∑
Correcto: La longitud de una cadena ω que se denota como |ω| es el número de letras que aparecen en ω. A la cadena que no tiene símbolos o que es lo mismo decir que tiene longitud cero, se le llama palabra vacía. Si ∑ es un alfabeto, se le llama ∑ n al conjunto de todas las palabras de longitud n sobre ∑. la estrella * genera el conjunto de todas las cadena de cualquier longitud sobre ∑. Si se analiza ∑ + esta representa al conjunto de todas las cadenas sobre el alfabeto ∑ excepto la vacía.
Correcto
Puntos para este envío: 1/1. 1
Puntos: 1
Dentro de la jerarquía y clasificación de los lenguajes (Chomsky) identifique que asociaciones
están erradas.
Seleccione al menos una respuesta.
a. Una gramática regular o de tipo 3, puede generar
Autómatas finitos (AF)
b. Los lenguajes que no poseen restricciones o de tipo 0, son reconocidos mediante Autómatas Finitos No
Deterministas (AFND)
Correcto: esta afirmación está errada. Los lenguajes que no poseen restricciones o de tipo 0, son reconocidos mediante Máquinas de Turing (MT)
c. Los lenguajes libres de contexto o de tipo 2, pueden
ser generados por los autómatas de pila (AP)
d. Los lenguajes regulares pueden ser pueden ser
descritos mediante expresiones regulares (ER)
Esta afirmación es verdadera. Un lenguaje puede ser descrito mediante una expresión regular (expresar de forma compacta cómo son todas las cadenas de símbolos que le pertenecen).
Parcialmente correcto
Puntos para este envío: 0.3/1.
Question2
Puntos: 1
Las condiciones mínimas para poder describir un Autómata Finito Determinístico (DFA) son:
Seleccione al menos una respuesta.
a. Identificando el estado inicial y los estados finales. Correcto: Un autómata puede describirse
dando la lista de sus estados, el alfabeto, el estado inicial, los estados finales, y la función transición.
b. Identificando el alfabeto. Correcto: Un autómata puede describirse
dando el alfabeto.
c. Identificando la función de transición. Correcto: Un autómata puede describirse
dando la lista de sus estados, el alfabeto, el estado inicial, los estados finales, y la función transición.
d. Dando la lista de sus estados. Correcto: Un autómata puede describirse
dando la lista de sus estados, el alfabeto, el estado inicial, los estados finales, y la función transición. Esta función se puede describir usando notación usual para definir funciones o usando una matriz, con una fila por cada estado y una columna por cada símbolo del alfabeto. Todas las condiciones son necesarias para describir el autómata.
Correcto
Puntos para este envío: 1/1.
Question3
Puntos: 1
Las siguientes cadenas:
{Lambda,aaa, bb, bbb, aabb, aba, abaaa, abbaa}
son generadas expresadas por la ER
Seleccione una respuesta.
a. (a + b ) *
b. (a.b)*
c. (a,b)*
Incorrecto
d. ( a | b)*
Incorrecto
Puntos para este envío: 0/1.
Question4
Puntos: 1
Para el siguiente autómata, identifique cuál es la Expresión Regular (ER) que
mejor lo representa:
Seleccione una respuesta.
a. (ab+ba) + a
b. (ab + aba)* Correcto: Aceptará cadenas que empiecen por una
a seguida de una b incluyendo la cadena vacía.
c. a +(ab)*
d. ab +(ab)*
Correcto
Puntos para este envío: 1/1.
Question5
Puntos: 1
Dado el siguiente autómata, analice sus características verdaderas en comportamiento, diseño y lenguajes
de aceptación:
Seleccione al menos una respuesta.
a. Es Regular y cualquier cadena contiene al menos
un cero.
Incorrecto: Es regular pero las cadenas no poseen esas características.
b. Es un autómata finito determinista (AFD).
c. Es Regular e independiente del contexto por lo
que contiene más de un estado Halt.
d. Es Regular.
Incorrecto
Puntos para este envío: 0/1.
Question6
Puntos: 1
Este lenguaje:
L (G) = {a (potencia n) b (potencia n) / n>=1}
Es generado por la gramática:
Seleccione una respuesta.
a. S ---> ab| Sab Incorrecto
b. S ---> aSb | ab
c. S ---> Sab | aSb
d. S ---> Sa| Sb
Incorrecto
Puntos para este envío: 0/1.
Question7
Puntos: 1
Dado los siguientes dos autómatas: determine cuáles afirmaciones son válida
Seleccione al menos una respuesta.
a. El autómata A es un AFD pero no reconoce el mismo
lenguaje que el autómata B
Correcto: Ambos autómatas son AFD y o reconocen el mismo lenguaje
b. Ambos son AFD y reconocen el mismo lenguaje
c. El autómata B es un AFD pero no reconoce el mismo
lenguaje que el autómata A
Correcto: Ambos autómatas son AFD y o reconocen el mismo lenguaje.
d. El autómata B es un AFND (además posee dos estados de aceptación) y su ER es la misma que la del
Incorrecto: Ambos autómatas son AFD y o reconocen el mismo lenguaje.
autómata A.
Correcto
Puntos para este envío: 1/1.
Question8
Puntos: 1
Dada la siguiente gramática con las siguientes producciones,
S --> ab
SaSb
que derivaciones son válidas al usar sus reglas:
Seleccione al menos una respuesta.
a. Bbaa
b. aabb
Correcto
c. ab
d. Ba
Parcialmente correcto
Puntos para este envío: 0.5/1.
Question9
Puntos: 1
Analice e identifique cuáles afirmaciones son válidas con referencia al diseño del siguiente
autómata:
Seleccione una respuesta.
a. Es un autómata AFND que acepta el lenguaje (ab)* U (aba)* U
a*b*
b. Es un autómata finito no determinista que acepta la cadena
{ababaab}
c. Es un AFND que acepta el lenguaje (ab U aba)*
Correcto
d. Es una autómata AFND cuya ER es: (ababa)*
Correcto
Puntos para este envío: 1/1.
Question10
Puntos: 1
Dado el siguiente autómata: Cambie los símbolos del alfabeto asociando a = 0 y b =1 . Para las
siguientes opciones,(que están en base 10 o decimal), conviértalas a base 2 (binario) y recorra
el autómata e identifique cuál número acepta el autómata.
Seleccione una respuesta.
a. 205
b. 182 Correcto: equivale a recorrer la cadena 10110110 (cadenas que terminen en
cero “0” o en la asociación del autómata que terminen en “a”)
c. 253
d. 73
Correcto
Puntos para este envío: 1/1.
Question11
Puntos: 1
Para el siguiente Autómata, asocie la expresión regular que lo identifica:
Seleccione una respuesta.
a. (0+1+0*)
b. (10 + 0)
c. (10 + 0)* 10
d. (10 + 0)* Correcto: La ER tiene en cuenta las
transiciones vacías. Se tiene en cuenta la precedencia y jerarquía de símbolos.
Correcto
Puntos para este envío: 1/1.
Question12
Puntos: 1
Sea el autómata A = (∑, Q, f, q1, F) donde:
∑ ={a,b}, Q = {q1, q2, q3, q4}, F= { q4} y la función f vienen dada por la siguiente tabla:
Determine qué aspectos son válidos para el autómata
Seleccione al menos una respuesta.
a. El lenguaje reconocido por el autómata es: a (b*b |
a*b) a*
Correcto: Es un AFND. El lenguaje que reconoce es : a (b*b | a*b) a* o también a (b* | a* ) ba* para efectos de mejor comprensión, hay que recrear o realizar el autómata mediante un diagrama de Moore
b. Es un Autómata Finito Determinístico (AFD)
c. El lenguaje reconocido por el autómata es: a (b* | a* )
ba*
Correcto: Es un AFND. El lenguaje que reconoce es : a (b*b | a*b) a* o también a (b* | a* ) ba* para efectos de mejor comprensión, hay que recrear o realizar el autómata mediante un diagrama de Moore
d. Es un Autómata Finito Determinístico con lambda
transiciones
Correcto
Puntos para este envío: 1/1.
Question13
Puntos: 1
Se pueden generar palíndromos (cadenas ω) sobre el alfabeto ∑ = {0,1}. Evidentemente este lenguaje tiene
infinitas cadenas
Selecciones las afirmaciones válidas con referencia al anterior postulado.
Seleccione al menos una respuesta.
a. Los símbolos de un alfabeto, definen el tipo de lenguaje
a que pertenece.
b. Los palíndromos son una excepción de los lenguajes regulares y no hacen parte de la jerarquía de
Chomsky
Incorrecto: Los palíndromos tienen regularidades. Son lenguajes de tipo 3
c. Existe un lenguaje denominado el lenguaje vacío que es un conjunto vacío y se denota por {Ø}. El lenguaje vacío no debe confundirse con un lenguaje que contenga
una sola cadena.
Correcto
d. ω = lambda ó cadena vacía y ω = 0 ; Son
palíndromos
Parcialmente correcto
Puntos para este envío: 0.5/1.
Question14
Puntos: 1
Dado el siguiente autómata Finito, es válido afirmar:
Seleccione al menos una respuesta.
a. La Er que lo representa es: (ab*a)*
b. La ER que lo representa: (b+ab*a)*ab*
Correcto
c. La ER que lo representa es: (b+ab*a)*
d. La ER que lo representa es: (b*ab*a)*b*ab*
Parcialmente correcto
Puntos para este envío: 0.5/1.
Question15
Puntos: 1
Sean dos lenguajes L1 y L2 definidos sbre el mismo alfabeto ∑, la operación que se representa a
continuación es:
L = L1L2 = {xy / x pertenece L1 Ʌ y pertenece L2}
Seleccione una respuesta.
a. Operación cerrada de dos lenguajes
b. Concatenación de lenguajes Correcto: La concatenación de ambos lenguajes
estará formada por todas las palabras obtenidas al concatenar una palabra cualquiera de L1 con
otra de L2.
c. Unión de lenguajes
d. Asociación de lenguajes
Correcto
Puntos para este envío: 1/1.
1
Puntos: 1
Dado el alfabeto ∑= {a,b}, identifique cuál afirmación es falsa.
Seleccione una respuesta.
a. La expresión regular b*a*b* representa al lenguaje
de las cadenas que pueden o no tener “a”
b. La expresión regular b*(ab*ab*)* representa al lenguaje de las cadenas con un número par de letras
a
c. La expresión regular b*ab* (ab*ab*)* representa al lenguaje de las cadenas con un número impar de
letras a
d. La expresión regular (b*ab*ab*a) * representa al lenguaje de las cadenas con un número múltiplo de 3
de letras “a”
Esta afirmación (ER) es errada para las cadenas que dice generar.
Correcto
Puntos para este envío: 1/1.
Question2
Puntos: 1
Dada la Gramática S→aS; S→aSbS; S→.
Indique cuáles de las siguientes afirmaciones no corresponden al desarrollo de
la misma o al tipo de cadenas o palabras ω que pueda generar.
Seleccione al menos una respuesta.
a. Para cualquier prefijo de una cadena generada por la gramática se verifica que el número de letras a es mayor o igual al número de letras b. Prefijo de una cadena ω es toda cadena no vacía x para la que existe una cadena u tal que
ω=xu
b. Cualquier cadena ω generada por la gramática contiene una subcadena no vacía donde algunas veces el número de letras a es igual al número de letras
b.
Correcto: Correcto: Las cadenas ω van a empezar por a. El lenguaje generado por la gramática es estructurado por frases. Solo algunas cadenas generadas contiene igual número de a´s que de b´s.
c. Las cadenas que acepta la gramática siempre van a empezar por b. Además el lenguaje generado por la gramática es
“no es estructurado por frases”.
d. Las cadenas ω que acepta la gramática siempre van a empezar por a. Además el lenguaje generado por la
gramática es estructurado por frases
Correcto: Correcto: Las cadenas ω van a empezar por a. El lenguaje generado por la gramática es estructurado por frases. Solo algunas cadenas generadas contiene igual número de a´s que de b´s.
Las gramáticas cuyas reglas son de la forma A ---> aB o bien A ---> a, donde A y B son variables, y a es un
caracter terminal. A estas gramáticas se les llama regulares.
Correcto
Puntos para este envío: 1/1.
Question3
Puntos: 1
Con referencia las gramáticas de Tipo 2, que aspectos válidos hacen referencia a la forma de
generar lenguajes de tipo 2 y su comportamiento y descripción:
Seleccione al menos una respuesta.
a. Los autómatas de pila aceptan exactamente los LLC (Lenguajes
Libres de Contexto).
Correcto
b. Si M es un AP, entonces L(M) es un LLC
Correcto
c. Si L es un LLC, entonces hay un AP M tal que L(M) = L
Correcto
d. Las producciones son de la forma: A - aa Dado que hay un
carácter de lectura y uno de escritura
Correcto
Puntos para este envío: 1/1.
Question4
Puntos: 1
En una Gramática Regular, un componente de la Cuadrupla que la compone, es
el Alfabeto. Este esta caracterizado como:
Seleccione una respuesta.
a. Un alfabeto infinito y no vacío de símbolos terminales
b. Un alfabeto inicializado con lambda como cadena válida
c. Un alfabeto no vacío de símbolos terminales
Correcto
d. Un alfabeto regular (o sea de tipo 3 según Chomsky)
Una gramática regular G es una cuádrupla G = (E, N, S, P), donde:
E : alfabeto (no vacío) de símbolos terminales
Correcto
Puntos para este envío: 1/1.
Question5
Puntos: 1
Que aspectos son válidos cuando se analiza el funcionamiento de los autómatas de pila (AP).
Seleccione al menos una respuesta.
a. Los APND y los APD no aceptan los mismos lenguajes.
b. Los autómatas de pilas no tienen metodología tan generalmente aplicable, solo se debe tener una estrategia clara para el manejo de
la pila.
c. Para verificar el funcionamiento del autómata, podemos simular su ejecución listando las situaciones sucesivas en que se encuentran
mediante una tabla que llamaremos traza de ejecución.
Correcto
d. Cuando desarrollamos un autómata de pilas tenemos que repetir
lo que quiere ser recordado entre los estados y las pilas.
Correcto
Parcialmente correcto
Puntos para este envío: 0.5/1.
Question6
Puntos: 1
Para u AP, la función de transición también se puede representar mediante un diagrama donde
los nodos representan los estados y los arcos transiciones, Dada la siguiente transición como se
muestra en la figura, identifique las acciones correctas que haría el movimiento de la pila.
Seleccione una respuesta.
a. El estado actual es q0. La cabeza lectora apunta al símbolo “lambda”. El recorrido de la pila es de izquierda a derecha. El tope de la pila es X que no se modifica al cambiar al nuevo estado q1 y avanzar la cabeza
lectora.
b. El estado actual es q0. La cabeza lectora apunta al símbolo “a”. El tope de la pila es “a” como primer símbolo a leer que se va a sustituir por lambda al cambiar al nuevo
estado q1 y avanzar la cabeza lectora.
c. El estado actual es q0. La cabeza lectora apunta al símbolo “a”. El tope de la pila es X que se va a sustituir por lambda al cambiar al nuevo estado q1 y avanzar la cabeza
lectora.
Correcto
d. El estado actual es q0. La cabeza lectora apunta al tope X que es donde inicia la lectura del símbolo “a” que entra al
pasar al estado q1 y sustituir lambda por X.
Correcto
Puntos para este envío: 1/1. 1
Puntos: 1
Del diseño y naturaleza de los autómatas de pila (PDA), es válido afirmar:
Seleccione una respuesta.
a. A la hora de diseñar un AP tenemos que repartir lo que requiere ser “recordado” entre los estados y la pila. Distintos diseños para un mismo problema pueden tomar decisiones diferentes en cuanto a que
recuerda cada cual
Respuesta Correcta: Aunque en el caso de los AP no hay metodologías tan generalmente aplicables como era el caso de los autómatas finitos, siguen siendo válidas las ideas básicas del diseño sistemático, en particular establecer claramente qué es lo que “recuerda” cada estado del AP antes de ponerse a trazar transiciones a diestra y siniestra.
b. Un Autómata de Pila al igual que una Máquina de Turing o un Autómata Finito, su definición básica es
de naturaleza no determinista
c. Un autómata de pila no puede hacer las funciones de "contador" ya que sus recorridos varían en la cinta y lo que le importa a esta automatización es el estado
final y la salida del dato.
d. Para poder simular un autómata de Pila se debe tener en cuenta: Las columnas de una traza de ejecución para un AP son: el estado en que se encuentra el autómata, lo que ha leido hasta el momento o estado actual al inicio de la simulación, y
el contenido de la memoria al final del recorrido.
A la hora de diseñar un AP tenemos que repartir lo que requiere ser
“recordado” entre los estados y la pila. Distintos diseños para un mismo
problema pueden tomar decisiones diferentes en cuanto a que recuerda cada
cual.
Correcto
Puntos para este envío: 1/1.
Question2
Puntos: 1
Para que una palabra de entrada sea aceptada en un AP se deben cumplir las
condiciones siguientes:
Seleccione al menos una respuesta.
a. La palabra de entrada se debe haber agotado
(consumido totalmente).
Correcto; para que una palabra de entrada sea aceptada en un AP se deben cumplir todas las condiciones siguientes: 1. La palabra de entrada se debe haber agotado (consumido totalmente). 2. El AP se debe encontrar en un estado final. 3. La pila debe estar vacía.
b. El AP se debe encontrar en un estado final. Correcto: para que una palabra de entrada
sea aceptada en un AP se deben cumplir todas las condiciones siguientes: 1. La palabra de entrada se debe haber agotado (consumido totalmente). 2. El AP se debe encontrar en un estado final. 3. La pila debe estar vacía.
c. La pila debe estar vacía. Correcto: la pila debe estar vacía.
d. La pila debe tener lambda como elemento final.
A la hora de diseñar un AP tenemos que repartir lo que requiere ser “recordado” entre los estados y la pila.
Distintos diseños para un mismo problema pueden tomar decisiones diferentes en cuanto a qué recuerda
cada cual.
Correcto
Puntos para este envío: 1/1.
Question3
Puntos: 1
Los errores más comunes al diseñar gramáticas (GLC) son:
Seleccione al menos una respuesta.
a. Que “sobren palabras” Correcto: esto es, que la gramática genere
algunas palabras que no debería
generar. En este caso, la gramática seria incorrecta.
b. Que “falten palabras”, Correcto esto es, que haya palabras en el
lenguaje considerado para lasque no hay ninguna derivación. En este caso, la gramática seria incompleta.
c. Reutilizar gramáticas y modificarlas para ajustarlas al
lenguaje generado
Incorrecto: Es posible hacerlo pero no son errores comunes
d. Combinar gramáticas
El problema del diseño de GLC consiste en proponer, dado un lenguaje L, una GLC G tal que su
lenguaje generado es exactamente L.
Correcto
Puntos para este envío: 1/1.
Question4
Puntos: 1
Identifique los aspectos que se deben tener para garantizar el determinismo en un Autómata de
pila finito determinista (AFPD).
Tenga en cuenta además de los componentes (tupla) de la pila que::
f: es la función de transición:
e: es una transición dada espontanea.
Seleccione al menos una respuesta.
a. El determinismo se da cuando no hay alternativas de movimiento para el mismo estado, usando la misma entrada y el mismo símbolo de
pila.
b. Las transiciones lambda en un AFPD permiten que el autómata cambie el contenido de la pila, sin procesar (o consumir) símbolos sobre
la cinta de entrada.
Correcto
c. La definición de la función de transición (f) requiere que haya por lo menos un símbolo en la pila. No se permiten operaciones con la pila
vacía.
Correcto
d. Las operaciones: f(q,a,s)y f(q,e,s) con a ∑ ,, q Q y s (pertenecen) al alfabeto de la pila y no pueden estar simultáneamente definidos o
declarados.
Parcialmente correcto
Puntos para este envío: 0.5/1.
Question5
Puntos: 1
Los AP tienen ciertos comportamientos y asociaciones con los AF.
Seleccione las afirmaciones válidas:
Seleccione al menos una respuesta.
a. Si se quiere meter cadenas a una pila, puede hacerse
con una operación tipo “pop”
b. Los autómatas de pila aceptan exactamente los LLC. Por
lo que: Si M es un AP, entonces L(M) es un LLC
Correcto: Si L es un LLC, entonces hay un AP M tal que L(M) = L
c. Los AP son una extensión de los AF
Correcto
d. Los AP son una extensión de los AF
Correcto
Correcto
Puntos para este envío: 1/1.
Question6
Puntos: 1
Cuando las gramáticas son demasiado extensas y generan árboles de
derivación grandes, se suele usar:
Seleccione una respuesta.
a. Formas de Greibach
b. Formas de LIC
c. Producciones de tipo GIC con un solo nodo terminal
d. Formas canónicas que restrinjan los tipos de producciones que
pueden utilizarse.
Correcto
La definición de una gramática independiente del contexto es demasiado
amplia, y por lo tanto, es deseable establecer una forma canónica que restrinja
los tipos de producciones que pueden utilizarse.
Correcto
Puntos para este envío: 1/1.
Question7
Puntos: 1
Sea un autómata (finito o de pila) M y una cadena x ∈ L(M). Si el autómata lee la cadena x,
¿llegará necesariamente a un estado de aceptación?
Seleccione una respuesta.
a. Sí, siempre.
b. Si, si M es un autómata finito.
c. No todas las veces, dado que puede tratarse de un autómata no
determinista.
Correcto
d. Nunca, Queda en un bucle ya que solo recorre un símbolo.
Correcto
Puntos para este envío: 1/1.
Question8
Puntos: 1
Indique cuál de las siguientes afirmaciones es verdadera:
Seleccione al menos una respuesta.
a. Cuando se dice que un AFPD (autómata de pila determinista) es más sencillo , se refiere a que es menos potente y no se refiere ala
sencillez de su diseño.
Correcto:
b. Para reconocer un lenguaje regular mediante un autómata de pila el alfabeto de la pila debe
contener al menos un símbolo
c. Para reconocer un lenguaje regular mediante un autómata de pila no es necesario que el
alfabeto de la pila contenga ningún símbolo
Correcto: Cualquier lenguaje independiente del contexto puede ser aceptado por un autómata de pila, y todos lenguajes regulares son independientes del contexto.
d. Con un autómata de pila no puede
reconocerse un lenguaje regular
Correcto
Puntos para este envío: 1/1.
Question9
Puntos: 1
En un autómata de pila (AP), la función de transición aplica o interviene a:
Seleccione al menos una respuesta.
a. A cada símbolo topo de la pila
Correcto
b. A cada estado
Correcto
c. A cada movimiento de la pila
d. A cada símbolo de entrada (Incluyendo la cadena
vacía)
Correcto
La función de transición aplica cada estado, cada símbolo de entrada
(incluyendo la cadena vacía) y cada símbolo tope de la pila en un conjunto de
posibles movimientos. Cada movimiento parte de un estado, un símbolo de la
cinta de entrada y un símbolo tope de la pila. El movimiento en sí consiste en
un cambio de estado, en la lectura del símbolo de entrada y en la substitución
del símbolo tope de la pila por una cadena de símbolos.
Parcialmente correcto
Puntos para este envío: 0.8/1.
Question10
Puntos: 1
Acerca del funcionamiento de un Autómata de Pila, cuál de las siguientes
operaciones o comportamientosNO las hace este autómata.
Seleccione una respuesta.
a. En la Pila una transición de un estado a otro Arroja la información de lo que sale de la pila (tope), no de lo que entra ya que el avance es progresivo
hacia adelante y no hacia atrás.
Correcto: Esta afirmación es falsa ya que en los AP las transiciones de un estado a otro indican, además de los caracteres que se
consumen de la entrada, también lo que se saca del tope de la pila, así como también lo que se mete a la pila.
b. La pila no tiene límite en sus extremos. A diferencia de las MT que son cerradas por la
izquierda.
c. Al igual que los AF, los AP tienen estados finales, que permiten distinguir cuando una palabra de
entrada es aceptada
d. Una de las condiciones para que una palabra de entrada sea aceptada en un AP la pila debe estar
vacía.
Para verificar el funcionamiento del autómata, podemos simular su ejecución,
listando las situaciones sucesivas en que se encuentra, mediante una tabla que
llamaremos “traza de ejecución”. Las columnas de una traza de ejecución para
un AP son: el estado en que se encuentra el autómata, lo que falta por leer de
la palabra de entrada, y el contenido de la pila
Correcto
Puntos para este envío: 1/1.
1
Puntos: 1
Considere la gramática G1 = {S→ aS/ aA/ a, A→ aB/ bS, B→ aB/ bB, C→ aA/ bC}
y G2 = {S→ aS/ aA/ a, A→ bS}. Sean L1 y L2 los lenguajes generados respectivamente por G1
y G2; entonces: (Nota: el símbolo ⊂denota la relación de inclusión estricta):
Seleccione una respuesta.
a. L1 ⊂ L2
b. L2 ⊂ L1
c. L1 = L2 Correcto: Las reglas que implican a los no terminales B y C no generan
ninguna cadena.
d. L1 ≠ L2
Correcto
Puntos para este envío: 1/1.
Question2
Puntos: 1
Desarrolle la siguiente gramática cuyos símbolos terminales son {a,b}
S aAA, A ---> bS, A ---> lambda
Identifique las apreciaciones válidas. Se recomienda desarrollar el árbol de derivación
Seleccione al menos una respuesta.
a. El autómata más sencillo que Acepta L(G) es un autómata de pila (AP). Una cadena válida sería
{abab}
b. La cadena más sencilla que genera el L(G) es:
{aba}
c. El autómata más sencillo que Acepta L(G) es un
autómata finito
Correcto
d. El lenguaje que genera la gramática es L(G) =
a(ba)*
Correcto
Correcto
Puntos para este envío: 1/1.
Question3
Puntos: 1
Dada la siguiente gramática G= (VN= {S, A}, VT= {0,1}, S, P) donde P son
las producciones:
Seleccione al menos una respuesta.
a. S –> 0A –> 0A –> 00A –> 000
b. S –> 0A –> 00A –> 001S –> 0010 A –>
00100
Correcto: Ambas producciones aplican a la gramática con cadenas válidas como 0100 y 00100
c. S –> 0A –> 01S –> 010 A –> 0100 Correcto: Ambas producciones aplican a la gramática con
cadenas válidas como 0100 y 00100
d. S –> 0A –> 00A –> 001 A –> 0010
Correcto
Puntos para este envío: 1/1.
Question4
Puntos: 1
Si una gramática independiente del contexto tiene todas sus reglas de la forma: A → wB, o bien
de la forma A → w, donde w es una cadena de uno o más terminales, y A y Bson símbolos no
terminales, entonces el lenguaje generado por dicha gramática es:
Seleccione una respuesta.
a. Regular
Correcto
b. Estructurado por frases y no independiente del contexto
c. Decidible
d. Independiente del contexto no regular
Correcto
Puntos para este envío: 1/1.
Question5
Puntos: 1
Cual de las siguientes afirmaciones se asocia correctamente al diseño y
funcionamiento de los árboles de derivación.
Seleccione una respuesta.
a. En un árbol de derivación cada nodo solamente
puede tener otro hijo nodo
b. En un árbol de derivación, una gramática es ambigua cuando hay dos o más árboles de derivación distintos
para una misma cadena.
Respuesta Correcta: Una gramática es “ambigüa” cuando hay dos o más árboles de derivación distintos para una misma cadena
c. Los lenguajes generados por una Gramática Independiente del Contexto son llamados Lenguajes
Regulares
d. En los árboles de derivación, no es necesario usar
nodo raíz
Al derivar una cadena a través de una GIC, el símbolo inicial se sustituye por
alguna cadena. Los no terminales se van sustituyendo uno tras otro por otras
cadenas hasta que ya no quedan símbolos no terminales, queda una cadena
con sólo símbolos terminales. A veces es útil realizar un gráfico de la
derivación. Tales gráficos tienen forma de árbol y se llaman “árbol de
derivación” o “árbol de análisis”. Para una derivación dada, el símbolo inicial
“S” etiqueta la raíz del árbol. El nodo raíz tiene unos nodos hijos para cada
símbolo que aparezca en el lado derecho de la producción, usados para
reemplazar el símbolo inicial. De igual forma, cada símbolo no terminal tiene
unos nodos hijos etiquetados con símbolos del lado derecho de la producción
usada para sustituir ese no terminal.
Correcto
Puntos para este envío: 1/1.
Question6
Puntos: 1
Cual de las siguientes afirmaciones es VERDADERA
Seleccione una respuesta.
a. Los lenguajes generados por una Gramática Independiente del Contexto son llamados Lenguajes
Regulares
b. En un árbol de derivación cada nodo solamente puede tener otro hijo nodo. De lo contrario se formaría
otro nodo.
c. En un árbol de derivación, una gramática es ambigua, cuando hay dos o más árboles de derivación
distintos para una misma cadena.
Correcto. En este caso es ambigua por cuanto puede tener varias soluciones
d. En los arboles de derivación, los nodos raíces
siempre derivan en dos ramas.
Es posible probar que cualquier palabra que sea aceptada por el AFD M, puede
ser generada por la gramática regular G. Esto significa que L(G) = L(M).
Correcto
Puntos para este envío: 1/1.
Question7
Puntos: 1
La combinación de autómatas se demostró en los Autómatas Finitos de la
Unidad 1 en as que era viable combinar dos Autómatas que generaban el miso
lenguaje y obtener otro que genera las mismas cadenas que los autómatas
combinados.
Con referencia a los Autómatas de Pila (AP), este tema de combinación tiene
aspectos a analizar. identifique cuál es válido para estas operaciones:
Seleccione una respuesta.
a. Se pueden obtener AP que acepten operaciones de Unión y Concatenación de los lenguajes aceptados por los Autónomas de
Pila dados.
Correcto
b. Solo la operación de Unión de los lenguajes de dos AP es
permitida.
c. Las operaciones de combinar AP solo es viable cuando los dos
Autónomas leen el mismo alfabeto.
d. Un AP se puede combinar con una MT siempre y cuando lean y
acepten el mismo lenguaje.
En los AP también es posible aplicar métodos de combinación modular de
autómatas, como se hizo con los autómatas finitos. En particular, es posible
obtener AP que acepten la unión y concatenación de los lenguajes aceptados
por dos AP dados.
Correcto
Puntos para este envío: 1/1.
Question8
Puntos: 1
Se propone la siguiente GLC (Gramática Libre de Contexto) para que genere el lenguaje de los palíndromos
en el alfabeto ∑ = {a,b}
G = S → aSa | bSb | a | b |
Dada esa gramática, determine cuáles reglas corresponden a los palíndromos generados.
Seleccione al menos una respuesta.
a. S → b (Palíndromos con símbolos
pares)
b. S → a (Palíndromos con símbolos
pares)
c. S → a | S → b (Palíndromos con símbolos
impares)
Correcto: Al realizar el árbol de derivación y el desarrollo de la gramática, las reglas que llevan a crear palíndromos impares son: S → a produce la cadena ω = baaab (impar) y S → b produce la cadena ω = babab (impar) y S → lambda produce la cadena ω = baab (par).
d. S → lambda ( Palíndromos con símbolos
pares )
Correcto: Al realizar el árbol de derivación y el desarrollo de la gramática, las reglas que llevan a crear palíndromos impares son: S → a produce la cadena ω = baaab (impar) y S → b produce la cadena ω = babab (impar) y S → lambda produce la cadena ω = baab (par).
Correcto
Puntos para este envío: 1/1.
Question9
Puntos: 1
Dado el siguiente árbol de derivación, identifique las apreciaciones válidas cuando se analiza su
comportamiento y diseño:
Seleccione al menos una respuesta.
a. La gramática está representada como G = { S --->lambda |
aS}
b. El árbol representa una gramática lineal por la izquierda, que
genera el lenguaje L ={lambda, a,aa,aaa,…}
Correcto: Es una Gramática lineal por la izquierda. La ER es la que representa el lenguaje descrito
c. El árbol representa las cadenas que inician en dos a”s
seguida de una o más a”s de un lenguaje regular
d. La gramática está representada como: G = { S -lambda | Sa} y el lenguaje generado puede representarse con la expresión
regular a*
Correcto: Es una Gramática lineal por la izquierda. La ER es la que representa el lenguaje descrito.
Correcto
Puntos para este envío: 1/1.
Question10
Puntos: 1
Sea L el lenguaje de alfabeto Σ = {a,b,c} y cadenas de forma wcv, donde w y v son cadenas de
a’s y b’s y w y v tienen la misma longitud pero v no es la cadena inversa de w. Dicho lenguaje
coincide con el generado por la gramática:
Seleccione una respuesta.
a. S → aSa, S→bSb, S→aRb, S→bRa, R→aRa, R→bRb,
R→c.
b. S → aSa, S→bSb, S→aRb, S→bRa, R→aRa, R→bRb,
R→aRb, R→bRa, R→c.
Correcto: Como w y v no pueden ser cadenas inversas, al menos debe existir
un par de caracteres de w y v que ocupen posiciones simétricas con respecto al centro de la cadena y sean diferentes . Por tanto, toda cadena de L puede
ser generada por la gramática, y toda cadena generada por la gramática pertenece a L
c. S → aSa, S→bSb, S→aRb, S→bRa, R→aRb, R→bRa,
R→c.
d. S → aSa, S→bSb, S→aRb, S→bRa, R→bRb, R→aRa,
R→bRa, R→c.
Correcto
Puntos para este envío: 1/1.
Question11
Puntos: 1
Considere la gramática S →Rc, R → aRbR, R → λ. Siendo w una cadena cualquiera generada por
dicha gramática, indique cuál de las siguientes afirmaciones es falsa:
Seleccione una respuesta.
a. El número de letras a es mayor o igual al de letras b en todo prefijo de w. Prefijo de una cadena w es toda cadena no
vacía x para la que existe una cadena u tal que w = xu.
b. El número de letras a es igual al de letras b en w Esto es verdadero
c. Las cadenas {abc, c} son aceptadas
d. w = xc | x ∈ (a∪ b)*
Incorrecto
Puntos para este envío: 0/1.
Question12
Puntos: 1
Dada la siguiente gramática.
Genera le lenguaje {aibjci+j | i+j>0}.
S aAc |ac | bBc | bc ; A aAc | ac |bBc | bc; B ---> bBc | bc
Identifique que producciones fueron necesarias para generar la cadena válida {aabbbccccc}
Seleccione una respuesta.
a. S --->aAc ; A--->bBc ; B ---> bc
b. S --->aAc ; A--->aAc | bBc ; B --->
bc
c. S --->aAc ; A--->aAc | aAc | bBc ; B --->
bBc | bc
d. S --->aAc ; A--->aAc | bBc ; B ---> bBc |
bc
Correcto
Correcto
Puntos para este envío: 1/1.
Question13
Puntos: 1
En la descripción de las gramáticas, las producciones unitarias tienen la forma:
Seleccione una respuesta.
a. A --> B
Correcto
b. S-->a
c. S-->ABs
d. A -->sB
Las producciones unitarias son las que tienen la forma A → B
Correcto
Puntos para este envío: 1/1.
Question14
Puntos: 1
Indique cuál de las siguientes afirmaciones es verdadera
Seleccione una respuesta.
a. Los autómatas finitos tienen un número finito de
estados
Correcto
b. Los autómatas finitos sólo pueden aceptar lenguajes
finitos
c. Los autómatas de pila reconocen lenguajes generados por
gramáticas de tipo 3
d. Las máquinas de Turing y los autómatas de pila son
autómatas finitos
Correcto
Puntos para este envío: 1/1.
Question15
Puntos: 1
Dada la gramática S → aS; S→ aSbS; S→ λ. Indique cuál de las siguientes afirmaciones es falsa:
Seleccione una respuesta.
a. La cadena {b} es rechazada
b. Cualquier cadena generada por la gramática contiene una subcadena no vacía donde el número de letras a es igual al
número de letras b
Esta es la opción falsa. La cadena a que en efecto es aceptada , generada por la gramática, no cumple esta condición
c. Para cualquier prefijo de una cadena generada por la gramática se verifica que el número de letras a es mayor o igual al número de letras b. Prefijo de una cadena w es toda cadena no vacía x para la que existe una cadena u tal que w
= xu
d. El lenguaje generado por la gramática es estructurado por
frases
Correcto
Puntos para este envío: 1/1. 1
Puntos: 1
A las computadoras reales y las MT se les asocian muchas similitudes y diferencias: Cuáles diferencias entre
una computadora Real y una máquina de Turing (MT) son verdaderas:
Seleccione al menos una respuesta.
a. En una MT el Número de estados depende de la
cadena, palabra o dato que lea.
Incorrecto: la palabra o cadena de lectura no determina la cantidad de estados que deba tener una MT. Puede determinar pro que estados recorre la máquina.
b. En una MT el orden de ejecución de las instrucciones no
necesariamente debe estar definido.
c. En una computadora, el número de estados viene
representado por el contenido de la memoria.
d. En cuanto al orden de ejecución de las instrucciones, En la estructura Von Neumann el secuenciamiento lo marca el orden de colocación de las instrucciones en la memoria
interna y viene asegurado por el contador de programa.
Correcto: Diferencias entre las computadoras y las máquinas de Turing. En Una máquina de Turing, el orden de ejecución de las instrucciones si está definido, lo marca en todo instante el estado de la máquina y el carácter de la cinta apuntado, que son los dos datos que determinan la quíntupla que ha de ser ejecutada.
Parcialmente correcto
Puntos para este envío: 0.5/1.
Question2
Puntos: 1
Un problema de decisión (PD) es aquel formulado por una pregunta (referida a alguna propiedad) que
requiere una respuesta de tipo “si/no”. Para la Teoría de Lenguajes, un problema de decisión
es “insoluble” cuando:
Seleccione al menos una respuesta.
a. Si no se logra representar con un diagrama de Moore el
problema.
b. Si no existe un procedimiento efectivo para determinar si la
propiedad es verdadera (no existe una Máquina de Turing MT).
Correcto
c. Si no existe un algoritmo total para determinar si la propiedad y
objetivo del problema es verdadera.
Correcto
d. Existe un procedimiento definido que determina la ambigüedad
del problema
Correcto
Puntos para este envío: 1/1.
Question3
Puntos: 1
Analice la codificación de la siguiente Máquina: Si lee 0101 (de izquierda a derecha), la salida
correspondiente es:
Seleccione una respuesta.
a. 0101
b. 0111 Correcto: La salida correspondiente es 0111 si se tiene en cuenta
que en las transiciones, el primer carácter es el que lee y el segundo es el que escribe.
c. 0011
d. 0110
Correcto
Puntos para este envío: 1/1.
Question4
Puntos: 1
Dentro de las tesis que plasmaron Church y Turing, está una de las más aplicadas y
demostradas hoy en día, enfocada al funcionamiento de las máquinas reales (coputadoras). Esta
es:
Seleccione una respuesta.
a. Las máquinas reales tienen mayor poder de cómputo que las Máquinas de Turing, aunque resuelvan los mismos
problemas.
Incorrecto
b. Toda función computable tiene un algoritmo decidible pro
una MT
c. La máquina de Turing, tiene mayor poder de cómputo que
las reales, aunque resuelvan los mismos problemas.
d. Una MUT es funcional y eficiente tanto como una máquina
real.
Incorrecto
Puntos para este envío: 0/1.
Question5
Puntos: 1
La codificación redundante tiene como objetivo introducir símbolos para asegurar la veracidad en
la trasmisión. Esto se logra por medio de algoritmos que aseguran la veracidad de la información
transmitida procurando no perder velocidad en la trasmisión. Los algoritmos para la veracidad
son:
Seleccione una respuesta.
a. Los de codificación AWGN
b. Los de codificación de fuente:
c. Los de codificación de canal Correcto: Esto se logra por medio de algoritmos que
adapten la información teniendo en cuenta las características estadísticas del ruido que presenta el canal.
d. Los de codificación de ruido
Correcto
Puntos para este envío: 1/1.
Question6
Puntos: 1
Cuáles diferencias entre una computadora Real y una máquina de Turing (MT) son verdaderas:
Seleccione al menos una respuesta.
a. En una MT el orden de ejecución de las instrucciones no
está definido.
b. En cuanto al orden de ejecución de las instrucciones, En la estructura Von Neumann el secuenciamiento lo marca el orden de colocación de las instrucciones en la memoria
interna y viene asegurado por el contador de programa.
Correcto: En Una máquina de Turing, el orden de ejecución de las instrucciones si está definido, lo marca en todo instante el estado de la máquina y el carácter de la cinta apuntado, que son los dos datos que determinan la
quíntupla que ha de ser ejecutada.
c. En una computadora, el número de estados viene
representado por el contenido de la memoria.
Correcto
d. En una MT el nº de estados depende del algoritmo.
Correcto
Correcto
Puntos para este envío: 1/1. 1
Puntos: 1
Los PROBLEMAS DE HALTING hacen referencia a: (Seleccione las opciones
verdaderas).
Seleccione al menos una respuesta.
a. El problema de tipo "insoluble" define que hay un algoritmo que lo soluciona pero que no se puede llevar a una MT o una
máquina abstracta.
Incorrecto
b. El problema de “Halting” es el primer problema indecidible
mediante maquinas de Turing
Correcto
c. Equivale a construir un programa que te diga si un problema de ordenador finaliza alguna vez o no (entrando a un bucle
infinito, por ejemplo)
Correcto
d. El problema de la parada o problema de la detención es de hecho soluble y la Teoría de la Computación lo definió como
tal
Incorrecto
El problema de “Halting” es el primer problema indecidible mediante máquinas
de Turing. Equivale a construir un programa que te diga si un problema de
ordenador finaliza alguna vez o no (entrando a un bucle infinito, por ejemplo)
Correcto
Puntos para este envío: 1/1.
Question2
Puntos: 1
La Máquina de Turing, y un autómata finito, tienen similitudes como:
Seleccione al menos una respuesta.
a. Una cabeza lectora Correcto
b. Un control finito Correcto
c. Un alfabeto para la cinta y un alfabeto de entrada Incorrecto
d. Un cabezal de lectura y otro para escritura Incorrecto
Máquina de Turing (abreviado MT) tiene, como los autómatas que hemos visto
antes, un control finito, una cabeza lectora y una cinta donde puede haber
caracteres, y donde eventualmente viene la palabra de entrada
Correcto
Puntos para este envío: 1/1.
Question3
Puntos: 1
Dado los siguientes tres codificadores convolucionales, diseñados para trabajar de forma lineal
secuencial redundante:
Se da como entrada el bit “1” en el codificador 1. Haga el recorrido completo hasta llegar a la
salida del codificador 3. Los bits de salida codificados finales son:
Tenga en cuenta que a partir del codificador 2, los bits de salida o entrada (según el caso) se
deben sobrescribir o reemplazar.
Seleccione una respuesta.
a. 01
Correcto
b. 10
c. 00
d. 11
Correcto
Puntos para este envío: 1/1.
Question4
Puntos: 1
Cuando se tratan los PROBLEMAS INSOLUBLES PARA LA TEORIA DE LENGUAJES, se presentan los
“Problemas de decisión” (PD).
Que aspectos en análisis son válidos para apoyar esta teoría
Seleccione al menos una respuesta.
a. Se puede decir que un lenguaje es decidible por que existe una
MT que los puede reconocer.
Correcto
b. Si se presenta un lenguaje decidible, es por que hay un algoritmo
que la MT reconoce.
Correcto
c. Un PD podría ser aquél formulado por una pregunta (referida a alguna propiedad) que requiere una respuesta de tipo “si/no”. Hay problemas de decisión de tipo “soluble”, “parcialmente soluble” e
“insoluble
Correcto
d. Mientras que los lenguajes computables son una infinidad numerable, los lenguajes no computables son una infinidad no
numerable.
Correcto
Correcto
Puntos para este envío: 1/1.
Question5
Puntos: 1
De los modelos creados para realizar cómputos y desarrollar problemas, es
válido afirmar:
Seleccione una respuesta.
a. Los modelos propuestos por Hilbert, solucionan cualquier problema
"No soluble"
b. Las funciones computables hacen referencia o son iguales a afirmar
que son modelos computables.
c. La MT no es un modelo Computable ya que solo se basa en
simulación.
d. Las llamadas máquinas de Turing no constituyen ni el primero ni el único formalismo para expresar cómputos, pero sí el que más ha
perdurado
Correcto
Las llamadas máquinas de Turing no constituyen ni el primero ni el único
formalismo para expresar cómputos, pero sí el que más ha perdurado.
Su creador, el matemático inglés Alan Turing (1912-1954) estaba convencido
de que no existía un algoritmo para el problema de decisión planteado por
Hilbert y su intención era demostrar dicha no existencia.
El modelo en el que se inspiró fue el de una persona real llevando a cabo un
cálculo mecánico, por ejemplo una multiplicación de dos grandes números en
el sistema decimal.
Correcto
Puntos para este envío: 1/1.
Question6
Puntos: 1
Dado los siguientes tres codificadores convolucionales, diseñados para trabajar de forma lineal
secuencial redundante:
Se da como entrada el bit “1” en el codificador 1. Haga el recorrido completo hasta llegar a la
salida del codificador 3 y determine el valor de “m” los bits que quedan en la memoria del código
de longitud restringida:
Tenga en cuenta que a partir del codificador 2, los bits de salida o entrada (según el caso) se
deben sobrescribir o reemplazar.
Seleccione una respuesta.
a. 010
b. 100
c. 001
Incorrecto
d. 110
Incorrecto
Puntos para este envío: 0/1.
Question7
Puntos: 1
Una Máquina de Turing (MT) se puede comportar como un aceptador de lenguaje, de la misma forma que lo
hace un Autómata finito (AF) o un Autómata de Pila (AP) así: Colocando una cadena ω en la cinta, situando
la cabeza de lectura/escritura sobre el símbolo del extremo izquierdo de la cadena ω y al poner en marcha la
máquina a partir de su estado inicial. Entonces ω es aceptada si, después de una secuencia de movimientos,
la MT llega a un estado final y para.
Que aspectos son válidos para el comportamiento de una MT..?
Seleccione al menos una respuesta.
a. Se pueden combinar dos Máquinas de Turing (MT) permitiendo que compartan la misma cinta y, que cuando una termine su ejecución, la otra
empiece.
Correcto
b. Es válido empezar el diseño de una MT por el diseño de un AF. Ambos son aceptadores de
lenguajes.
Correcto: Al diseñar una MT que acepte un cierto lenguaje, en realidad diseñamos el autómata finito que controla la cabeza y la cinta, el cual es un autómata con salida (acepta cadenas válidas).
c. La MT es un mecanismo abstracto avanzado que tiene el mismo poder computacional que las
máquinas reales.
Incorrecto: La Máquina de Turing es un mecanismo de computación notoriamente primitivo, y sin embargo permite llevar a cabo cualquier cómputo que podamos hacer en nuestro PC
d. Para rechazar una cadena que no es aceptable, lo único que hay que hacer es evitar que se llegue
a un estado final.
Correcto
Correcto
Puntos para este envío: 1/1.
Question8
Puntos: 1
Con referencia a una Máquina de Turing (MT) de dos direcciones: Una Máquina de Turing con una cinta
infinita en un sentido puede simular una Máquina de Turing con la cinta infinita en los dos
sentidos. Sea M una Máquina de Turing con una cinta infinita en los dos sentidos, entonces:
Para que se logre o se dé esta máquina se debe cumplir:
Seleccione al menos una respuesta.
a. La pista inferior y superior leen los datos simultáneamente en ambos sentidos. Luego y dependiendo de los estado repetitivos, se detiene una pista y continúa la que menos
celdas tenga ocupada.
Incorrecto
b. La cinta superior contiene información correspondiente a la parte derecha de la cinta M a partir de un punto de referencia
dado.
Correcto: La cinta superior por orden contiene la información de la parte derecha.
c. La pista inferior contiene tanto la parte izquierda como la
derecha de la cinta M (en orden inverso).
Incorrecto: La cinta superior por orden contiene la información de la parte derecha.
d. La Máquina de Turing M que tiene una Cinta Infinita en un sentido, puede simular a M si tiene una cinta con dos
pistas.
Correcto: La pista superior maneja un sentido
y la inferior maneja otro sentido (dirección).
Correcto
Puntos para este envío: 1/1.
Question9
Puntos: 1
Acerca del tipo de cadenas que puede aceptar una Máquina de Turing,
determine cuál afirmación es válida.
Seleccione una respuesta.
a. Por ser una máquina tan simple pero a la vez tan potente, resulta fácil que cualquier lenguaje puede ser reconocido por una
máquina de Turing
b. Es posible que un lenguaje sea estructurado por frases pero no exista ninguna máquina de Turing que se detenga exclusivamente cuando las cadenas escritas
en su cinta pertenezcan al lenguaje
c. Una máquina de Turing cuyo estado inicial coincida con el estado de parada acepta toda
cadena
Correcto: Decimos que en la MT se llega al “final de un cálculo” cuando se alcanza un estado especial llamado halt en el control finito, como resultado de una transición. Representaremos al halt por “h”
d. Cuando se desea que una MT no acepte una palabra, simplemente se debe configurar para que llegue a un estado halt de parada o
stop.
Al diseñar una MT que acepte un cierto lenguaje, en realidad diseñamos el
autómata finito que controla la cabeza y la cinta, el cual es un autómata con
salida.
Correcto
Puntos para este envío: 1/1.
Question10
Puntos: 1
Indique que características asocian particularidades o semejanzas válidas entre las MT y las
computadoras reales.
Seleccione al menos una respuesta.
a. En las máquinas reales están definidos procesos de manera jerárquica. En las MT estos procesos están
definidos por el número de estados.
Incorrecto: En una MT el nº de estados depende del algoritmo. En una computadora, un estado viene representado por el contenido de la memoria, y una situación por un estado y un puntero a una dirección (la que contiene a la instrucción que va a ejecutarse).
b. Las MUT son de un solo propósito. Las máquinas reales interpretan muchos programas escritos en
diferentes lenguajes (multipropósito).
Incorrecto: Esta máquina Universal no debe ser diseñada para realizar un cálculo específico, sino para procesar cualquier información (realizar cualquier cálculo específico -MT particular- sobre cualquier configuración inicial de entrada correcta para esa MT particular).
c. Los computadores electrónicos, basados en la arquitectura Von Neumann así como las máquinas cuánticas tendrían exactamente el mismo poder de expresión que el de una Máquina de Turing (MT) si dispusieran de recursos ilimitados de tiempo y espacio.
Correcto
d. Los lenguajes de programación, tienen a lo sumo el mismo poder de expresión que el de los programas para una Máquina de Turing (MT) y en la práctica no
todos lo alcanzan.
Correcto
Correcto
Puntos para este envío: 1/1.
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
Correcto
momento, cuál será el símbolo de salida.
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
Correcto
cadena
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→.
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 |
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.
Que significan las reglas de la forma A → lambda
Seleccione al menos una respuesta.
a. Se le llaman producciones
nulas
Correcto: Producciones Nulas: Son de la forma A → lambda
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
d. Generan lenguajes que contienen
la palabra vacía
Parcialmente correcto
Puntos para este envío: 0.5/1.
Question2
Puntos: 1
Que opciones son verdaderas al analizar la siguiente gramática.
Seleccione al menos una respuesta.
a. Genera el lenguaje que acepta cadenas como: {bacab, bbbc, aaac,
aabcbb}
b. Las cadenas que puede aceptar corresponden a cadenas de forma wcv, donde w y v son cadenas de a’s ó b’s y w y v tienen la misma
longitud sin importar si v o wsoon inversas simultáneamente.
c. Genera un lenguaje que acepta cadenas como: {aacab, aacbb,
abcbb, bbbcaba}
Correcto: El lenguaje corresponde a 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
d. Las cadenas que puede aceptar corresponden a 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
Parcialmente correcto
Puntos para este envío: 0.5/1.
Question3
Puntos: 1
Considere la gramática G1 = {S→ aS/ aA/ a, A→ aB/ bS, B→ aB/ bB, C→ aA/ bC}
y G2 = {S→ aS/ aA/ a, A→ bS}. Sean L1 y L2 los lenguajes generados respectivamente por G1
y G2; entonces: (Nota: el símbolo ⊂denota la relación de inclusión estricta):
Seleccione una respuesta.
a. L1 ⊂ L2
b. L1 = L2
c. L2 ⊂ L1
Incorrecto
d. L1 ≠ L2
Incorrecto
Puntos para este envío: 0/1.
Question4
Puntos: 1
Respecto a la definición de Ambigüedad, cuáles afirmaciones aplican al
concepto y lo clarifican en el tema de automatización cuando intervienen
gramáticas de diferente tipo: (seleccione más de una opción).
Seleccione al menos una respuesta.
a. Un lenguaje es inherentemente ambiguo si no existe una gramática que la describe y que no sea
ambigua
b. Sea una gramática G. Una sentencia x que pertenece a L(G) es ambigua si puede obtenerse por medio de varias derivaciones distintas correspondientes a árboles de derivación diferentes.
c. Se presenta cuando cada instrucción tiene una sola interpretación en cada rama de un árbol de derivación
y tiene un fin de parada en el segundo nodo.
Incorrecto. La ambigüedad es una propiedad indeseada en los lenguajes de programación. Cada instrucción debe tener solo una
interpretación.
d. Una gramática es ambigua si genera alguna
sentencia ambigua
La ambigüedad es una propiedad indeseada en los lenguajes de programación.
Cada instrucción debe tener solo una interpretación.
Incorrecto
Puntos para este envío: 0/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 LIC contiene al conjunto de
los lenguajes regulares.
b. El conjunto de los lenguajes regulares contiene
al conjunto de los LIC.
c. El conjunto de los lenguajes regulares y el conjunto de los LIC son conjuntos independientes.
Incorrecto: Los lenguajes generados por una GIC son llamados Lenguajes Independientes del Contexto (LIC).
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
Dado el siguiente árbol de derivación, identifique las apreciaciones válidas cuando se analiza su
comportamiento y diseño:
Seleccione al menos una respuesta.
a. La gramática está representada como: G = { S -lambda | Sa} y el lenguaje generado puede representarse con la expresión
regular a*
b. El árbol representa una gramática lineal por la izquierda, que
genera el lenguaje L ={lambda, a,aa,aaa,…}
c. El árbol representa las cadenas que inician en dos a”s seguida
de una o más a”s de un lenguaje regular
Incorrecto: Pueden haber cadenas con una sola “a”
d. La gramática está representada como G = { S --->lambda |
aS}
Incorrecto
Puntos para este envío: 0/1.
Question7
Puntos: 1
Indique cuál de las siguientes afirmaciones es verdadera
Seleccione una respuesta.
a. Los autómatas finitos tienen un número finito de
estados
b. Los autómatas finitos sólo pueden aceptar lenguajes
finitos
Incorrecto
c. Las máquinas de Turing y los autómatas de pila son
autómatas finitos
d. Los autómatas de pila reconocen lenguajes generados
por gramáticas de tipo 3
Incorrecto
Puntos para este envío: 0/1.
Question8
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. Solo la operación de Unión de los lenguajes de dos AP es
permitida.
b. Se pueden obtener AP que acepten operaciones de Unión y Concatenación de los lenguajes aceptados por los Autónomas de
Pila dados.
c. Las operaciones de combinar AP solo es viable cuando los dos
Autónomas leen el mismo alfabeto.
Incorrecto
d. Un AP se puede combinar con una MT siempre y cuando lean
y acepten el mismo lenguaje.
En los AP también es posible aplicar métodos de combinación modular de
autómatas, como se hizo con los autómatas finitos. En particular, es posible
obtener AP que acepten la unión y concatenación de los lenguajes aceptados
por dos AP dados.
Incorrecto
Puntos para este envío: 0/1.
Question9
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 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.
b. Simular su ejecución, listando las situaciones sucesivas en que se encuentra, mediante una tabla llamada “traza de
ejecución
Correcto
c. Simularlo en JFLAP con la cadena vacía Lambda para
determinar si la pila inicia o no.
d. Simular su ejecución en una MT que se comporta de igual
forma
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
Si a un Autómata se le adiciona un almacenamiento auxiliar, se está
construyendo entonces:
Seleccione una respuesta.
a. Una Turing Machine (TM)
b. Un Pushdown Automaton (PA)
c. Un Autómata Determinístico Finito.
d. Un Autómata No determinístico pero Finito
Añadir al AF un almacenamiento auxiliar, que llamaremos pila, donde se
podrían ir depositando caracter por caracter cadenas arbitrariamente grandes,
es el primer paso a la construcción de un AP a partir de un simple AF.
Incorrecto
Puntos para este envío: 0/1.
Question11
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
b. 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*
c. 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
d. Este árbol de derivación es producto de la gramática
lineal por la derecha: S –>aA | A ---> bA | c
Parcialmente correcto
Puntos para este envío: 0.3/1.
Question12
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 | 1S2 | 10
b. S –> 0A0 | 1S0 | 2 | 0
c. S –> 0A0 | 1S1 | 2
d. 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.
Incorrecto
Puntos para este envío: 0/1.
Question13
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
b. Las cadenas {0101, 1001] no son parte del lenguaje que
genera
c. La regla S→ S0 es innecesaria
Correcto
d. La gramática es equivalente a S→0S, S→ 1S, S→ λ
Parcialmente correcto
Puntos para este envío: 0.3/1.
Question14
Puntos: 1
Dada la gramática S → aS; S→ aSbS; S→ λ. Indique cuál de las siguientes afirmaciones es falsa:
Seleccione una respuesta.
a. El lenguaje generado por la gramática es estructurado por
frases
b. La cadena {b} es rechazada
c. Para cualquier prefijo de una cadena generada por la gramática se verifica que el número de letras a es mayor o igual al número de letras b. Prefijo de una cadena w es toda cadena no vacía x para la que existe una cadena u tal que w
= xu
Esta afirmación es correcta: ejemplo la cadena {aabbb} no es aceptada
d. 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
Incorrecto
Puntos para este envío: 0/1.
Question15
Puntos: 1
Sea M un autómata de pila. Indique cuál de las siguientes afirmaciones es falsa:
Seleccione una respuesta.
a. 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
Esta afirmación es verdadera ya que L es un lenguaje regular
b. Un autómata de Pila reconoce lenguajes que sean
generados por gramáticas de tipo2.
c. 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
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
Incorrecto
Puntos para este envío: 0/1.
1
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.
Incorrecto
c. ∑0 = {lambda} Conjunto cuyo único elemento es la
palabra 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.
Incorrecto
Puntos para este envío: 0/1.
Question2
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
Incorrecto: Las cadenas no son aceptadas cuando se recorre la gramática.
b. {a,b}
c. {baaaa, aaaaa, bba}
d. {aa, aaaa, bbba, ba, bba, baaa, baba}
Incorrecto
Puntos para este envío: 0/1.
Question3
Puntos: 1
Los AP tienen ciertos comportamientos y asociaciones con los AF.
Seleccione las afirmaciones válidas:
Seleccione al menos una respuesta.
a. Los autómatas de pila aceptan exactamente los LLC. Por lo
que: Si M es un AP, entonces L(M) es un LLC
b. Si se quiere meter cadenas a una pila, puede hacerse con
una operación tipo “pop”
c. Los AP son una extensión de los AF
Correcto
d. Los AP son una extensión de los AF
Parcialmente correcto
Puntos para este envío: 0.3/1.
Question4
Puntos: 1
Respecto a la relación entre un AF y un AP cuál afirmación es cierta:
Seleccione una respuesta.
a. Un AP es infinito por su capacidad de memoria.
Un AF es finito por su número de estados.
b. Los AF y los AP tienen la misma capacidad de
memoria
Incorrecto: los AP tienen mayor capacidad de memoria
c. Todo lenguaje aceptado por un AF es también
aceptado por un AP
d. Las gramáticas que generan los lenguajes que pueden representar estos autómatas o máquinas,
son las GLC
En los AP también es posible aplicar métodos de combinación modular de
autómatas, como se hizo con los autómatas finitos. En particular, es posible
obtener AP que acepten la unión y concatenación de los lenguajes aceptados
por dos AP dados.
Incorrecto
Puntos para este envío: 0/1.
Question5
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 --->B |lambda , A ---> 1B | lambda,, B ---> lambda}
c. G= {S -->0B | 0A , A ---> 1B | lambda , B ---> lambda
Incorrecto
d. G = { S --->A |lambda , A ---> 0B | lambda,, B ---> lambda}
Incorrecto
Puntos para este envío: 0/1.
Question6
Puntos: 1
Del diseño y naturaleza de los autómatas de pila (PDA), es válido afirmar:
Seleccione una respuesta.
a. 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.
b. Un Autómata de Pila al igual que una Máquina de Turing o un Autómata Finito, su definición básica es de naturaleza no
determinista
c. Un autómata de pila no puede hacer las funciones de "contador" ya que sus recorridos varían en la cinta y lo que le importa a esta automatización es el estado final y la salida del
dato.
Incorrecto: Los autómatas de Pila se usan como contadores de datos, es una aplicación más de estas máquinas. De hecho este conteo es usado para comparar otros elementos de entrada y comportamientos.
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
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.
Incorrecto
Puntos para este envío: 0/1.
Question7
Puntos: 1
Dado un alfabeto ∑, los símbolos Ø, y los operadores + (unión), ∙
(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 ω = lambda entonces L (lambda) = { lambda}
b. Si ω = a y a pertenece ∑ entonces L (ω) no pertenece ∑
c. Si ω = Ø entonces L (ω) = Ø
d. Si ω* es una ER entonces L (ω*) no es una ER
La notación de conjuntos nos permite describir los lenguajes regulares, pero
nosotros quisiéramos una notación en que las representaciones de los
lenguajes fueran simplemente texto (cadenas de caracteres). Así las
representaciones de los lenguajes regulares serían simplemente palabras de un
lenguaje (el de las representaciones correctamente formadas).
Incorrecto
Puntos para este envío: 0/1.
Question8
Puntos: 1
Identifique los aspectos que se deben tener para garantizar el determinismo en un Autómata de
pila finito determinista (AFPD).
Tenga en cuenta además de los componentes (tupla) de la pila que::
f: es la función de transición:
e: es una transición dada espontanea.
Seleccione al menos una respuesta.
a. El determinismo se da cuando no hay alternativas de movimiento para el mismo estado, usando la misma entrada y el mismo símbolo de
pila.
Correcto
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.
c. Las operaciones: f(q,a,s)y f(q,e,s) con a ∑ ,, q Q y s (pertenecen) al alfabeto de la pila y no pueden estar simultáneamente definidos o
declarados.
d. La definición de la función de transición (f) requiere que haya por lo menos un símbolo en la pila. No se permiten operaciones con la pila
vacía.
Parcialmente correcto
Puntos para este envío: 0.3/1.
Question9
Puntos: 1
De entre las cuatro clases de gramáticas de la clasificación de Chomsky, el
grupo más importante, desde el punto de vista de la aplicabilidad en teoría de
compiladores, es el de las gramáticas independientes o libres del contexto. Las
gramáticas de este tipo se pueden usar para expresar la mayoría de
estructuras sintácticas de un lenguaje de programación.
Aspectos que caracterizan este tipo de gramáticas son:
Seleccione al menos una respuesta.
a. La longitud de las cadenas de derivaciones nunca puede ser nula y siempre se grafican en el Arbol de derivación iniciando por la Izquierda La representación de las derivaciones de la gramática siempre se hacen de forma vertical. Nunca de forma
comprimida u horizontal
b. Un árbol ordenado y etiquetado D es un árbol de derivación
para una gramática libre de contexto G(A)
c. La representación de las derivaciones de la gramática siempre se hacen de forma vertical. Nunca de forma comprimida u
horizontal
Incorrecto
d. El lenguaje definido por una gramática G, denotado L(G) es el conjunto de cadenas de símbolos terminales, que se pueden derivar partiendo del axioma de la gramática, y empleando para
las derivaciones las reglas de producción de P
Una gramática es un conjunto de reglas para formar correctamente las frases
de un lenguaje; así tenemos la gramática del español, del francés, etc. La
formalización que presentaremos de la noción de gramática es debida a N.
Chomsky, y está basada en las llamadas reglas gramaticales.
Incorrecto
Puntos para este envío: 0/1.
Question10
Puntos: 1
Para que una palabra de entrada sea aceptada en un AP se deben cumplir las
condiciones siguientes:
Seleccione al menos una respuesta.
a. La pila debe tener lambda como elemento final.
b. La palabra de entrada se debe haber agotado
(consumido totalmente).
c. El AP se debe encontrar en un estado final. Correcto: para que una palabra de entrada
sea aceptada en un AP se deben cumplir todas las condiciones siguientes: 1. La palabra de entrada se debe haber agotado (consumido totalmente). 2. El AP se debe encontrar en un estado final. 3. La pila debe estar vacía.
d. La pila debe estar vacía.
A la hora de diseñar un AP tenemos que repartir lo que requiere ser “recordado” entre los estados y la pila.
Distintos diseños para un mismo problema pueden tomar decisiones diferentes en cuanto a qué recuerda
cada cual.
Parcialmente correcto
Puntos para este envío: 0.3/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 no genera ningún lenguaje porque presenta más de un estado de aceptación o
final.
Incorrecto: la gramática si genera un lenguaje y no genera la cadena vacía.
b. La gramática no genera la cadena vacía
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
Incorrecto
Puntos para este envío: 0/1.
Question2
Puntos: 1
Dado el alfabeto ∑= {a,b}, identifique cuál afirmación es falsa.
Seleccione una respuesta.
a. La expresión regular b*ab* (ab*ab*)* representa al lenguaje de las cadenas con un número impar de letras
a
b. La expresión regular b*(ab*ab*)* representa al lenguaje
de las cadenas con un número par de letras a
Esto es afirmativo
c. La expresión regular (b*ab*ab*a) * representa al lenguaje de las cadenas con un número múltiplo de 3 de
letras “a”
d. La expresión regular b*a*b* representa al lenguaje de
las cadenas que pueden o no tener “a”
Incorrecto
Puntos para este envío: 0/1.
Question3
Puntos: 1
Dada la Gramática S→aS; S→aSbS; S→.
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. Las cadenas que acepta la gramática siempre van a empezar por b. Además el lenguaje generado por la
gramática es “no es estructurado por frases”.
Incorrecto
c. 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.
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
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.
Incorrecto
Puntos para este envío: 0/1.
Question4
Puntos: 1
Cuando se diseñan AP o se formalizan, se utilizan notaciones gráficas parecidas a la de los diagramas de los
AF. Con respecto a esto: ¿qué aspectos de diseños son válidos para formalizar un AP.?
Seleccione al menos una respuesta.
a. Si se da la transición “a/x/c” indica que se saca de la pila un carácter “a”, luego se avanza una posición “x” en la pila, y se mete “c” a la
pila.
b. Para que una palabra de entrada sea aceptada en un AP debe cumplir tres condiciones. Una de ellas es que el AP se debe
encontrar en un estado final.
Correcto: El funcionamiento de un AP indica una sintaxis en la que el caractér del centro o símbolo hace referencia a lo que se saca o no de la pila. Otra condición para que la cadena sea aceptada en un AP es que la pila esté vacía,
c. Si se da la transición “a/x/c” indica que se consume de la entrada un carácter “a”, se avanza una posición “x” y se mete “c” a la
pila.
d. Si se da la transición “a/x/c” indica que se consume de la entrada un carácter “a”, no se
saca nada de la pila, y se mete “c” a la pila.
Parcialmente correcto
Puntos para este envío: 0.5/1.
Question5
Puntos: 1
Un árbol de derivación, para una derivación dada se construye: (seleccione que las operaciones
que son necesarias): Teniendo en cuenta el siguiente árbol.
Seleccione al menos una respuesta.
a. Todos los nodos hoja están etiquetados con símbolos
terminales.
b. El nodo raíz tiene unos hijos para cada símbolo que aparece en el lado derecho de la producción usada para reemplazar el símbolo
inicial.
c. Creando un nodo raíz que se etiqueta con el símbolo inicial.
Correcto
d. Los nodos que no tienen hijos, deben ser etiquetados con
símbolos terminales.
Parcialmente correcto
Puntos para este envío: 0.3/1.
Question6
Puntos: 1
Para u AP, la función de transición también se puede representar mediante un diagrama donde
los nodos representan los estados y los arcos transiciones, Dada la siguiente transición como se
muestra en la figura, identifique las acciones correctas que haría el movimiento de la pila.
Seleccione una respuesta.
a. El estado actual es q0. La cabeza lectora apunta al símbolo “a”. El tope de la pila es X que se va a sustituir
por lambda al cambiar al nuevo estado q1 y avanzar la
cabeza lectora.
b. El estado actual es q0. La cabeza lectora apunta al tope X que es donde inicia la lectura del símbolo “a” que
entra al pasar al estado q1 y sustituir lambda por X.
Incorrecto
c. El estado actual es q0. La cabeza lectora apunta al símbolo “a”. El tope de la pila es “a” como primer símbolo a leer que se va a sustituir por lambda al cambiar al nuevo estado q1 y avanzar la cabeza
lectora.
d. El estado actual es q0. La cabeza lectora apunta al símbolo “lambda”. El recorrido de la pila es de izquierda a derecha. El tope de la pila es X que no se modifica al cambiar al nuevo estado q1 y avanzar la cabeza
lectora.
Incorrecto
Puntos para este envío: 0/1. 1
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. 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
b. 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
c. Un estado de aceptación también puede ser inicial. Solo
para autómatas finitos no
d. Conocer el estado de un autómata, es lo mismo que conocer toda la historia de símbolos de entrada, así como el estado inicial. Estado en que se encontraba el autómata al
recibir el primero de los símbolos de entrada.
Correcto
Correcto
Puntos para este envío: 1/1.
Question2
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 cadenas válidas para el autómata “A”, pero no para las
del autómata “B”.
b. La ER (0+1)*11(01)* genera cadenas válidas para el autómata “B” pero no para
las del autómata “A”.
c. 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.
d. La ER (0+1)*01 genera las mismas cadenas para el Autómata “B” y del
autómata “A”
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.
Correcto
Puntos para este envío: 1/1.
Question3
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. Unión de lenguajes
b. Asociación de lenguajes
c. Operación cerrada de dos lenguajes
d. 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.
Correcto
Puntos para este envío: 1/1.
Question4
Puntos: 1
Se pueden generar palíndromos (cadenas ω) sobre el alfabeto ∑ = {0,1}. Evidentemente este lenguaje tiene
infinitas cadenas
Selecciones las afirmaciones válidas con referencia al anterior postulado.
Seleccione al menos una respuesta.
a. Los símbolos de un alfabeto, definen el tipo de lenguaje
a que pertenece.
b. 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
c. ω = lambda ó cadena vacía y ω = 0 ; Son
palíndromos
d. 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
Parcialmente correcto
Puntos para este envío: 0.5/1.
Question5
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. Es un Autómata Finito Determinístico con lambda
transiciones
c. 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
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.
Question6
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 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
c. 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.
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.
Question7
Puntos: 1
Dada la siguiente gramática con las siguientes producciones,
S --> ab
SaSb
que derivaciones son válidas al usar sus reglas:
Seleccione al menos una respuesta.
a. aabb
Correcto
b. ab
c. Ba
d. Bbaa
Parcialmente correcto
Puntos para este envío: 0.5/1.
Question8
Puntos: 1
Dado el siguiente autómata: Cambie los símbolos del alfabeto asociando a = 0 y b =1 . Para las
siguientes opciones,(que están en base 10 o decimal), conviértalas a base 2 (binario) y recorra
el autómata e identifique cuál número acepta el autómata.
Seleccione una respuesta.
a. 182
b. 205
c. 73 Incorrecto: equivale a la cadena 01001001 y esta no
es reconocida
d. 253
Incorrecto
Puntos para este envío: 0/1.
Question9
Puntos: 1
Las siguientes cadenas:
{Lambda,aaa, bb, bbb, aabb, aba, abaaa, abbaa}
son generadas expresadas por la ER
Seleccione una respuesta.
a. ( a | b)*
b. (a + b ) *
c. (a.b)*
d. (a,b)*
Incorrecto
Incorrecto
Puntos para este envío: 0/1.
Question10
Puntos: 1
Expresiones regulares: Determine que igualdades son válidas:
Seleccione al menos una respuesta.
a. aa+b*a = (aa+b*)a
Incorrecto
b. a+a=a
c. a(aa+b)* + a(aa+b)* = a(aa+b)*
Correcto
d. a*=a*.a*=(a*)* Correcto: Por asociación
Parcialmente correcto
Puntos para este envío: 0.7/1.
Question11
Puntos: 1
Dados los siguientes autómatas determine que características aplican en cuanto a su
comportamiento y diseño.
Seleccione al menos una respuesta.
a. La cadena bababbaabb la reconocen los dos
autómatas.
Correcto: esta cadena es aceptada por ambos autómatas. Además amas máquinas son equivalentes
b. El autómata A es “equivalente” al autómata B Correcto: aceptan el mismo lenguaje.
c. El autómata A es un AFND y reconoce el mismo
lenguaje que el autómata B
Correcto. Además el autómata B resúltate de un proceso de equivalencia es un AFD.
d. El autómata A NO es “equivalente” al autómata B.
Correcto
Puntos para este envío: 1/1.
Question12
Puntos: 1
Dado el siguiente autómata, analice si es posible su minimización y seleccione las opciones
válidas para su análisis:
Seleccione al menos una respuesta.
a. Los estados q2 y q3 son equivalentes. Dado que transitan igual para los dos símbolos del alfabeto. Por tanto se pueden
fusionar en no solo.
b. El autómata no se puede minimizar. No hay estados equivalentes y los estados distinguibles no se pueden
modificar.
Incorrecto. El autómata se puede minimizar y os estados equivalentes o candidatos a comparar son q2 y q3.
c. Si es posible minimizarlos y el autómata resultante tendrá
tres estados
Correcto
d. El estado final q1 es equivalente con el inicial. (teorema de equivalencia de estados). Por tanto el autómata es candidato
a minimizarse.
Parcialmente correcto
Puntos para este envío: 0.5/1.
Question13
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. Los lenguajes que no poseen restricciones o de tipo 0, son reconocidos mediante Autómatas Finitos No
Deterministas (AFND)
b. Una gramática regular o de tipo 3, puede generar
Autómatas finitos (AF)
Correcto: esta afirmación es errada ya que las gramáticas generan lenguajes. Las máquinas o autómatas reconocen es lenguajes.
c. 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).
d. Los lenguajes libres de contexto o de tipo 2, pueden
ser generados por los autómatas de pila (AP)
Correcto: esta afirmación es errada ya que un lenguaje es descrito por una máquina y no generado por la máquina.
Parcialmente correcto
Puntos para este envío: 0.7/1.
Question14
Puntos: 1
Dados los siguientes dos autómatas finitos, identifique los aspectos válidos en cuanto a su
comportamiento.
Seleccione una respuesta.
a. Los autómatas reconocen cadenas o palabras
diferentes.
b. La cadena {bb} solo es reconocida por un autómata.
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 dos autómatas son producto de una gramática libre de
contexto GLC
Correcto
Puntos para este envío: 1/1.
Question15
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. Al clasificar lenguajes, no se están clasificando máquinas que los
reconozcan, Se clasifican gramáticas que los generan.
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. 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.
Correcto
d. Se llama “clase de lenguajes” a conjuntos de lenguajes que comparten
cierta propiedad dada.
Correcto
Correcto
Puntos para este envío: 1/1.
1
Puntos: 1
Algunas operaciones y propiedades sobre lenguajes y ER que se pueden realizar son:
Seleccione al menos una respuesta.
a. El orden de prioridad de los operadores es, de mayor a menor: *, ∙, + Este orden puede alterarse mediante paréntesis, de forma análoga a como se hace con las
expresiones aritméticas.
Correcto
b. (B U C) ∙ A = (B ∙ A) U (C ∙ A)
c. 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
d. A ∙ (B U C) = (A ∙ B) U (A ∙ C)
Parcialmente correcto
Puntos para este envío: 0.5/1.
Question2
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*(1)
b. 1(01) *
c. 0(010)* Incorrecto: Las cadenas inician con 1. Por
consiguiente la ER no es válida.
d. 1( 1) (0)*
Incorrecto
Puntos para este envío: 0/1.
Question3
Puntos: 1
Dado el siguiente Autómata Finito (AF).
La Expresión Regular (ER) que denota el Lenguaje que representa es.
Seleccione una respuesta.
a. xx*zx((zx+x*z)x)*
b. xz(xz)*((x*+xx*z)x)* Incorrecto: La ER no expresa as
cadenas válidas que acepta el autómata.
c. xxzx((zx)*z)*
d. xx*zx((z+xx*z)x)*
Incorrecto
Puntos para este envío: 0/1.
Question4
Puntos: 1
Que representa la siguiente figura:
Seleccione una respuesta.
a. Que representa la siguiente figura:
b. Un Autómata que acepta palabras o cadenas
que contienen únicamente b´s o a´s
c. 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 |∑|
d. No representa un autómata válido por que el mismo estado inicial es el mismo estado
final.
Correcto
Puntos para este envío: 1/1.
Question5
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. Solo el Autómata A reconoce la cadena vacía lambda
b. El Autómata A es un AFND y el Autómata B es un AFD
c. El Autómata B tiene un error de diseño. Un AF no puede
tener dos estados de aceptación
Incorrecto
d. Los dos Autómatas reconocen el mismo Lenguaje. Correcto: Ambos autómatas reconocen el
mismo lenguaje,
Parcialmente correcto
Puntos para este envío: 0.5/1.
Question6
Puntos: 1
Dado los autómatas M1 y M2 siguientes, cuáles relaciones entre estas dos máquinas son válidas.
Seleccione al menos una respuesta.
a. Los Autómatas M1 y M2 aceptan ambos el lenguaje a
*
Correcto: La equivalencia se da por la aceptación de lenguajes. Ambos aceptan el lenguaje a * y aceptan exactamente el mismo lenguaje
b. 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.
c. 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
d. Los Autómatas M1 y M2 son iguales pero no
equivalentes
Correcto
Puntos para este envío: 1/1.
Question7
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, 00100, …} = { 1(01)n |n ≠
0} La expresión regular es: 0(01) *
b. L = (A2 ) = {0, 001, 01111, …} = { 1(10)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.
Question8
Puntos: 1
Si se considera un autómata finito M con transiciones lambda que
reconoce el lenguaje L: De la relación entre determinista y no determinista de los autómatas, y el comportamiento de las cadenas
vacías (lambda), es válido afirmar
Seleccione al menos una respuesta.
a. Las transiciones lambda solo son aceptadas en la
descripción de las gramáticas.
b. Un autómata finito con transiciones lambda es un autómata
no determinista.
Correcto: Las cadenas vacías lambda son aceptadas y suelen presentarse en AFND.
c. Siempre existe un autómata finito determinista que reconoce un lenguaje reconocido por un autómata finito no
determinista.
d. No existe un autómata finito sin transiciones (lambda) que
reconozca L.
Incorrecto: Si es posible este tipo de autómatas.
Parcialmente correcto
Puntos para este envío: 0.5/1.
Question9
Puntos: 1
Cuáles afirmaciones son válidas cuando se trata de analizar el funcionamiento de los Autómatas Finitos (AF):
Seleccione al menos una respuesta.
a. Los AF son máquinas de memoria limitada. Correcto: Los estados son el único medio de
que disponen los AF para recordar los eventos que ocurren (por ejemplo, qué caracteres se han leído hasta el momento); esto quiere decir que son máquinas de memoria limitada.
b. En una máquina de estados finitos, la función de transición
almacena los datos de entrada del Autómata.
c. Los AF son máquinas de memoria amplia por ser
máquinas abstractas (no reales).
d. 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.
Correcto
Puntos para este envío: 1/1.
Question10
Puntos: 1
Se diseña el siguiente Autómata Finito Deterministico (AFD) para el
lenguaje de palabras del alfabeto {a,b} que no tiene
varias a´s seguidas. Esta solución es defectuosa porque.
Seleccione al menos una respuesta.
a. Tiene dos finales o de aceptación q1 y
q2
Incorrecto: No influye la ´parte de diseño el hecho de los dos estados de aceptación. El error se fundamenta es por la función de transición.
b. Hay palabras como “ba”, que no tienen a´s seguidas y sin embargo no son aceptadas por
el AFD.
Correcto: El "problema de diseño" de un AFD es considerar demasiadas posibilidades. El hecho que tenga dos estados finales o de aceptación no es problema y es válido en el diseño. La palabra "baba" No es aceptada por el autómata aunque sus elementos o símbolos si hacen parte del alfabeto que las compone.
c. Hay palabras como “baa”, que tiene a´s seguidas y sin embargo son aceptadas por el
AFD.
d. Hay palabras como “baba” que no tienen a´s seguidas y sin embargo son aceptadas por el AFD pero que no pertenecen al alfabeto
dado.
Parcialmente correcto
Puntos para este envío: 0.5/1.
Top Related