AUTÓMATAS Y LENGUAJES FORMALES: Act 12: Lección Evaluativa 3

Todas correctas

1.

 Una Máquina de Turing (MT) de k cintas tiene las siguientes características: 

Seleccione al menos una respuesta. 

 a. En cada paso, lee simultáneamente los k caracteres bajo los cabezales, y toma una decisión basada en la k-upla Correcta

 b. En cada movimiento se pasa a un nuevo estado y realiza una acción en cada cinta Correcta

 c. La MT de k cintas lee tres lenguajes y tres alfabetos diferentes acorde a la k-upla que se define en la función de transición.

 d. Tiene un cabezal en cada cinta. Correcta

2.

Una Máquina de Turing (MT) se puede comportar como un aceptador de un lenguaje. Si colocamos una cadena w en la cinta, situamos la cabeza de lectura/escritura sobre el símbolo del extremo izquierdo de la cadena w y ponemos en marcha la máquina a partir de su estado inicial. Para que w sea aceptada se requiere: 

Seleccione una respuesta.

 a. Si después de una secuencia de movimientos, la Máquina de Turing (mt) llega a un estado final y para Correcto

 b. Que se complete un clico así: Inmediatamente después del primer ciclo de lectura del cabezal a la cinta. c. Que la cinta no haya sido inicializada.

 d. Que el estado final contenga la cadena vacía o nula

3.

De las siguientes afirmaciones, cuáles NO aplica o corresponde al concepto de Máquinas de Turing (MT) y su funcionamiento : 

Seleccione al menos una respuesta. 

 a. La palabra de entrada en la MT no está escrita inicialmente en la cinta. Esta solo se escribe la final del cálculo cuando es aceptada.  Correcto

 b. En realidad una máquina de Turing que siempre mueve su cabeza a la izquierda se diferencia de un autómata finito principalmente en el mecanismo de aceptación de cadenas: una máquina de Turing entra en un estado de aceptación en cuanto concluye sus cálculos  Correcto

 c. Una máquina de Turing es un aceptador de lenguaje.

 d. Los lenguajes regulares podrían ser aceptados por máquinas de Turing que siempre moviesen su cabeza a la izquierda. Correcto

4.

 Indique cuál de las siguientes afirmaciones aplica correctamente al funcionamiento o comportamiento de una Máquina de Turing. (MT): 

Seleccione una respuesta. 

 a. Con una única máquina de Turing, ya sea de una o varias cintas, determinista o no determinista, sólo es posible reconocer un lenguaje

 b. Es posible diseñar una máquina de Turing de tres cintas que reconozca tres lenguajes. Correcta

 c. Existen solo MT de una sola cinta

 d. Con una única máquina de Turing pueden reconocerse tres lenguajes: el lenguaje de las cadenas que acepta, el lenguaje de las cadenas que rechaza y el lenguaje de las cadenas que llevan a la máquina a un bucle de ejecución infinita.

5.

 Acerca de los problemas de Hilbert. Que análisis son verdaderos acerca de lo que se postuló en los "PROBLEMAS DE HILBERT" 

Seleccione al menos una respuesta.

 a. Este problema recibió el nombre de “Entscheidungsproblem”, resolverlo significaría que para cualquier problema bien definido existiría un algoritmo capaz de resolverlo. Correcto

 b. Los problemas de Hilbert son una lista de 23 problemas matemáticos compilados por el matemático alemán David Hilbert para la conferencia en París del Congreso Internacional de Matemáticos de 1900. Correcto

 c. Los problemas de Hilbert se basaban en un modelo matemático ya existente.

 d. La intención de Hilbert era conseguir un modelo matemático formal, completo y consistente, en el que a través de un algoritmo, se pudiese determinar la veracidad o falsedad de cualquier proposición formal. Correcto

6.

Seleccione cuál de las siguientes situaciones no es posible cuando una máquina de Turing determinista examina una cadena: 

Seleccione una respuesta. 

 a. La máquina abandona los cálculos por no encontrar ninguna transición aplicable Correcta

 b. La MT no define un estado de parada o de aceptación halt.

 c. La máquina no se detiene nunca

 d. Se produce una terminación anormal (es decir, la cabeza lectora se desplaza a la izquierda de la primera celda de la cinta)

