automatas y lenguajes formales

AUTOMATAS Y LENGUAJES FORMALES 301405

Act1: Revisión de Presaberes

Question 1

Puntos: 1

En Octubre de 1950, Alan Turing hizo estudios más abstractos y trató el tema de la

Inteligencia artificial. Para ello propuso un experimento que hoy se conoce como el “test de

Turig”. Que consiste básicamente en: (seleccione la verdadera).

Question 1

Puntos: 1

En Octubre de 1950, Alan Turing hizo estudios más abstractos y trató el tema de la

Inteligencia artificial. Para ello propuso un experimento que hoy se conoce como el “test de

Turig”. Que consiste básicamente en: (seleccione la verdadera).

Seleccione una respuesta.

a. Método para evaluar el rendimiento y

capacidad de una maquia. “Poder de

procesamiento”

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

c. Prueba de error que determina cuando un

problema tiene solución o no.

d. Procedimientos para evaluar decisiones

lógicas de una máquina.

2. Turing trabajo desde 1952 – 1954 en la Biología Matemática (Morfogénesis). Publicó un trabajo

titulado “Fundamentos químicos de la morfogénesis”. Su principal interés era: (seleccione los

verdaderos).

Seleccione al menos una respuesta.

a. Definir los números áureos y sus

características. Incorrecto

b. Comprender la existencia de

números de Fibonacci en las

estructuras vegetales.

Correcto

c. Comprender la secuencia de

Fibonacci y determinar si es finta o

infinita.

Incorrecto

d. Comprender la phyllotaxis de

fibonacci.

Correcto: Utilizó ecuaciones de reacción-

difusión actualmente usadas en el campo de la

formación de patrones.

Biografía de Alan Turing

3En septiembre de 1939 Inglaterra le declara a guerra a Alemania. A Turing junto con otros

criptógrafos, se les asignó el trabajo de descifrar la máquina “Enigma” del ejército Alemán

que transmitía de manera codificada las coordenadas y comunicaciones que definían las

estrategias de guerra y la ubicación de bombarderos y, misiles, tanques y submarinos.

Para este trabajo Turing ideo:


a. La MUT

b. La MT

c. La

Criptografía

d. El Bombe

Correcto. El Bombe replicaba la acción de varias máquinas Enigma

cableadas una con la otra. Casda uno de los rápidos tambores

rotativos. Simulaba la acción de un rotor del enigma

Biografía de Alan turing

4. Identifique los acontecimientos que dentro del marco histórico sucedieron en torno a la vida del

matemático Alan Turing.


a. En el mismo año que nació Alan

Mathison Turing, aconteció el

hundimiento del trasatlántico

Británico “El Titanic”

Correcto: El hundimiento del Titanic se

desarrolló en la noche del 14 al 15 de abril de

1912 en el océano Atlántico Septentrional frente

a las costas de Terranova. Por otra parte Alan

Mathison Turing nació en Londres, 23 de junio

de 1912

b. Alan Mathison Turing fue criado

siempre al lado de sus padres. Por

eso su cultura y legado que ha

dejado a raíz de las enseñanzas y

educación que ellos le dieron.

c. El Padre de Alan Mathison

Turing: Julius Mathison Turing era

de origen Polaco.

d. Alan Mathison Turing murió a los

48 años de edad. Se cree que fue un

suicidio aunque hay apartes de la

historia que mienten esta versión.


5Turing 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:


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. En 1928, con dieciséis años, al descubrir e

interpretar los trabajos de Albert Einstein

c. Dada la muerte de Christopher Morcom, quién

fue el primer amor. Morcom murió repentinamente

el 13 de febrero de 1930 .

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


Incorrecto

Puntos para este envío: 0/1.

Question 6

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:


a. Determinar las teorías de números ordinales y de algoritmos.

b. Establecer los principios de la criptografía.

c. Definir los conceptos modernos de lógica

d. Establecer las nociones de lo que hoy se conoce como la “Máquina de

Turing” Correcto


Correcto

Act 3: Reconocimiento Unidad No. 1

1

Puntos: 1

Sea el vocabulario {a,b} y la expresión regular aa*bb* Indique cuales cadenas que se

relacionan a continuación son válidas para esa ER


a. {ab, aab, aab, a, aa,bb}

Incorrecto: las cadenas válidas tienen almenos una “b”

después de almenos una “a”

b. {a, b, ab, ba, aab, bba,

aaab}

c. {ab, aab, aaab, abbb,

abb, aa,bb}

d. {ba, ab, b, a}

Incorrecto


Question 2

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:


a. La cadena vacía (lambda)

es un lenguaje regular. Correcto: Lambda es regular.

b. La cadena vacía y el

conjunto vacío no son

lenguajes regulares.

c. {ab} no es regular.

d. {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}.

Correcto


Question 3

Puntos: 1

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

correctamente:


a. Por símbolo no se está haciendo referencia a un

sólo carácter. Los símbolos pueden ser nombres.

b. Por ser un alfabeto un conjunto finito de

elementos, las posibles cadenas que se formen no

pueden ser vacías

c. Las cadenas que se forman a partir de un alfabeto

finito, resultan ser infinitas.

Incorrecto: Las palabras

aceptadas pueden ser infinitas.

d. Dado un alfabeto, podemos formar palabras o

cadenas con los símbolos del alfabeto

Correcto: Es el principio básico

para empezar a tratar con

lenguajes.

Parcialmente correcto

Puntos para este envío: 0.5/1.

Question 4

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


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

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

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


Question 5

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.


a. El alfabeto de

entrada

b. El conjunto

finito de estados.

c. El estado inicial.

d. La función de

transición.

Correcto: Solo la función de transición puede diferenciar los AFD

de los AFND. Las demás opciones pueden ser comunes a ambos

tipos de autómatas y válidas.

Correcto


Question 6

Puntos: 1

Dados los siguientes lenguajes del alfabeto ∑= {0,1}: L1= {0n1n, | n ≥ 1} y L2 = {cadenas

con igual número de 1´s que de 0´s} y L3 = {cadenas en que cada 1 va seguido de al menos

un 0}. Señale la afirmación que es verdadera:

