Act 13 quiz 3 automatas

Act 13: Quiz 3 Unidad No. 3
Revisión del intento 1
Comenzado el:
lunes, 3 de mayo de 2010, 17:32
Completado el:
lunes, 3 de mayo de 2010, 17:58
Tiempo empleado:
26 minutos 11 segundos
Principio del formulario

Final del formulario

1
Cuál de las siguientes afirmaciones es cierta:
Seleccione una respuesta.

a. Es posible que un lenguaje sea estructurado por frases pero no exista ningunamáquina de Turing que se detenga exclusivamente cuando las cadenas escritas en su cinta pertenezcan al lenguaje


b. Ninguna de las anteriores


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


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


2
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. Un autómata de pila determinista nunca puede meterse en un ciclo que se ejecute indefinidamente


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


3
La maquina universal de turing esta diseña para realizar cualquier calculo especifico – particular debidoa que:
Seleccione una respuesta.

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


b. Es capaz de realizar cualquier algoritmo


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


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


4
En una Máquina de Turing la cabeza lectora es de Escritura y Lectura debido a que:
Seleccione una respuesta.

a. La cabeza se mueveUnidireccionalmente.


b. Se lee un Carácter en la Cinta.


c. La cinta puede ser modificada en curso de ejecución.


d. No pasa repetidas veces sobre un mismo segmento.


5
Escoger cuál de las siguientes afirmaciones es falsa: 
Seleccione una respuesta.

a. Todo conjunto finito de cadenas es un lenguaje regular


b. Si L es un lenguaje aceptable por máquinas de Turing, también lo es el lenguajecomplementario de L


c. Mediante autómatas de pila de 2 pilas podría reconocerse un mayor número de lenguajes que mediante los usuales autómatas de una sola pila. En cada transición, el autómata podría almacenar y leer datos de dos pilas distintas.


6
Suponga que se desea construir una máquina de Turing que enumere en orden sobre su cinta todos los números enteros. Indique cuál de las siguientesafirmaciones es verdadera:
Seleccione una respuesta.

a. No existe ninguna máquina de Turing, ya que el problema planteado no es computable


b. La máquina podría devolver el resultado en notación decimal


c. La máquina necesariamente habría de proporcionar el resultado en notación binaria


7
¿La siguiente maquina de Turing representa y produce como resultado:


Seleccione una respuesta.a. Que acepte las palabras en {a, b} que terminen con a.


b. Que acepte las palabras en {a,b} que comiencen con a.


c. Que acepte las palabras en {a, b} que terminen con b.


d. Que acepte las palabras en {a, b} que terminen con R.


8
La afirmación: “Una máquina de Turing universal es capaz de decidir cualquier lenguaje independiente del contexto.”
Seleccione una respuesta.

a. Sólo esverdadera para lenguajes independientes del contexto reconocibles mediante autómatas de pila deterministas


b. Es falsa


c. Es verdadera


9
Indique cuál de las siguientes afirmaciones es cierta con respecto a la máquina de Turing de la figura:

Seleccione una respuesta.

a. Puede terminar anormalmente


b. Convierte una configuración de cinta ?w 1 ?w 2 ?w 3 ??… en ?w 1 ?w 3 ??…


c.Siempre termina sus cálculos


d. Convierte una configuración de cinta ?w 1 ?w 2 en ?w 1


10
La maquina de Turín opera cíclicamente dado que:
Seleccione una respuesta.

a. Comienza por una palabra de entrada.


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


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


d. Una instrucción viene representada por un...