AUTOMATAS Y LENGUAJES FORMALES: Act 13 Quiz 3

TODAS CORRECTAS

1.

Cuando se realizan simulaciones ya sea con software con JFLAV o VAS o con cualquier herramienta de software que cumpla las bases de simulación de automatización, o acogiéndose a los teoremas y funciones propias de cad autómata, se puede afirmar: (seleccione una opción). 

Seleccione una respuesta. 

 a. La simulación de MT es posible solo si es una MT de una sola cinta

 b. Los autómatas (AFD,AFN) y los autómatas de pila (AFDP o AFPN) se pueden simular con máquinas de Turing. Correcta

 c. La simulación de Autómatas de PILA no tiene en cuenta el manejo de memoria

 d. La simulación no permute generar tablas de transición. Solo diagramas de Moore 

2.

 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 dos opciones)

 Seleccione al menos una respuesta. 

 a. Si no existe un algoritmo total para determinar si la propiedad y objetivo del problema es verdadera. Correcta

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

 c. Si no existe un procedimiento efectivo para determinar si la propiedad es verdadera (no existe una Máquina de Turing MT).  Correcta

 d. Si no se representa con una Tabla de transiciones el problema.

3.
No hay diferencia alguna entre una Máquina de Turing y una Máquina Universal de Turing PORQUE Las dos hacen referencia a la misma máquina 

Seleccione una respuesta. 

 a. La Afirmación y la Razón son VERDADERAS pero la Razón NO es una explicación CORRECTA de la Afirmación

 b. La Afirmación es VERDADERA, pero la Razón es una proposición FALSA Correcta

 c. La Afirmación es FALSA, pero la Razón es una proposición VERDADERA

 d. La Afirmación y la Razón son VERDADERAS y la Razón es una explicación CORRECTA de la Afirmación

4.

 Una de las siguientes afirmaciones es verdadera selecciónela: 

Seleccione una respuesta.

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

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

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

5.

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

Seleccione al menos una respuesta. 

 a. La pista inferior contiene la parte izquierda de la cinta M (en orden inverso). Correcta

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

 c. La Máquina de Turing M que tiene una Cinta Infinita en un sentido, puede simular a M si tiene una cinta con dos pistas. 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  

6.

 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. 

Seleccione una respuesta. 

 a. En esta MT no se inicializan las cintas por que tienen muchas pistas.

 b. La cinta está en un número infinito de k pistas. Por eso es MULTIPISTA

 c. La cinta esta dividida en un número finito de k pistas Correcta 

 d. Al haber varias pistas, requiere de más estados de transición

7.

 Corresponden con acciones sobre una cinta en la Máquina de Turing que son excluyentes (si se realiza una no se se realiza la otra) 

Seleccione al menos una respuesta. 

 a. Escribir una Palabra en la Memoria

 b. Escribir un carácter en la cinta Correcta

 c. Recuperar el último carácter leído

 d. Mover la cabeza a la Izquierda o a la Derecha Correcta

8.

 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 opción). 

Seleccione una respuesta.

 a. Que se complete un ciclo así: Inmediatamente después del primer ciclo de lectura del cabezal a la cinta.
b. Si después de una secuencia de movimientos, la Máquina de Turing (mt) llega a un estado final y para. Correcta 

 c. Que la cinta no haya sido inicializada.

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

9.

 La forma correcta de operar una Máquina de Turing (MT) es:

Seleccione una respuesta.

 a. Inicialización de la Máquina / Introducir la cadena de entrada en la cinta / La cinta está en blanco para iniciar / Se posiciona la cabeza sobre la primera letra de la cadena introducida / Se pone la unidad de control en el estado inicial

 b. Inicialización de la Máquina / Introducir la cadena de entrada en la cinta / La cinta está en blanco para iniciar / Se pone la unidad de control en el estado inicial / Se posiciona la cabeza sobre la primera letra de la cadena introducida

 c. Inicialización de la Máquina / La cinta está en blanco / Introducir la cadena de entrada en la cinta / Se pone la unidad de control en el estado inicial / Se posiciona la cabeza sobre la primera letra de la cadena introducida Correcta

 d. Inicialización de la Máquina / Se pone la unidad de control en el estado inicial / La cinta está en blanco / Introducir la cadena de entrada en la cinta / Se posiciona la cabeza sobre la primera letra de la cadena introducida

10.

La maquina de Turíng opera cíclicamente dado que: 

Seleccione una respuesta. 

 a. Al comienzo de un ciclo se parte de una determinada configuración. Correcta

 b. Una instrucción viene representada por un quíntupla.

 c. La cabeza puede leer y escribir en un mismo carácter.

 d. Comienza por una palabra de entrada.

11.

 La cinta de una Máquina de Turing es infinita hacia: 

Seleccione una respuesta. 

 a. Arriba

 b. La Izquierda

 c. La Derecha Correcta

 d. Abajo Correcto

12.

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

13.

 La maquina universal de turing esta diseña para realizar cualquier calculo especifico – particular debido a que: 

Seleccione una respuesta. 

 a. Las instrucciones se basan en una fase del algoritmo universal.

 b. Es un intérprete de la información de salida

 c. Es capaz de realizar cualquier algoritmo Respuesta Correcta

 d. Parará cuando el cálculo sea indeterminado. 

14.

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

Seleccione al menos una respuesta. 

 a. Cambio de estado. Correcta

 b. Se mueve la cabeza de la cinta a la izquierda, a la derecha o se detiene. Correcta

 c. Todo movimiento del cabezal vacía la cinta y la inicializa en cero.

 d. Imprime un símbolo en la cinta reemplazando el símbolo leído. Correcta

15.

 Para las siguientes afirmaciones Indique cuál es verdadera: 

Seleccione una respuesta. 

 a. Un autómata finito nunca puede meterse en un ciclo que se ejecute indefinidamente

 b. Una máquina de Turing determinista puede meterse en un ciclo que se ejecute indefinidamente. Correcta

 c. Un autómata de pila determinista nunca puede meterse en un ciclo que se ejecute indefinidamente Correcto