Tenga en cuenta qque se 0n1n (equivale a 0 potencia n 1 potencia n)


a. L1 y L2 son independientes del contexto Correcto: L1 y L2 son independientes de contexto.

b. Ninguno de los lenguajes es regular.

c. Solo L2 y L3 son regulares.

d. Solo L1 es regular.

Correcto

Act 4: Lección Evaluativa Unidad No.1

Question 1

Puntos: 1

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


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. A ∙ (B U C) = (A ∙ B) U (A ∙ C)

Correcto: Se está identificando o

definiendo que la concatenación de

lenguajes es distributiva con

respecto a la unión

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

Correcto


Question 2

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


a. Las transiciones lambda solo son aceptadas en

la descripción de las gramáticas.

Incorrecto: Estas transiciones son

aceptadas en AF.

b. Siempre existe un autómata finito determinista

que reconoce un lenguaje reconocido por un

autómata finito no determinista.

Correcto: Las cadenas vacías

lambda son aceptadas y suelen

presentarse en AFND.

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

d. No existe un autómata finito sin transiciones

(lambda) que reconozca L.

Incorrecto: Si es posible este tipo

de autómatas.

Correcto


Question 3

Puntos: 1

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


a. xzxxxxzxzzx

b. xxxxzxzxzxzx

Correcto: Toda cadena para ese autómata empezará con x y

terminará en una sola x. Se recorre el autómata con la cadena

xxxxzxzxzxzx

c. xxxzxx

d. xzzxzxzx

Correcto


Question 4

Puntos: 1

Cuáles afirmaciones son válidas cuando se trata de analizar el funcionamiento de los

Autómatas Finitos (AF):


a. Los AF son máquinas de memoria

amplia por ser máquinas abstractas

(no reales).

b. En una máquina de estados

finitos, la función de transición

almacena los datos de entrada del

Autómata.

c. Los estados son el único medio de

que disponen los AF para recordar

Correcto: Los estados son el único medio de

que disponen los AF para recordar los eventos

los eventos que ocurren (por ejemplo

que caracteres se han leído hasta el

momento).

que ocurren (por ejemplo, qué caracteres se han

leído hasta el momento); esto quiere decir que

son máquinas de memoria limitada.

d. Los AF son máquinas de memoria

limitada.

Correcto: Los estados son el único medio de

que disponen los AF para recordar los eventos

que ocurren (por ejemplo, qué caracteres se han

leído hasta el momento); esto quiere decir que

son máquinas de memoria limitada.

Correcto


Question 5

Puntos: 1

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


a. Es un Autómata Finito

que acepta la palabra vacía

b. Es un Autómata Finito

Determinista (AFD).

Correcto: Es determinista porque de sus nodos no se

repiten salida pro interacciones con el mismo símbolo. Se

acepta la condición teórico de determinismo.

c. Es un Autómata Finito

No Determinístico (AFND)

d. Es un Autómata Regular

Correcto


Question 6

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


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

b. {101, 210, 20,110,

200}

c. Es un AFND y acepta

cualquier cadena que

inicie con cero (0)

d. {22, 0,1,001122, 12,

012, 022}

Incorrecto


Question 7

Puntos: 1

Analice el siguiente Autómata y determine cuáles apreciaciones son válidas en su análisis:


a. La función de transición define para cada posible combinación

(0,1) un estado nuevo. Incorrecto

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

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

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

Incorrecto


Question 8

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 f por la tabla siguiente:

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


a. 0(010)*

b. 1*(1)

c. 1( 1) (0)*

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

Correcto


Question 9

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


a. Si ω = lambda entonces L (lambda) = { lambda} Correcto: Esta es una

ER

b. Si ω = a y a pertenece ∑ entonces L (ω) no pertenece ∑

c. Si ω = Ø entonces L (ω) = Ø Correcto: Esta es una

ER

d. Si ω* es una ER entonces L (ω*) no es una ER

Correcto


Question 10

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 ∑