7.

 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. 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. Cuando se desea que una MT no acepte una palabra, simplemente se debe configurar para que llegue a un estado halt de parada o stop.

 d. Una máquina de Turing cuyo estado inicial coincida con el estado de parada acepta toda cadena Correcta

8.

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

Seleccione una respuesta.

 a. Mediante un autómata finito Correcta

 b. No es un problema soluble

 c. Mediante una máquina de Turing, pero no mediante un autómata de pila

 d. Mediante un autómata de pila, pero no mediante un autómata finito

9.

 Indique cuál de las siguientes afirmaciones son verdaderas acerca de la Tesis que formuló Alan Turing. 

Seleccione al menos una respuesta. 

 a. La tesis de Turing implica que para todo lenguaje existe una máquina de Turing que lo acepta, ya sea el alfabeto finito o infinito.

 b. Turing describía en su artículo que a través de su máquina había conseguido caracterizar de un modo matemático el número de funciones calculables, usando para ello un algoritmo Correcto

 c. La máquina de Turing es tan eficiente como cualquier dispositivo de computar  Correcto

 d. La tesis de Turing implica que los lenguajes más generales que existen son los lenguajes estructurados por frases.

10.

 Cuál de las siguientes apreciaciones no aplica para el funcionamiento de la Máquina de Turing (MT). 

Seleccione una respuesta.

 a. La palabra de entrada en la MT está escrita inicialmente en la cinta.

 b. Por definición, al iniciar la operación de la MT, la cabeza lectora está posicionada en el carácter blanco a la izquierda de la palabra de entrada, el cual es el cuadro más a la izquierda de la cinta.

 c. Las informaciones necesarias para resumir la situación de una MT en medio de un cálculo son: Estado en que se encuentra la MT, Contenido de la Cinta y Posición d ela cabeza.

 d. El desplazamiento de la cabeza de una Máquina de Turing, se realiza en un solo sentido, y no hacia ambos lados. Correcta

11.

Una de las siguientes afirmaciones corresponde correctamente al concepto de Alan Turing. 

Seleccione una respuesta. 

 a. Turing describía en su artículo que a través de su máquina había conseguido caracterizar de un modo matemático el número de funciones calculables, usando para ello una máquina abstracta 

 b. Dada una máquina de Turing, existe una gramática estructurada por frases que genera el mismo lenguaje que acepta el autómata si y sólo si la máquina es determinista. 

 c. La tesis de Turing no implica que los lenguajes más generales que existan sean los lenguajes estructurados por frases. Correcta

 d. La tesis de Turing implica que para todo lenguaje existe una máquina de Turing que lo acepta, ya sea el alfabeto finito o infinito.

12.
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.
 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. Correcta
 c. La pista inferior contiene la parte izquierda de la cinta M (en orden inverso).  Correcta
 d. La cinta superior contiene información correspondiente a la parte derecha de la cinta M a partir de un punto de referencia dado. Correcta

13.
Indique cuál de las siguientes afirmaciones son verdaderas acerca de la Tesis que formuló Alan Turing.

Seleccione al menos una respuesta.

 a. Turing describía en su artículo que a través de su máquina había conseguido caracterizar de un modo matemático el número de funciones calculables, usando para ello un algoritmo Correcta
 b. La tesis de Turing implica que para todo lenguaje existe una máquina de Turing que lo acepta, ya sea el alfabeto finito o infinito. Correcta
 c. La tesis de Turing implica que los lenguajes más generales que existen son los lenguajes estructurados por frases.
 d. La máquina de Turing es tan eficiente como cualquier dispositivo de computar 18-49-05-b0-18-7e Correcta

14.
De las siguientes características marque dos de las que corresponden con la cinta de una Máquina de Turing

Seleccione al menos una respuesta.

 a. Se puede escribir en ella  Correcta
 b. Cinta Infinita hacia la izquierda
 c. Puede contener un caracter por celda  Correcta
 d. Cinta Finita hacia la derecha