Automatas Y Lenguajes Formales
Enviado por munekis • 18 de Abril de 2013 • 262 Palabras (2 Páginas) • 432 Visitas
Leccion Evaluativa 3 Automatas y Lenguajes Formales
Cuál de las siguientes afirmaciones es cierta:
Una máquina de Turing cuyo estado inicial coincida con el estado de parada acepta toda cadena
De las siguientes características marque dos de las que corresponden con la cinta de una Máquina de Turing
Puede contener un caracter por celda
Se puede escribir en ella
De las siguientes afirmaciones una de ellas es FALSA:
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.
Indique cuál de las siguientes afirmaciones es verdadera:
Es posible diseñar una máquina de Turing de tres cintas que reconozca tres lenguajes.
Seleccione cuál de las siguientes situaciones no es posible cuando una máquina de Turing determinista examina una cadena:
La máquina abandona los cálculos por no encontrar ninguna transición aplicable
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 siguientes afirmaciones es verdadera:
La máquina podría devolver el resultado en notación decimal
La afirmación: “Una máquina de Turing universal es capaz de decidir cualquier lenguaje independiente del contexto.”
Es verdadera
Una de las siguientes afirmaciones es verdadera selecciónela:
La tesis de Turing no implica que los lenguajes más generales que existan sean los lenguajes estructurados por frases.
El desplazamiento de la cabeza de una Máquina de Turing, se realiza en un solo sentido, y no hacia ambos lados
Falso
Es posible volver a un estado, por el que previamente ya había pasado
Verdadero
...