a. ∑ (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.

b. ∑ (potencia 0) =

Conjunto de todas las

cadenas sobre el

alfabeto ∑ excepto la

vacía.

c. ∑ (potencia +) =

Conjunto de todas las

cadenas positivas

excepto la vacía

Incorrecto: Conjunto de todas las cadenas 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

Act 5: Quiz 1 - Unidad No. 1

1

Puntos: 1

Para el siguiente autómata determine cuales afirmaciones son válidas cando se trata de

evaluar que cadenas acepta el autómata.


a. Todas las cadenas que tengan igual

número de unos y de ceros son aceptadas.

b. Si una cadena tiene menos de 5 unos,

entonces tiene un número par 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. 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

Correcto


Question 2

Puntos: 1

Las siguientes cadenas:

{Lambda,aaa, bb, bbb, aabb, aba, abaaa, abbaa}

son generadas expresadas por la ER


a. ( a | b)* Correcto

b. (a,b)*

c. (a.b)*

d. (a + b ) *

Correcto


Question 3

Puntos: 1

Este lenguaje:

L (G) = {a (potencia n) b (potencia n) / n>=1}

Es generado por la gramática:


a. S ---> ab| Sab Incorrecto

b. S ---> Sab | aSb

c. S ---> aSb | ab

d. S ---> Sa| Sb

Incorrecto


Question 4

Puntos: 1

Las condiciones mínimas para poder describir un Autómata Finito Determinístico (DFA)

son:


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

b. Identificando el

alfabeto. Correcto: Un autómata puede describirse dando el alfabeto.

c. Identificando el

estado inicial y los

estados finales.



función transición.

d. Identificando la

función de

transición.



función transición.

Correcto


Question 5

Puntos: 1

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

comportamiento de los dos autómatas:


a. Solo un autómata es una máquina de estados que representa un lenguaje

regular

b. Ambos autómatas aceptan las mismas cadenas, como por ejemplo:

{012,011,11,2222,1122,001122}

c. Un autómata es AFD y el otro es AFND

d. Ambos autómatas son AFD Correcto

Correcto


Question 6

Puntos: 1

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


a. La ER que lo representa: (b+ab*a)*ab* Correcto

b. La ER que lo representa es: (b*ab*a)*b*ab* Correcto

c. La Er que lo representa es: (ab*a)*

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

Correcto


Question 7

Puntos: 1

Dada la siguiente ER, el lenguaje que define esta, es el de todas las cadenas que alternan

entre 0 y 1.

(((01)*+(01)*0)+((10)*+(10)*1))

Identifique las cadenas no válidas.


a. {0,1}

b. {01,10,101,010}

c. {11, 0110, 00,11,1011} Correcto: estas son cadenas no validas

d. {010010, 101101,1}

Correcto


Question 8

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:


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


Question 9

Puntos: 1

Sea el alfabeto ∑= {a,b} con la Expresión Regular: a(a+b), identifique las cadenas válidas

que se pueden generar:


a. {a, aab, abb}

b. {aa, ab,}

c. {aba, aab,}

d. {a, b, aa, bb}

Incorrecto: Las cadenas siempre van a empezar por a, seguidas de

una a ó una b

Incorrecto


Question 10

Puntos: 1

Dada la siguiente gramática con las siguientes producciones,

S --> ab

SaSb

que derivaciones son válidas al usar sus reglas:


a. Ba

b. aabb Correcto

c. ab

d. Bbaa



Question 11

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:


a. Al clasificar lenguajes, no se están clasificando máquinas que los

reconozcan, Se clasifican gramáticas que los generan.

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

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

d. Se llama “clase de lenguajes” a conjuntos de lenguajes que comparten

cierta propiedad dada. Correcto

Correcto


Question 12

Puntos: 1

Dentro de la jerarquía y clasificación de los lenguajes (Chomsky) identifique que

asociaciones están erradas.


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

b. Los lenguajes que no poseen

restricciones o de tipo 0, son

reconocidos mediante Autómatas

Finitos No Deterministas (AFND)

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

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



Question 13

Puntos: 1

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


a. No es un autómata válido en diseño

b. No tiene alfabeto definido

c. Es un AF. Correcto

d. Es una aplicación de los autómatas. Un interruptor de luz Correcto

Correcto


Question 14

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.


a. ω = lambda ó cadena vacía y ω = 0 ; Son palíndromos Correcto

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. Los palíndromos son una excepción de los lenguajes regulares y no hacen

parte de la jerarquía de Chomsky

d. Los símbolos de un alfabeto, definen el tipo de lenguaje a que pertenece.

Correcto


Question 15

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.


a. El Palíndromo se puede definir como: (ω = ω potencia R ). Correcto: Ejemplo: ω =

reconocer

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

d. En general (ω1 ω2 ) potencia R ≠ ω1 potencia R ω1 potencia R

pero (ω1 ω2) potencia R = ω2 potencia R ω 1 potencia R Correcto

Correcto


1

Puntos: 1

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

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

Seleccione la opción que sea verdadera.


a. La gramática y el

autómata no generan ningún

lenguaje

b. La gramática y el

autómata son equivalentes.

c. La gramática y el

autómata no son

equivalentes.

Correcto: La gramática y el autómata no son

equivalentes por que no generan el mismo lenguaje

(ejemplo no se genera la cadena vacía con la gramática

dada).

d. Es un autómata finito

determinístico (AFD)

Correcto


Question 2

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.


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

b. Creando un nodo raíz que se etiqueta con el símbolo inicial. Correcto

c. Todos los nodos hoja están etiquetados con símbolos terminales. Correcto

d. Los nodos que no tienen hijos, deben ser etiquetados con símbolos

terminales. Correcto

Correcto


Question 3

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:


a. La gramática no genera la cadena vacía

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

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


Question 4

Puntos: 1

Indique cuál de las siguientes afirmaciones es falsa teniendo en cuenta el determinismo de

los autómatas finitos. (AF).


a. Un autómata finito no determinista de q estados y n símbolos

puede tener a lo sumo n × q2 transiciones

b. El número máximo de transiciones de un autómata finito

determinista depende del número de estados y del número de

símbolos del alfabeto del autómata

Esta afirmación

es válida

c. Un autómata finito determinista de q estados y n símbolos tiene n

× q transiciones

d. Un autómata finito no determinista puede tener un número

ilimitado de transiciones distintas

Incorrecto


Question 5

Puntos: 1

En una Gramática Regular, un componente de la Cuadrupla que la compone, es el Alfabeto.

Este esta caracterizado como:


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


Question 6

Puntos: 1

Toda Gramática Libre de Contexto (GIC) puede ser transformada en un GIC en Forma

Normal de Chomsky.

Indique cuál es el primer paso jerárquicamente para que se pueda hacer esta

transformación.


a. Para ello lo primero que hay que hacer es suprimir

las producciones nulas y unitarias

Correcto: Acorde al algoritmo

este es el primer paso

b. Reemplazar variables en el orden de las

producciones dadas.

c. Añadir variables para cada producción.

d. Añadir producciones a la derecha de la gramática

El algoritmo para eliminar los símbolos y producciones inútiles consta de dos pasos

fundamentales: 1. Eliminar las variables desde las que no se puede llegar a una palabra de T

y las producciones en las que aparezcan. 2. Eliminar aquellos símbolos que no sean

alcanzables desde el estado inicial, S, y las producciones en las que estos aparezcan.

Correcto

Act 8: Lección Evaluativa Unidad No. 2

1

Puntos: 1

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


a. La gramática que lo genera es: S -->SaS |

SbS | Sc | a Incorrecto

b. La gramática que lo genera es: S --> SbS

| ScS | a Correcto

c. La derivación de la cadena {abaca} es: S

---> ScS ---> SbScS ---> abScS ---> abacS

---> abaca

Incorrecto; si reconoce la cadena pero

genera un árbol de derivación diferente

por la izquierda.

d. La derivación de la cadena {abaca} es: S

--> SbS --> SbScS ---> SbSca ---> Sbaca --

-> abaca

Correcto

Correcto


Question 2

Puntos: 1

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


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

b. G= {S -->0B | 0A , A ---> 1B | lambda , B ---> lambda

c. G = { S --->A |lambda , A ---> 0B | lambda,, B ---> lambda}

d. G = { S --->B |lambda , A ---> 1B | lambda,, B ---> lambda}

Correcto


Question 3

Puntos: 1

Considere la gramática G = {S → aS | aA | a , A → aA | bS } ¿Cuál es la longitud de las

cadenas que puede generar y cuáles son esas cadenas, identifíquelas?


a. 10 y son {Ø, a, aa, ab, ba, bb, aba,

abab, bbb, b }

b. 7 y son {a,aa,aaa,aaaa, abaa, aaba,

abab}

Correcto: Son 7 cadenas: {a,aa,aaa,aaaa,

abaa, aaba, abab}

c. 5 y son {Ø, a, aa, ab, ba }

d. 6 y son {a, aa, ab, ba, bb, aba }

Correcto


Question 4

Puntos: 1

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

siguientes:


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

b. La pila debe tener

lambda como elemento

final.

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

d. La pila debe estar

vacía. Correcto: 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.

Correcto


Question 5

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?


a. Nunca, Queda en un bucle ya que solo recorre un símbolo.

b. No todas las veces, dado que puede tratarse de un autómata no

determinista. Correcto

c. Sí, siempre.

d. Si, si M es un autómata finito.

Correcto


Question 6

Puntos: 1

Acerca del funcionamiento de un Autómata de Pila, cuál de las siguientes operaciones o

comportamientos NO las hace este autómata.


a. Una de las condiciones para que una

palabra de entrada sea aceptada en un AP

la pila debe estar vacía.

b. Al igual que los AF, los AP tienen

estados finales, que permiten distinguir

cuando una palabra de entrada es aceptada

c. La pila no tiene límite en sus extremos.

A diferencia de las MT que son cerradas

por la izquierda.

Incorrecto: La pila, está limitada en un

extremo por definición, cuando se lee un

elemento de la pila, este desaparece o se

saca y cuando se escribe en la pila se

introduce un elemento.

d. En la Pila una transición de un estado a

otro Arroja la información de lo que sale

de la pila (tope), no de lo que entra ya que

el avance es progresivo hacia adelante y no

hacia atrás.

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

Incorrecto


Question 7

Puntos: 1

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


a. A cada símbolo de entrada (Incluyendo la cadena vacía) Correcto

b. A cada estado Correcto

c. A cada movimiento de la pila Correcto

d. A cada símbolo topo de la pila Correcto

La función de transición aplica cada estado, cada símbolo de entrada (incluyendo la cadena

vacía) y cada símbolo tope de la pila en un conjunto de posibles movimientos. Cada

movimiento parte de un estado, un símbolo de la cinta de entrada y un símbolo tope de la

pila. El movimiento en sí consiste en un cambio de estado, en la lectura del símbolo de

entrada y en la substitución del símbolo tope de la pila por una cadena de símbolos.

Correcto


Question 8

Puntos: 1

Indique cuál de las siguientes afirmaciones es verdadera:


a. Para reconocer un lenguaje regular

mediante un autómata de pila el alfabeto

de la pila debe contener al menos un

símbolo

b. Para reconocer un lenguaje regular

mediante un autómata de pila no es

necesario que el alfabeto de la pila

contenga ningún símbolo

Correcto: Cualquier lenguaje independiente

del contexto puede ser aceptado por un

autómata de pila, y todos lenguajes

regulares son independientes del contexto.

c. Con un autómata de pila no puede

reconocerse un lenguaje regular

d. Cuando se dice que un AFPD

(autómata de pila determinista) es más

sencillo , se refiere a que es menos

potente y no se refiere ala sencillez de su

diseño.

Correcto:

Correcto


Question 9

Puntos: 1

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


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. Combinar gramáticas

d. Reutilizar gramáticas y

modificarlas para ajustarlas al

lenguaje generado

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


Question 10

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:


a. Un árbol ordenado y etiquetado D es un árbol de derivación para una

gramática libre de contexto G(A) Correcto

b. La representación de las derivaciones de la gramática siempre se hacen de

forma vertical. Nunca de forma comprimida u horizontal

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

Correcto

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

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.

Correcto

Act 9: Quiz 2 - Unidad No. 2

Question 1

Puntos: 1

Indique cuál de las siguientes afirmaciones es verdadera:


a. Los autómatas finitos no deterministas son más potentes que los

autómatas finitos deterministas

b. Un PDA es siempre no determinista por que la cinta es infinita y puede

generar muchas combinaciones en las cadenas que lee.

c. En un diagrama completo que represente a un autómata finito

determinista, de cada estado sale un arco por símbolo y sólo uno Correcto

d. Los AP son siempre deterministas. El no determinismo no se hace

presente por que los AP poseen un mecanismo adicional de manejo de

memoria

Correcto


Question 2

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


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}

Incorrecto: El autómata más sencillo que

genera es un AF. Además la cadena

{abab} es rechazada.

b. La cadena más sencilla que genera el

L(G) es: {aba}

Incorrecto: La cadena más sencilla que

genera es {a}. De acuerdo a la ER que se

genera por el L(G).

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


Question 3

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:


a. Un AP se puede combinar con una MT siempre y cuando lean y acepten

el mismo lenguaje.

b. Solo la operación de Unión de los lenguajes de dos AP es permitida.

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

d. Las operaciones de combinar AP solo es viable cuando los dos

Autónomas leen el mismo alfabeto.

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


Question 4

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}


