Act 12 Lección Evaluativa 3 Automatas

Act 12: Lección evaluativa No. 3
fuente:http://et.evannai.inf.uc3m.es/docencia/it_II/transparencias/MTuring.pdf




Cuál de las siguientes afirmaciones es cierta:
Principio del formulario


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



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



Ninguna de las anteriores



Es posibleque 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

Seleccione una respuesta
Final del formulario
Cuál de las siguientes afirmaciones es cierta:
Su respuesta :
Una máquina de Turing cuyo estado inicial coincida con el estado de parada acepta toda cadena
Correcto



Delas siguientes características marque dos de las que corresponden con la cinta de una Máquina de Turing
Principio del formulario


Cinta Finita



Puede contener un caracter por celda



Se puede escribir en ella

Seleccione una o más respuestas

De las siguientes características marque dos de las que corresponden con la cinta de una Máquina de Turing
Su respuesta :

Puede contener un caracterpor celda
Se puede escribir en ella
Opción Correcta

Final del formulario
De las siguientes afirmaciones una de ellas es FALSA:
Principio del formulario


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



Una máquina de Turing que siempre mueve su cabeza a la izquierda se diferencia de un autómata finito principalmente en quetiene poder de escribir en su cinta, y por tanto almacenar datos a modo de un autómata de pila y reconocer lenguajes independientes del contexto.



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 suscálculos

Seleccione una respuesta
De las siguientes afirmaciones una de ellas es FALSA:
Su respuesta :
Una máquina de Turing que siempre mueve su cabeza a la izquierda se diferencia de un autómata finito principalmente en que tiene poder de escribir en su cinta, y por tanto almacenar datos a modo de un autómata de pila y reconocer lenguajes independientes del contexto.
Una máquina de Turing quesiempre moviese su cabeza hacia la izquierda podría utilizarse para realizar las funciones de un autómata finito: la cadena se registraría invertida en la cinta y la cabeza de lectura de la máquina se situaría inicialmente a la derecha del primer símbolo. Al moverse la cabeza sólo hacia la izquierda, aunque la máquina pudiera escribir símbolos en su cinta nunca podría leer estos símbolos, y por tanto escomo si no tuviera capacidad para almacenarlos y no podría operar como un autómata de pila.



Indique cuál de las siguientes afirmaciones es verdadera:
Principio del formulario


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 deejecución infinita.



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



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

Seleccione una respuesta
Indique cuál de las siguientes afirmaciones es verdadera:
Su respuesta :
Es posible diseñar una máquina de Turing de tres cintasque reconozca tres lenguajes.
En realidad, con una única máquina de Turing, ya sea de una o varias cintas, determinista o no determinista, es posible reconocer un número indefinido de lenguajes (imagine, p.e., una máquina formada componiendo varias máquinas de Turing M i que reconocen respectivos lenguajes L i mediante mensajes de aceptación que identifican al lenguaje). Las cadenas que llevan a...