a. S --->aAc ; A--->aAc | aAc | bBc ;

B ---> bBc | bc

Incorrecto: estas producciones generan la

cadena {aaabbbcccccc}

b. S --->aAc ; A--->aAc | bBc ; B ---

> bc

c. S --->aAc ; A--->bBc ; B ---> bc

d. S --->aAc ; A--->aAc | bBc ; B ---

> bBc | bc

Incorrecto


Question 5

Puntos: 1

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


a. S-->ABs

b. S-->a

c. A -->sB

d. A --> B Correcto

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

Correcto


Question 6

Puntos: 1

Indique cuál de las siguientes afirmaciones es falsa:


a. La unión de un número finito de

lenguajes estructurados por frases es

un lenguaje estructurado por frases

b. La intersección de un lenguaje

regular con un lenguaje independiente

del contexto es siempre un lenguaje

regular.

Correcto: La intersección del lenguaje regular

xn ym y el lenguaje independiente del

contexto xn yn es el lenguaje independiente

del contexto no regular xn yn

c. La intersección de dos lenguajes

estructurados por frases es un lenguaje

estructurado por frases

d. Todo lenguaje cuyo complementario

sea un lenguaje finito es independiente

del contexto

Correcto


Question 7

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.


a. S –> 0A0 | 1S0 | 2 |

0

b. S –> 0A0 | 1S2 | 10

c. S –> 0A0 | 1S2 | 1 |

0

d. S –> 0A0 | 1S1 | 2

Correcto: Si se desarrolla el árbol de derivación se obtiene la

cadena 01210

Correcto


Question 8

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):


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


Question 9

Puntos: 1

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


a. Un Autómata No determinístico pero Finito

b. Un Autómata Determinístico Finito.

c. Un Pushdown Automaton (PA) Correcto

d. Una Turing Machine (TM)

Añadir al AF un almacenamiento auxiliar, que llamaremos pila, donde se podrían ir

depositando caracter por caracter cadenas arbitrariamente grandes, es el primer paso a la

construcción de un AP a partir de un simple AF.

Correcto


Question 10

Puntos: 1

Cual de las siguientes afirmaciones se asocia correctamente al diseño y funcionamiento de

los árboles de derivación.


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. En los árboles de derivación, no es

necesario usar nodo raíz

d. Los lenguajes generados por una

Gramática Independiente del Contexto son

llamados Lenguajes Regulares

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


Question 11

Puntos: 1

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

producciones:


a. S –> 0A –> 00A –> 001S –

> 0010 A –> 00100

Correcto: Ambas producciones aplican a la gramática

con cadenas válidas como 0100 y 00100

b. S –> 0A –> 00A –> 001 A

–> 0010 Incorrecto: las producciones no aplican a la gramática.

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 –> 0A –> 00A –>

000 Incorrecto: Las producciones no aplican a la gramática.

Correcto


Question 12

Puntos: 1

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


a. Σ∪Σ

b. Σ∗×Σ∗

c. Σ×Σ

d. (Σ*)* Correcto: (Σ*)*=Σ*

La concatenación de dos lenguajes es el lenguaje que resulta al concatenar las respectivas

cadenas (la concatenación de dos cadenas es una nueva cadena) y por tanto pertenece a Σ*.

Σ∪Σ=Σ ; Σ×Σ es el conjunto de pares ordenados formados por dos símbolos de Σ, y Σ*×Σ*

es el conjunto de pares ordenados formados por dos cadenas de Σ*.

Correcto


Question 13

Puntos: 1

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

falsa:


a. Para cualquier prefijo de una cadena generada por la

gramática se verifica que el número de letras a es

mayor o igual al número de letras b. Prefijo de una

cadena w es toda cadena no vacía x para la que existe

una cadena u tal que w = xu

b. La cadena {b} es rechazada

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

d. El lenguaje generado por la gramática es

estructurado por frases

Correcto


Question 14

Puntos: 1

Dado el siguiente árbol de derivación, identifique las apreciaciones válidas cuando se

analiza su comportamiento y diseño:


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

b. El árbol representa las cadenas que inician en

dos a”s seguida de una o más a”s de un lenguaje

regular

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

d. La gramática está representada como G = { S -

-->lambda | aS}

Correcto


Question 15

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:


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.

c. S → aSa, S→bSb, S→aRb, S→bRa, R→bRb,

R→aRa, R→bRa, R→c.

d. S → aSa, S→bSb, S→aRb, S→bRa, R→aRb,

R→bRa, R→c.

Incorrecto: esa gramática no

genera la cadena aacab

Incorrecto


Question 1

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:


a. Las máquinas reales tienen mayor poder de cómputo que las Máquinas

de Turing, aunque resuelvan los mismos problemas. Incorrecto

b. La máquina de Turing, tiene mayor poder de cómputo que las reales,

aunque resuelvan los mismos problemas.

c. Toda función computable tiene un algoritmo decidible pro una MT

d. Una MUT es funcional y eficiente tanto como una máquina real.

Incorrecto


Question 2

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:


a. Existe un procedimiento definido que determina la ambigüedad del

problema

b. Si no se logra representar con un diagrama de Moore el problema.

c. Si no existe un algoritmo total para determinar si la propiedad y objetivo

del problema es verdadera. Correcto

d. Si no existe un procedimiento efectivo para determinar si la propiedad es

verdadera (no existe una Máquina de Turing MT). Correcto

Correcto


Question 3

Puntos: 1

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

verdaderas:


a. En una computadora, el número de estados

viene representado por el contenido de la

memoria.

Correcto

b. En una MT el nº de estados depende del

algoritmo.

c. En cuanto al orden de ejecución de las

instrucciones, En la estructura Von Neumann el

secuenciamiento lo marca el orden de

colocación de las instrucciones en la memoria

interna y viene asegurado por el contador de

programa.

Correcto: En Una máquina de Turing, el orden

de ejecución de las instrucciones si está definido,

lo marca en todo instante el estado de la

máquina y el carácter de la cinta apuntado, que

son los dos datos que determinan la quíntupla

que ha de ser ejecutada.

d. En una MT el orden de ejecución de las

instrucciones no está definido.



Question 4

Puntos: 1

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

computacionales es:


a. Usando el método de

“Halting”

b. Usando el método de

Reducción “Reducibilidad de

Turing”

Correcto: La reducibilidad ha permitido llegar a

determinar la indecibilidad en algunos problemas

computacionales

c. Usando el método de “

Decibilidad de Teorías Lógicas”

d. Usando el método de las

“Funciones computables”

Correcto


Question 5

Puntos: 1

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


a. Nivel de ruido

b. La velocidad que se

mantenga.

Correcto: Cuando se transmite información, las variables

más importantes son: la velocidad y la veracidad (libre

de errores).

c. La veracidad de los datos

en todo su sentido.

Correcto: Cuando se transmite información, las variables

más importantes son: la velocidad y la veracidad (libre

de errores).

d. Redundancia

Correcto


Question 6

Puntos: 1

Algunos problemas computacionales suelen tener características de “indecibilidad”. Las

estrategias usadas para poder determinar esta característica en estos problemas es:


a. Mediante funciones

computables, determinar la

ambigüedad de solucione y

seleccionar la que tenga

menos restricciones.

Incorrecto

b. Fraccionar o reducir el

problema e otros más

pequeños

Correcto: La reducibilidad ha permitido llegar a

determinar la indecibilidad en algunos problemas

computacionales: Una manera más simple de

determinar la indecibilidad es utilizando el método de

reducción,

c. Al reducir un problema a

otros más pequeños, de tal

forma que la solucionar uno,

tendremos la solución del

otro.

Correcto: dado un problema P1, este se reduce a

solucionar P2. Es decir, si solucionamos P2, tenemos

solucionado P1. De esta manera hemos convertido un

problema en otro.

d. Mediante la decibilidad de

teorías lógicas. Icorrecto

Correcto

Act 12: Lección Evaluativa Unidad No. 3

Question 1

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. Decidir si un lenguaje que se genera es vacío o no, es un problema que sí

tiene solución por una MT.

b. Las MT por ser la máquina abstracta más poderosa, soluciona cualquier

problema que en teoría sea indecidible.

c. Hay infinitos problemas para los que no se va a tener una MT que los

resuelva (ni siquiera los reconozca). Correcto

d. Con un computador real, se puede determinar con certeza cualquier

problema en el sentido si es decidible o no.

Una MT que los resuelva (ni siquiera los reconozca). También se ha formulado la tesis de Church-

Turing, que determina el límite de los computadores actuales Correcto


Question 2

Puntos: 1

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

computadoras reales.


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

c. Las MUT son de un solo propósito. Las máquinas reales interpretan

muchos programas escritos en diferentes lenguajes (multipropósito).

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

Correcto


Question 3

Puntos: 1

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

Turing:


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

b. Una máquina de Turing cuyo estado inicial coincida con el estado de

parada acepta toda cadena Correcto

c. El diseño de una MT es procedimentalmente sencillo para programar

lenguajes de máquinas reales.

d. Cualquier lenguaje puede ser reconocido por una máquina de Turing



Question 4

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.


a. 10

b. 00

c. 11

d. 01 Correcto

Correcto


Question 5

Puntos: 1

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

Los códigos convolucionales, suelen describirse mediante:


a. Árboles, Trellis y Diagrama de estados. Correcto

b. Árboles y diagramas de estados

c. Autómatas finitos (grafos). Máquinas de estados

d. Autómatas finitos (grafos). Máquinas de estados

Correcto


Question 6

Puntos: 1

De las siguientes características marque dos de las que corresponden con la cinta de una

Máquina de Turing


a. Cinta Finita hacia la

derecha, por que al

extremo izquierdo

siempre esta un topeo

carácter blanco.

b. Puede contener un

caracter por celda

Correcto: En la MT la cabeza lectora es de lectura y

escritura, por lo que la cinta puede ser modificada en curso

de ejecución. Además, en la MT la cabeza se mueve

bidireccionalmente (izquierda y derecha), por lo que puede

pasar repetidas veces sobre un mismo segmento de la cinta

c. Se puede escribir en

ella

Correcto: En la MT la cabeza lectora es de lectura y

escritura, por lo que la cinta puede ser modificada en curso

de ejecución. Además, en la MT la cabeza se mueve

bidireccionalmente (izquierda y derecha), por lo que puede

pasar repetidas veces sobre un mismo segmento de la cinta.

d. Cinta Infinita hacia la

izquierda

La máquina de Turing (abreviado MT) tiene, como los autómatas finitos, un control finito,

una cabeza lectora y una cinta donde puede haber caracteres, y donde eventualmente viene

la palabra de entrada. La cinta es de longitud infinita hacia la derecha, hacia donde se

extiende indefinidamente, llenándose los espacios con el caracter blanco

Correcto


Question 7

Puntos: 1

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


a. Mediante un autómata

de pila, pero no mediante

un autómata finito

b. Mediante una máquina

de Turing, pero no

mediante un autómata de

pila

c. No es un problema

soluble. Es un problema

de decisión

d. Mediante un autómata

finito

Correcto: Al no tener memoria, el ascensor es una máquina

que experimenta una transición de estado como función

exclusiva del estado en que se encuentra y el evento que

recibe (botón pulsado por un usuario).

Al no tener memoria, el ascensor es una máquina que experimenta una transición de estado

como función exclusiva del estado en que se encuentra y el evento que recibe (botón

pulsado por un usuario).

Correcto


Question 8

Puntos: 1

Con que configuración de cinta se detendrá la máquina de Turing mostrada a continuación si

comienza con la cinta configurada como xxxΔΔΔ . Asuma el orden con que están

numerados los estados para el proceso.

La "V" indica la posición en la que estaría la máquina. Para el caso de los s+ímbolos "x"

estaría representado como (x)


a. xxxΔVV

b. xxxΔΔV

c. xx(x)ΔVΔ

Correcto: Se inicia con el estado de la máquina en 1 con xxxΔΔΔ y finaliza en el estado 3

con xxxΔΔΔ

d. xxxVΔΔ

Correcto


Question 9

Puntos: 1

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

verdaderas).


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

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

c. El problema de “Halting” es el primer problema indecidible mediante

maquinas de Turing Correcto

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

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


Question 10

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.


a. 010 Correcto

b. 110

c. 100

d. 001

Correcto

Act 13: Quiz 3 Unidad No. 3

Question 1

Puntos: 1

Las máquinas de Turing (MT) son también aceptadoras de lenguajes. Analice si los

lenguajes dados aplican a la tarea que cumplen estas máquinas


a. El lenguaje {w pertenece {a,b}* | w

contiene al menos una b} no es independiente

del contexto y por tanto no es decidible por

máquinas de Turing.

Incorrecto

b. El lenguaje {w pertenece {a,b}* | w

contiene al menos una a} es decidible por


Correcto: Esta opción (El lenguaje)

descrito es independiente del contexto,

y por tanto decidibles por máquinas de

Turing

c. El lenguaje {w pertenece {a,b}* | w

contiene tantas a´s como b´s} no es decidible

por máquinas de Turing

Incorrecto: Si es decidible,

d. El lenguaje {w pertenece {a,b}* | w

contiene tantas a´s como b´s} es decidible por


Correcto: Esta opción (El lenguaje)

descrito es independiente del contexto,

y por tanto decidibles por máquinas de

Turing

Correcto


Question 2

Puntos: 1

Dada la siguiente Máquina de Turing (MT), determine que afirmaciones son válidas para su

análisis:


a. La máquina acepta palabras que empiezan con

“b”

b. La máquina acepta palabras que empiezan con

“a” Correcto: La letra de entrada de la MT es a, y

cuando llega a halt es aceptada la cadena.

c. Si la primera letra no es una “a” la MT cae en

un ciclo infinito leyendo y escribiendo “a” Incorrecto: Al empezar con “b” la MT entra

en un bucle escribiendo “b”.

d. Si la primera letra no es una “a”, la MT cae en

un ciclo infinito leyendo y escribiendo “b”



Question 3

Puntos: 1

La decodificación para canales con ruido usando las técnicas de codificación

convolucional, se hace mediante el algoritmo de Viterbi. El objetivo de aplicar este método

es:


a. Que los bits redundantes que

acompañan al dato, ayuden a

detectar y corregir errores en la

transmisión. El método separa

los bits redundantes y muestra

el dato.

b. Identificar la mayor cantidad

de bits de control para

compararlos con los bits de

datos.

c. Encontrar el último estado

que posee el error.

d. Reducir la cantidad de

transiciones y cálculos cuando

se presentan los bits

redundantes y datos codificados.

Correcto: Lo que se consigue aplicando este método

es reducir el número de cálculos. Según el algoritmo

de Viterbi, para reducir el número de cálculos, cada

vez que dos trayectos (también llamados ramas) se

junten en un estado en el Diagrama de Trellis, el de

mayor métrica acumulada se desecha en la búsqueda

del trayecto óptimo

La codificación convolucional se decodifica con ayuda del algoritmo de Viterbi. El proceso

consiste en desechar algunos de todos los caminos posibles. Lo que se consigue aplicando

este método es reducir el número de cálculos.

Correcto


Question 4

Puntos: 1

Dada la siguiente Maquia de Turing (MT). Analice su comportamiento.


a. No es una maquina válida ya que no define un

estado final que acepta unas cadenas (no

interpreta un lenguaje definido).

b. Si se convierte el estado q0 en final, aceptará

todas las posibles combinaciones de {01}.

Aceptará secuencias de ceros y uso.

Correcto: Si además se exige que el

transductor termine en un estado

final y pare, si la entrada es

correcta, es decir, una simple

secuencia de ceros y unos

c. Es una máquina que solo acepta lenguajes

regulares.

d. Esta máquina de Turing que se comporta

como transductor, porque simplemente genera

una salida en la cinta.

Correcto. Escribe en la cinta y la

recorre.

Correcto


Question 5

Puntos: 1 Una analogía funcional, operacional de una Máquina de Turing con un componente físico real

podría ser: Seleccione una respuesta.

a. Un compilador

b. Un codificador secuencial con estados fijos pero con memoria (ej:

codificador convolucional)

c. Soluciones computacionales de arquitecturas híbridas de algoritmos

infinitos.

d. Sistemas de cómputo basados en arquitecturas como las de Neumann Correcto

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 si

dispusieran de recursos ilimitados de tiempo y espacio. Como consecuencia, 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 y en la práctica no todos lo alcanzan. Los lenguajes con poder de expresión

equivalente al de una máquina de Turing se denominan Turing completos Correcto


Question 6

Puntos: 1

Dependiendo de los diferentes tipos de Máquinas de Turing (MT), estas se comportan de

manera diferente en la solución de problemas. Para una MT MULTIPISTA, indique una

propiedad válida de esta.


a. La cinta está en un número infinito de

k pistas. Por eso es MULTIPISTA

b. En esta MT no se inicializan las cintas

por que tienen muchas pistas.

c. Por cada cinta , requiere de un estado

de aceptación “halt”

d. La cinta esta dividida en un número

finito de k pistas

Correcto: En el modelo multipista, la cinta

está dividida en un número finito de k

pistas.

Hay ciertos modelos de computación relacionados con las máquinas de Turing, que poseen

el mismo potencial como reconocedor de lenguajes que el modelo básico. Dentro de esas

modificaciones, una muy particular es la MULTIPISTA que resulta muy efectiva para

solución de problemas extensos.

Correcto


Question 7

Puntos: 1

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:


a. Se mueve la cabeza de la cinta

a la izquierda, a la derecha o se

detiene.

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. Cambio de estado.




c. Imprime un símbolo en la cinta

reemplazando el símbolo leído.




d. Todo movimiento del cabezal

vacía la cinta y la inicializa en

cero.

Incorrecto: En una MT de Turing no es cierto que

el movimiento del cabezal, implique vaciar la cinta

o inicializar los ímbolos iniciales

La palabra de entrada en la MT está escrita inicialmente en la cinta, como es habitual en

nuestros autómatas, pero iniciando a partir de la segunda posición de la cinta, siendo el

primer cuadro un caracter blanco. Como la cinta es infinita, inicialmente toda la parte de la

cinta a la derecha de la palabra de entrada está llena del caracter blanco (t).

Correcto


Question 8

Puntos: 1

La máquina universal de Turing esta diseña para realizar cualquier calculo especifico –

particular debido a que:


a. Es un intérprete de la

información de salida

b. Las instrucciones se

basan en una fase del

algoritmo universal

c. Parará cuando el

cálculo sea

indeterminado.

d. Es capaz de ejecutar

cualquier algoritmo

Respuesta Correcta: una M T capaz de ejecutar cualquier

algoritmo; es decir capaz de realizar los cálculos que

realizaría cualquier otra MT, o sea, capaz de simular (tener

el mismo comportamiento) cualquier MT particular.

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

Correcto


Question 9

Puntos: 1

Acerca de las Máquinas de Turing, Cuál de las siguientes afirmaciones es cierta:


a. Conociendo la posición del cabezal,

se conoce la situación actual de la

máquina de Turing.

b. Una máquina de Turing cuyo estado

inicial coincida con el estado de parada

acepta toda cadena

Correcto: Las acciones que puede ejecutar

en la cinta la MT pueden ser: Escribe un

símbolo en la cinta, o Mueve la cabeza a la

izquierda o a la derecha Estas dos acciones

son excluyentes, es decir, se hace una o la

otra, pero no ambas a la vez.

c. Es posible que un lenguaje sea

estructurado por frases pero no exista

ninguna máquina de Turing que se

detenga exclusivamente cuando las

cadenas escritas en su cinta pertenezcan

al lenguaje

d. Cualquier lenguaje puede ser

reconocido por una máquina de Turing

La operación de la MT consta de los siguientes pasos: 1. Lee un caracter en la cinta 2.

Efectúa una transición de estado 3. Realiza una acción en la cinta

Correcto


Question 10

Puntos: 1

Una de las bases o fundamentos en que se apoyaba el PRINCIPIO DE CHURCH-TURING

estaba fundado en aspectos de:


a. La lógica computacional

b. La aplicación de funciones computables

c. La simulación Correcto

d. El diseño computacional

"Todo proceso físico puede ser simulado por un dispositivo universal de computación."

Correcto


Question 11

Puntos: 1

La ejecución de esta máquina de Turing indica que:


a. Máquina que recorrerá las cadenas hasta el final de la cinta

pero se devolverá al extremo izquierdo (L)

b. Si se comporta como máquina reconocedora de lenguajes,

aceptara solo cadenas que contengan pares de uso y pares de

ceros sin importar su combinación

c. Es una máquina que recorrerá “cualquier cadena”

(combinación de 0´s y 1´s hasta el final de la cinta

Correcto: Máquina

que va al final de la

cinta

d. Si se ejecuta o se comporta como un Transductor, para la

cadena 00110011 , la salida va a ser 1. Correcto

Correcto


Question 12

Puntos: 1

El caractér blanco que se ubica en la parte derecha de la cinta de una Máquina de Turing,

está presente dada la condición de:


a. La cinta es infinita a la derecha Correcto

b. La cinta es infinita a la izquierda y finita a la derecha

c. La cinta es de solo lectura

d. La cinta es finita a la derecha y a la izquierda

La palabra de entrada en la MT está escrita inicialmente en la cinta, como es habitual en

nuestros autómatas, pero iniciando a partir de la segunda posición de la cinta, siendo el

primer cuadro un caracter blanco. Como la cinta es infinita, inicialmente toda la parte de la

cinta a la derecha de la palabra de entrada está llena del caracter blanco

Correcto


Question 13

Puntos: 1

Seleccione cuál de las siguientes situaciones no es posible cuando una máquina de

Turing determinista examina una cadena: Seleccione una respuesta.

a. El problema de parada solo aplica a

Máquinas de Turing no deterministas. Las

Deterministas solucionan este problema

b. Se produce una terminación anormal (es

decir, la cabeza lectora se desplaza a la

izquierda de la primera celda de la cinta)

c. La máquina no se detiene nunca

d. La máquina abandona los cálculos por no

encontrar ninguna transición aplicable

Correcto: Puesto que la máquina es

determinista, necesariamente encuentra

siempre una transición aplicable.

Ya que cualquier máquina de Turing determinista es también no determinista, es lógico que

una máquina de Turing determinista se pueda simular mediante una no determinista.

También una máquina de Turing determinista puede simular una no determinista. Por tanto,

no se gana ninguna potencia adicional a causa del no determinismo.

Correcto


Question 14

Puntos: 1

Dentro de los componentes de una máquina de Turing (MT), está el símbolo “blanco” B. El

comportamiento de este símbolo es:


a. Están situados al extremo izquierdo de la cinta.

b. También pertenece al alfabeto de cadenas a reconocer.

c. Indica un movimiento nulo de la cabeza lectora.

d. Aparece en todas las casillas excepto en aquellas que contienen los

símbolos de entrada. Correcto

Corresponde a la formalización de las Máquinas de Turing (MT) como un séptuplo en la

que hace parte el símbolo blanco.

Correcto


Question 15

Puntos: 1

E número de estados posibles para un diagrama de estados está dado por:


a. 2( potencia k(m-1)) Dónde: K= la secuencia en cantidad de bits que van a

entrar al codificador. m= la memoria del codificador ( es restringida) n = es

una salida codificada (número de bits).

Correcto

b. 2( potencia n) Dónde: K= es el número de bits de la cadena a evaluar

(antes de ser codificada). m= la memoria del codificador ( es restringida) n =

es una salida codificada (número de bits). Para un codificador convolucional

de ratio R = ½ co K=1 El total de estados es cuatro.

c. 2( potencia k(m-1)) Dónde: K= es el número de bits de la cadena a

evaluar (antes de ser codificada). m= la salida del codificador Si K =1 ; m=

3. El total de estados es cuatro.

d. 2( potencia k(n-1)) Dónde: K= es el número de bits de la cadena a evaluar

(antes de ser codificada). m= la memoria del codificador ( es restringida) n =

es una salida codificada (número de bits). Si K =1 ; n= 3. El total de estados

es cuatro.

Correcto

automatas y lenguajes formales

Documents